combinatorics
Budget: $10 – $30 CAD
1 > Prove that among any n positive integers, there exist some whose sum is divis- ible by n.
2 >
To play the Texas lottery game Lotto Texas, a gambler selects six different num- bers between 1 and 54. The order of selection is unimportant.
(a) Prove that if 10 people play Lotto Texas, then there must exist two whose lists of 6 chosen numbers have at least one number in common. (For instance, Alice chose 2, 7, 17, 24, 42, 51 and Bob chose 16, 22, 31, 42, 44, 49)
(b) Prove that if 100 people play Lotto Texas, then there must exist two whose lists of 6 chosen numbers have at least two numbers in common. (For instance, Alice chose 2, 7, 17, 24, 42, 51 and Bob chose 17, 22, 31, 42, 44, 49)
3 >
Consider a 5 × 5 chessboard. Prove that no matter how the 25 cells are colored in red and blue (each cell is either red or blue), there exist 4 cells of the same color whose centers determine a rectangle with sides parallel to the sides of the board.
Is the statement true for a 4 × 4 chessboard? What about 4 × 6 chessboard?
4 >
Find the smallest value of m so that the following statement is valid: Any col- lection of m distinct positive integers must contain at least two numbers whose sum or difference is a multiple of 10. Prove that your value is best possible.
2 >
To play the Texas lottery game Lotto Texas, a gambler selects six different num- bers between 1 and 54. The order of selection is unimportant.
(a) Prove that if 10 people play Lotto Texas, then there must exist two whose lists of 6 chosen numbers have at least one number in common. (For instance, Alice chose 2, 7, 17, 24, 42, 51 and Bob chose 16, 22, 31, 42, 44, 49)
(b) Prove that if 100 people play Lotto Texas, then there must exist two whose lists of 6 chosen numbers have at least two numbers in common. (For instance, Alice chose 2, 7, 17, 24, 42, 51 and Bob chose 17, 22, 31, 42, 44, 49)
3 >
Consider a 5 × 5 chessboard. Prove that no matter how the 25 cells are colored in red and blue (each cell is either red or blue), there exist 4 cells of the same color whose centers determine a rectangle with sides parallel to the sides of the board.
Is the statement true for a 4 × 4 chessboard? What about 4 × 6 chessboard?
4 >
Find the smallest value of m so that the following statement is valid: Any col- lection of m distinct positive integers must contain at least two numbers whose sum or difference is a multiple of 10. Prove that your value is best possible.