Olympiad Maths Prep

Library / /60 of 60

Combinatorics Difficulty 7.8 National olympiad, round 2 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 2n2n, n>1n>1 different in weight sectors (pieces). Weight of every piece is known by each player. After that they choose pieces according the following rules. At first Olesya chooses 1 piece, then Andriy chooses 2 pieces, but so, that pieces, that are left on table after her turn, form a sector. Then they choose in turns 2 pieces each so, that after every step pieces, that are left on the table, form a sector. By his last turn one of players takes the last piece. Each of players aims, that total weight of part of the cake, he or she took, is bigger, than opponent's one. For which nn Olesya can cut the cake so, that if by her first step she takes the smallest piece?
(Bogdan Rublyov)

Solution

Let's consider, which values nn can take.

If n=2k+1>1n = 2k+1 > 1, let's consider the following distribution of weights. Pieces n1n-1, nn and n+1n+1 have weight 1, and other ones – 0. Then after Olesya's first step Andriy can not take non-zero pieces. Until Andriy takes by his turn piece n2n-2 or n+2n+2, Olesya just makes her step so, that sector of taken pieces is symmetrical to sector with number 0. If Andriy takes by his turn one of pieces n2n-2 or n+2n+2, then it does not matter which other piece he takes, Olesya can take two pieces weighting 1 and win.

If Andriy by his first step takes pieces of zero weight 1 and 2n12n-1, Olesya chooses two big pieces with numbers 2 and 3. After this Andriy by his step can take at maximum two more big pieces, and Olesya by her turn – two more big pieces and win.

So, we assume, that Andriy by his first step chooses pieces 1 and 2 and we have the total weight 99100\frac{99}{100}. After that Olesya takes pieces 3 and 4 and we have the total weight 201100\frac{201}{100}. Andriy by any his step can not take piece 2n12n-1, because Olesya takes two more big pieces and wins. So Andriy has
---
to go in direction 4; 5; 6; ..., Olesya takes two neighboring in this direction. No body is beneficial to take a piece with number 2n12n-1, because then opponent can take two big pieces at once. So, they take zero pieces until they come to big pieces number 2n42n-4, 2n32n-3 and 2n22n-2. According to the order of steps, Andriy takes big pieces with numbers 2n32n-3 and 2n22n-2. Olesya by her last turn takes piece number 2n12n-1, and by last but one – two pieces with numbers 2n52n-5 and 2n42n-4, the last of which is big. In total we have, that Olesya's pieces' weight will be: 201100+101100=302100\frac{201}{100} + \frac{101}{100} = \frac{302}{100}, and Andriy's: 99100+199100=298100\frac{99}{100} + \frac{199}{100} = \frac{298}{100}. So, Olesya wins.

If n=2n=2, so by his first step Andriy will choose two the biggest pieces and win.
If n=4n=4, we have in total 2n=82n=8 pieces. Let's show, that Andriy always wins. Here number, which denotes the number of piece, also means its weight in comparisons. Let (k1,k,k+1)(k-1, k, k+1) denote the smallest in weight piece, that has corresponding number, [k1,k,k+1][k-1, k, k+1] – the biggest, and {k1,k,k+1}\{k-1, k, k+1\} – middle.
We can assume that 1+26+71+2 \ge 6+7. Let Andriy take by his first step 1+21+2 and does not win. This means, that Olesya could take set 6+7,3+76+7, 3+7 or 3+43+4 and win. Let's consider all these cases. Case 6+76+7 has contradiction. Really, as 1+26+71+2 \ge 6+7, and Andriy chooses [3,4,5]+{3,4,5}[3, 4, 5]+\{3, 4, 5\}, and Olesya has (3,4,5)(3, 4, 5), so Olesya loses.
If Olesya gets win after step 3+73+7, this means, that inequality is true:
3+7+(4,5,6)>12M>1+2+[4,5,6]+{4,5,6}.(1) 3+7+(4,5,6) > \frac{1}{2}M > 1+2+[4,5,6]+\{4,5,6\}. \quad (1)
Then Andriy by his first step takes not 1+21+2, but 6+76+7. Then he can take by his next step pair of pieces, including 3 (Olesya will not reach it). Then Andriy will have at least set: 6+7+3+(2,4)6+7+3+(2,4). As
6+7+3+(2,4)>3+7+(4,5,6)>12M, 6+7+3+(2,4) > 3+7+(4,5,6) > \frac{1}{2}M,
Andriy wins.
If Olesya gets win after step 3+43+4, this means, that inequality is true:
3+4+(5,6,7)>12M>1+2+[5,6,7]+{5,6,7}.(2) 3+4+(5,6,7) > \frac{1}{2}M > 1+2+[5,6,7]+\{5,6,7\}. \quad (2)
If Andriy by his first step plays 6+76+7, Olesya can not take 1+21+2 and 1+51+5, because Andriy will take winning combination 3+4+6+7>3+4+(5,6,7)>12M3+4+6+7 > 3+4+(5,6,7) > \frac{1}{2}M. Thus, Olesya can win with combination 4+54+5, thus inequality must be true:
4+5+(1,2,3)>12M>6+7+[1,2,3]+{1,2,3}.(3) 4+5+(1,2,3) > \frac{1}{2}M > 6+7+[1,2,3]+\{1,2,3\}. \quad (3)
If Andriy by his first step will play 1+71+7, so Olesya can not play 5+65+6 and 2+62+6, because then Andriy takes winning combination 3+4+1+7>3+4+(5,6,7)>12M3+4+1+7 > 3+4+(5,6,7) > \frac{1}{2}M. Thus, Olesya must win with combination 2+32+3, and thus inequality must be true:
2+3+(4,5,6)>12M>1+7+[4,5,6]+{4,5,6}.(4) 2+3+(4,5,6) > \frac{1}{2}M > 1+7+[4,5,6]+\{4,5,6\}. \quad (4)
If to add two last ratios, we have contradiction:
2+3+4+5+(1,2,3)+(4,5,6)>1+6+7+7+[1,2,3]+{1,2,3}+[4,5,6]+{4,5,6} 2+3+4+5+(1,2,3)+(4,5,6) > 1+6+7+7+[1,2,3]+\{1,2,3\}+[4,5,6]+\{4,5,6\}
as 2+3[1,2,3]+{1,2,3}2+3 \le [1, 2, 3] + \{1, 2, 3\}, 4+5[4,5,6]+{4,5,6}4+5 \le [4, 5, 6] + \{4, 5, 6\}, (1,2,3)1(1, 2, 3) \le 1, (4,5,6)6(4, 5, 6) \le 6, 0<7+70 < 7+7. Thus, Andriy has winning strategy, knowing ratio of weights of pieces.

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.