Sasha and Serg plays next game with $100$-angled regular polygon . In the beggining Sasha set natural numbers in every angle. Then they make turn by turn, first turn is made by Serg. Serg turn is to take two opposite angles and add $1$ to its numbers. Sasha turn is to take two neigbour angles and add $1$ to its numbers. Serg want to maximize amount of odd numbers. What maximal number of odd numbers can he get no matter how Sasha plays?
Problem
Source: St Petersburg Olympiad 2011, Grade 9, P7
Tags: combinatorics, number theory
29.09.2017 16:15
Any solution.
09.10.2017 18:32
Help me please.
18.10.2017 13:26
Answer: 27 Let the numbers of each polygon be $a_{0},a_{1},\ldots,a_{99}$ counterclockwise. We show the following two 1. Sasha can retain polygon at most 27 odd integers no matter how Serg plays. 2. Serg can achieve at least 27 odd integers no matter how Sasha plays. Proof of 1. We make 25 groups of numbers $a_{0},a_{1},a_{50},a_{51}$;$a_{2},a_{3},a_{52},a_{53}$;$\cdots$;$a_{48},a_{49},a_{98},a_{99}$. These are four numbers each are from two adjacent pair of opposite side. Sasha set $a_{0},a_{2},a_{4},\ldots,a_{48}$ 1 and others 2. Then, we can see that only one number is odd in each group. We show that Sasha can retain this property in each moment after Sasha's turn. We consider the Sreg's turn just before then. WLOG, we assume $a_{0}$ was odd, other numbers were even and Serg add $a_{0},a_{50}$ or $a_{1},a_{49}$. In the former case, only $a_{50}$ is odd and Sasha add 1 to $a_{0},a_{50}$ retaining the property. In the later case, $a_{0},a_{1},a_{49}$ is odd and Sasha add $a_{0},a_{1}$. Now, only $a_{49}$ is odd and retaining the property. Therefore, Sasha can retain the property with 25 odds. Serg may break the property for one group with total $27$ odds but Sasha can repair at the next turn. Proof of 2. We make another 25 groups of numbers: $a_{0},a_{50}$; $a_{2},a_{52}$; $\cdots$; $a_{48},a_{98}$. We only consider the odd number in these groups. We show that Serg can achieve the state before his turn that at least $25$ odd integers in these groups are odd. If there are at most $24$ odds in these groups, he can select a group, in which all two numbers in that group is even. Then, Serg add 1 to these group and the number of odds are increased by 2. Since Sasha can add only one number in these groups, there is still 1 more odds than the previous moment before Serg's turn. In this way, Serg can increase number of odds until 25. Once, he has 25 odds before his turn, he can add two even numbers which are opposite position. Then, there are at least 27 odds.