The following puzzles were used as the puzzle of the week at the Macalester College Problem of the Week.
Find an arrangement of 50 non-overlapping unit squares so that each one touches exactly 4 others.
The positive integers x = 692 and y = 1118 have a curious property:
The sum of their cubes starts with the digits of the sum of their squares. There are other pairs of positive integers with this property. Find another such pair.
Start with n players each with $1. Each round, two players X and Y with money left are chosen randomly, and a coin is flipped. If it is heads, X pays Y $1, and if it is tails, Y pays X $1. What is the expected number of rounds until one person has all $n?
Find a finite set of interior-disjoint unit squares in the plane such that each square touches exactly three others.
Find a finite set of interior-disjoint 2×1 dominoes in the plane such that each one touches exactly four others.
Here "touches" means that the intersection is a line segment that is more than a point.
You are the director of a tournament involving four players, A, B, C, D. The players are linearly ordered in terms of ability (perhaps C is better than A is better than B is better than D), but you do not know this order. Your job is to design a tournament that consists of a series of N games in order to maximize the probability that the best player is the champion. In every game between two players, the better player has a 2/3 chance of winning. The probability here is over the randomness in the game results and the randomness (as far as the director is concerned) in the ability-ordering of the players (all orderings are equally likely).
For example, if N = 3, the best tournament is A vs. B, C vs. D, and then the two winners against each other. The best player will win with probability (2/3)(2/3) or 44.4% of the time. The tournament with A vs. B, winner vs. C, and winner of previous vs. D is not as good. The best player wins that tournament with probability (2/4)(2/3)3 + (1/4)(2/3)2 + (1/4)(2/3) = 42.6%.
For N = 7, the best known tournament is A vs. B, C vs. D, and then a best-of-5 between the winners. Here the best player wins with probability (2/3) [(2/3)5 + 5 (2/3)4 (1/3) + 10 (2/3)3 (1/3)2] = 52.7%. An alternative is: A and B play a best-of-3, C plays D in a best-of-3, and the winners play each other; here the best player wins with probability [(2/3)3 + 3 (2/3)2 (1/3)](2/3) = 49.4%.
Suppose you have N=8 games at your disposal. Design a tournament that has the best player winning more than 53% of the time.