Olympiad Maths Prep

Library / /53 of 60

Combinatorics Difficulty 6.7 National olympiad Prove it Ukraine

Two players – Andriy and Olesya play the following game. On a table, there is a rounded cake, which is cut by one of them into 4n4n different in weight sectors (pieces). Weight of every part is known by each player. After that they choose pieces for themselves upon following rules. At first Andriy chooses 1 piece, then Olesya chooses 2 pieces, but so that the pieces, that are left after her turn, form a sector. Then they take in turns 2 pieces, so that after every step pieces that are on the table form a sector. Making the last step Andriy takes the last piece. Each player aims that the total weight of the part of the cake, he or she took, is bigger, than opponent's one. Is it possible that someone surely takes more than half of the whole cake if:
a) Olesya cuts the cake into sectors;
b) Andriy cuts the cake into sectors, but at his first step he is prohibited to take the biggest on weight piece?

Solution

a) Let's show how Olesya can cut the cake to win. Let MM denote the weight of the cake. She cuts it into 3 neighboring pieces weighting 13M\frac{1}{3}M (heavy), and all the rest have zero weight (light). Let's number the pieces clockwise 1; 2; ...; 4n4n. Piece number 4n4n is neighboring to 1. Let pieces 4n34n-3, 4n24n-2 and 4n14n-1 be heavy. Andriy can not begin with any of 5 pieces: 4n44n-4, ..., 4n4n, because otherwise Olesya by her first step will choose 2 heavy pieces and collect in total 23M>12M\frac{2}{3}M > \frac{1}{2}M. So Andriy chooses any other piece. Then the one who takes at least one of two pieces 4n44n-4 or 4n4n (even if together with one of heavy pieces), loses, because the opponent definitely can take 2 heavy pieces and collect more than half of the cake.

Thus, Andriy and Olesya have to make steps in sector between pieces 1 and 4n54n-5. After Andriy's turns 4n+14n+1 pieces will be taken, and after Olesya's turns 4n+3-4n+3. Thus, after completing the full sector between pieces 1 and 4n54n-5 Andriy will make his step and so he will lose.

b) Let's show how Andriy should cut the cake to win. Let's number pieces from 1 to 4n4n. Let there be 3 heavy pieces weighting 13M\frac{1}{3}M each, and the rest – light ones of zero weight. Let pieces 1, 3 and 5 be heavy ones. Then Andriy by his first step takes piece 3, then by his second turn he can take one more heavy piece and takes in total 23M>12M\frac{2}{3}M > \frac{1}{2}M.

It remains to satisfy the conditions of the task precisely. All the pieces must have different non-zero weight. For this in a) make the small pieces weight, for example, i5(4n3)(4n2)M\frac{i}{5(4n-3)(4n-2)}M, i=1;4n3i=1; 4n-3, then their sum
15(4n3)(4n2)M+25(4n3)(4n2)M++4n35(4n3)(4n2)M=(4n3)(4n2)10(4n3)(4n2)M=110M. \frac{1}{5(4n-3)(4n-2)}M + \frac{2}{5(4n-3)(4n-2)}M + \dots + \frac{4n-3}{5(4n-3)(4n-2)}M = \frac{(4n-3)(4n-2)}{10(4n-3)(4n-2)}M = \frac{1}{10}M.
Choose the big pieces weighting 29100M\frac{29}{100}M, 30100M\frac{30}{100}M and 31100M\frac{31}{100}M. Order of pieces does not play role. The same distribution of weights in b), but with condition, that 3rd piece has weight of 30100M\frac{30}{100}M.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.