Exercises
Multiple Choice
Articles
Open Problems
Login
27 items
Tagged:
clique number
x
counting
x
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Undergraduate
By
Chandra Chekuri
on July 29, 2012 | Updated Dec. 6, 2017
Diameter and low-degree vertex
Let \(G = (V,E)\) be an undirected connected graph. Suppose \(G\) has a pair of nodes \(s,t\) that are distance \(d\) apart. Show that there is a vertex \(v\in G\) such that the degree of \(v\) is at…
Computer Science
Mathematics
Algorithms
Graph Theory
counting
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Dec. 6, 2017
Counting intersections of chords
Consider \(n\) chords on a circle, each defined by its endpoints. Describe an \(O(n{\log}n)\)-time algorithm to determine the number of pairs of chords that intersect inside the circle. For example, i…
Computer Science
Algorithms
Data Structures
counting
sorting
0
Graduate
By
Shiva Kintali
on Aug. 29, 2012 | Updated Dec. 6, 2017
Random Intervals
There are \(n\) points on a line. These points are paired up at random to form \(n/2\) intervals. Prove that the probability that among these intervals there is one which intersects all the others i…
Mathematics
Puzzles
Probability
Puzzles
counting
0
Undergraduate
By
Shiva Kintali
on May 31, 2012 | Updated Dec. 6, 2017
Party Problem
Suppose there are six people at a party. Prove that there are always three of them so that every two know each other (or) no two know each other. In other words, let the edges of the complete graph o…
Mathematics
Puzzles
Combinatorics
Graph Theory
Puzzles
counting
extremal graph theory
interview question
0
Undergraduate
By
Shiva Kintali
on Aug. 29, 2013 | Updated Jan. 4, 2018
Even Subsets
A set \(T\) is called even if it has even number of elements. Let \(n\) be a positive even integer, and let \(S_1, S_2, \dots, S_n\) be even subsets of the set \(S = \){\(1,2,\dots,n\)}. Prove th…
Mathematics
Combinatorics
counting
0
Undergraduate
By
Shiva Kintali
on June 13, 2012 | Updated Dec. 6, 2017
Basics of Pigeonhole Principle
Prove the following : Given \(n\) integers, some nonempty subset of them has sum divisible by \(n\). Let \(A\) be a set of \(n+1\) integers from {\({1, 2,\dots , 2n}\)}. Prove that some element of \…
Mathematics
Discrete Mathematics
basics
counting
pigeonhole principle
0
High School
By
Shiva Kintali
on June 10, 2012 | Updated Dec. 6, 2017
Find the faulty Ball
There are 12 balls. They all look alike but one of them is faulty; it weights differently. It is not known, if this ball is heavier or lighter than the other balls. How do you find the faulty ball by …
Puzzles
Puzzles
counting
interview question
1
Undergraduate
By
Shiva Kintali
on Sept. 30, 2013 | Updated Jan. 4, 2018
Friends and Parties
Show that at a party of \(n\) people, there are two people who have the same number of friends in the party. Assume that friendship is symmetric. There are \(2n\) people at a party. Each person has…
Mathematics
Discrete Mathematics
counting
pigeonhole principle
0
High School
By
Shiva Kintali
on May 19, 2013 | Updated Dec. 6, 2017
Basics of counting
Let \(S = {1,2,...,n}\). How many ordered pairs \((A,B)\) of subsets of \(S\) are there that satisfy \(A \subseteq B\) ?
Mathematics
Combinatorics
basics
counting
0
Undergraduate
By
Shiva Kintali
on June 6, 2012 | Updated Dec. 6, 2017
Happy Ending Problem
Prove the following : Any set of five points in the plane in general position has a subset of four points that from the vertices of a convex quadrilateral. For any positive integer \(N\), any suffic…
Mathematics
Combinatorics
Geometry
counting
1
2
3
next page »
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
pigeonhole principle
circumcircle
incircle
jee
jee 2016
jee advanced
jee mathematics
basics
true or false
undecidability
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×