Problem of the Week

Imagine that n people are playing tennis, where n is a positive integer. They each play each other exactly once, and the winner and loser of each match are recorded. There are no ties. Prove that it is possible to order the n people such that the first person beats the second person, the second person beats the third person, and so on until the (n-1)st person beats the nth person.

The solution will be posted later this week.

There were no submissions so this problem may be reused in the future.

Consider all n-gons of area 1 in Euclidean space where n is a fixed integer ≥3. Prove that the n-gon with the smallest perimeter is regular. You may assume Bretschneider’s Formula and that such an n-gon with minimum perimeter exists.

Hint: Proving that the polygon is regular is the same as proving it is equilateral and cyclic.

Notice that a player wins when they move the rook to Row 1, Column 1. When X does not equal Y, the first player can move the rook to a square where X=Y on every turn, preventing the second player from ever winning. When X equals Y, the second player can move the rook to a square where X=Y on every turn, preventing the first player from ever winning.

Thus, the first player wins when X≠Y.

Imagine that there is a chessboard of infinite length and width. A rook is placed on the Row X and Column Y. Two players take turns moving the rook such that either the row number or column number decreases. A player loses when they are unable to make a move on their turn. For what X and Y will the first player win?

Let us find the sum of all of the numbers. Note that this is an integer. The sum is going to be the sum of all the possible results of the sum of 9 of them divided by 9. Note that (82+83+84+85+87+89+90+91+92) mod 9 is 0, so 90 must be repeated in order for the sum of the numbers to be an integer. Thus, the sum of all of them is (82+83+84+85+87+89+90+91+92+90)/9 = 97.

The 10 integers are then 5, 6, 7, 7, 8, 10, 12, 13, 14, 15.

Ten (not necessarily all distinct) integers have the property that if all but one of them are summed, nine of the possible sums are: 82, 83, 84, 85, 87, 89, 90, 91, 92. What are the 10 integers?

Let the people be person A and person B. The idea is to think about it from an outsider’s perspective who knows the possible sums of the sticky note numbers. At the beginning, the possibilities for the sums are (0,6), (1,5), …, (6,0), (0,7), (1,6), …, (7,0). Draw an a-edge between any two states (a,b) and (a’,b’) if person A cannot tell the difference between them, i.e. b = b’ and a not = a’. Similarly, draw a b-edge between any two states (a,b) and (a’,b’) if person B cannot tell the difference between them, i.e. a = a’ and b not = b’.

Perform the following algorithm with the goal of removing possible states whenever a person says no.

Without loss of generality, assume A answers the question. Let S be the set of states which are unambiguous for A, i.e. they are not connected to another state by an a-edge. If A answers yes, we are done. If A answers no, then remove all states in S because A would have said yes in any of those states.

Repeating this process removes all of the states, so the answer is yes.

In this case, (0,7) is removed. Then (0,6) and (7,0) are removed. Then (1,6) and (6,0) are removed. Then (1,5) and (6,1) are removed. Then (2,5) and (5,1) are removed. Then (2,4) and (5,2) are removed. Then (3,4) and (4,2) are removed. Then B would say yes at this point. They would have said no 3 times before this point.

Say there are two people with sticky notes on their foreheads. On each of the notes, the number 3 is written, but the people can only see the others’ sticky notes and not their own. All they know is that their number is a nonnegative integer. A person instructs them that the sum of their sticky note numbers is 6 or 7. They each take turns saying whether or not they know their own number. Will someone eventually say yes? If so, who would say yes, and how many times would that person have answered no before answering yes?

Answer: A holds two knives, m and n, where m points along an edge of the cake and n points parallel to m and is in a location such that the piece of the cake between m and n is one-half by A’s standard. A then slowly and continuously moves m and n simultaneously in the direction away from that edge, keeping the piece between m and n one-half by their standard at all times. B announces “stop” whenever this in-between piece is one-half by their standard, and then B takes that piece, while A takes the remainder of the cake.

There must be a point where B announces “stop,” because if the initial in-between piece is more than one-half by B’s standard, the final in-between piece must be less than one-half, so by continuity, there must be a point where the in-between piece is exactly one-half to B. A similar argument holds when the initial in-between piece is less than one-half by B’s standard.

Devise a strategy to divide a rectangular cake between two people, A and B, such that both A and B receive exactly one-half of the cake by their standard. An intuitive strategy, such as dividing the cake into two pieces with equal area, does not suffice. For example, A may value strawberries and receive the piece with fewer strawberries, so by A’s standard, their piece is less than one-half of the cake. Whereas B may value chocolate and receive a piece with more chocolate, so by B’s standard, their piece is more than one-half of the cake.

The best strategy is: I should flip until the number of heads exceeds the number of tails, and then stop immediately. The expected value for this would be pi/4.

There is a game: I have a coin, which I keep flipping. I can stop at any time, and when I do I get a score of (total # of heads) / (total # of flips). Create a strategy that maximizes the expected value of my score.

Answer: Nothing will happen. The lions will not eat.

Let us prove the general statement: if there are n lions and 1 sheep, if n is even, then nothing will happen, and if n is odd, then the lions will all try to eat the sheep and after a lion has eaten it, nothing will happen.

For the base case, if there is 1 lion and 1 sheep, the lion just eats the sheep.

Assume that the inductive hypothesis holds for n lions and 1 sheep. Consider the n+1 lions and 1 sheep case. Assume n is odd for now. Say one of the n+1 lions eats the sheep. Then it falls asleep, essentially acting as the sheep while there are n other lions. Because of the inductive hypothesis, the sleeping lion will be eaten, so as a result, it cannot eat the sheep in the first place. 

Now assume that n is even. If one of the n+1 lions eats the sheep, it will fall asleep and there are n other lions. By the inductive hypothesis, nothing will happen to the sleeping lion. Thus, all of the lions will immediately try to eat the sheep, but after one of the lions succeeds, nothing will happen.

Thus by the principle of mathematical induction, we proved the more general statement. Thus, in the 10 lion case, nothing will happen.

There are 10 hungry lions and 1 sheep in a cage. The lions will only eat sheep or sleeping lions. If a lion eats anything, it falls asleep from a food coma. The lions are perfectly rational and their goal is to eat as much as they can, but if they would die as a result of eating, they will not eat. What will happen in this situation, i.e. how many sheep and lions will survive after all eating has occurred?

1) 1, 3, 4, 6 = 6 / (1 - 3/4)

2) 3, 3, 7, 7 = (3 + 3/7) * 7

3) 3, 3, 8, 8 = 8 / (3 - 8/3)

4) 1, 5, 5, 5 = (5 - 1/5) * 5

Make 24 using +, -, *, /, () and the following numbers exactly once:

1) 1, 3, 4, 6

2) 3, 3, 7, 7

3) 3, 3, 8, 8

1) 1, 5, 5, 5