Browse · MathNet
Print58th Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
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 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 denote the weight of the cake. She cuts it into 3 neighboring pieces weighting (heavy), and all the rest have zero weight (light). Let's number the pieces clockwise 1; 2; ...; . Piece number is neighboring to 1. Let pieces , and be heavy. Andriy can not begin with any of 5 pieces: , ..., , because otherwise Olesya by her first step will choose 2 heavy pieces and collect in total . So Andriy chooses any other piece. Then the one who takes at least one of two pieces or (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 . After Andriy's turns pieces will be taken, and after Olesya's turns . Thus, after completing the full sector between pieces 1 and 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 . Let there be 3 heavy pieces weighting 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 .
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, , , then their sum Choose the big pieces weighting , and . Order of pieces does not play role. The same distribution of weights in b), but with condition, that 3rd piece has weight of .
Thus, Andriy and Olesya have to make steps in sector between pieces 1 and . After Andriy's turns pieces will be taken, and after Olesya's turns . Thus, after completing the full sector between pieces 1 and 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 . Let there be 3 heavy pieces weighting 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 .
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, , , then their sum Choose the big pieces weighting , and . Order of pieces does not play role. The same distribution of weights in b), but with condition, that 3rd piece has weight of .
Final answer
a) Yes. Olesya can cut and play so she surely gets more than half. b) Yes. Andriy can cut and play so he surely gets more than half even if he cannot take the heaviest piece on his first move.
Techniques
Games / greedy algorithms