Maths Olympiad Prep

Library / /59 of 62

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Ukraine

A square n×nn \times n is divided into n2n^2 cells. In total n2n^2 tokens are placed at some cell. During every round, a player can move one token from cell AA to cell BB, and one token from cell AA to cell CC, provided that cell AA contained at least two tokens, BB and CC are symmetric with respect to AA, and finally BB and CC are adjacent to AA. Is it possible that after a few such rounds every cell on the board contains exactly one token, in case:
a) n=2016n = 2016;
b) n=2017n = 2017?

Solution

Answer: a) impossible; b) possible.

a) Consider square n×nn \times n, for positive integer nn. Let us denote the most left column by 11, adjacent column by 22, and so on, the most right column by nn. For any cell cc we denote function w(c)=bw(c) = b, provided that cell cc is located in the column bb. For every token TT in the same way let w(T)=bw(T) = b provided that token TT is placed on the cell in the column bb at the moment. Finally, by WW we denote the sum of w(T)w(T) for all tokens TT on the board. It is clear that after every round WW is not changed. At the end of our process we must have
W=n+2n++n2=n(1+2++n)=n2(n+1)2. W = n + 2n + \dots + n^2 = n \cdot (1 + 2 + \dots + n) = \frac{n^2(n+1)}{2}.
At the beginning of our process W=ln2W = l \cdot n^2 provided that all tokens are placed at the cell in ll. And for n=2016n = 2016 we get a contradiction.

b) Let us consider the case n=2017n = 2017. It follows from previous arguments that the statement of the problem could be true only in the case when all tokens are placed on the central cell at the beginning. In this case we provide the algorithm. Let us note that in every cell we write the number of tokens placed there. Using induction, we prove the following statements

Statement 1. For every positive integer nn in a row of length 2n+12n+1 from the position
0;0;0;;0;2n+1;0;;0;00; 0; 0; \dots; 0; 2n+1; 0; \dots; 0; 0
we can get the position
1;1;1;;1;1;1;;1;11; 1; 1; \dots; 1; 1; 1; \dots; 1; 1

Statement 2. For every positive integer nn in a row of length 2n+12n+1 from the position
0;1;1;;1;3;1;;1;10; 1; 1; \dots; 1; 3; 1; \dots; 1; 1
we can get the position
1;1;1;;1;1;1;;1;11; 1; 1; \dots; 1; 1; 1; \dots; 1; 1

Proof. It is clear for n=1n=1. Suppose that for n=k1n=k-1 statements are true, let us prove them for n=kn=k. At the beginning, we have 2k+12k+1 tokens on the central cell. Two of them we will not move. The rest 2k12k-1 tokens we can move (according to the induction hypothesis) to the position
0;1;1;;1;1;3;1;1;;1;10; 1; 1; \dots; 1; 1; 3; 1; 1; \dots; 1; 1
Now consider the following replacing
0;1;1;;1;1;2;1;2;1;1;;1;10; 1; 1; \dots; 1; 1; 2; 1; 2; 1; 1; \dots; 1; 1
0;1;1;;1;2;0;3;0;2;1;;1;10; 1; 1; \dots; 1; 2; 0; 3; 0; 2; 1; \dots; 1; 1
0;1;1;;2;0;1;3;1;0;2;;1;10; 1; 1; \dots; 2; 0; 1; 3; 1; 0; 2; \dots; 1; 1
\dots
0;1;2;0;1;;1;1;1;3;1;1;1;;1;0;2;10; 1; 2; 0; 1; \dots; 1; 1; 1; 3; 1; 1; 1; \dots; 1; 0; 2; 1
0;2;0;1;1;;1;1;1;3;1;1;1;;1;1;0;20; 2; 0; 1; 1; \dots; 1; 1; 1; 3; 1; 1; 1; \dots; 1; 1; 0; 2
1;0;1;1;1;;1;1;1;3;1;1;1;;1;1;1;01; 0; 1; 1; 1; \dots; 1; 1; 1; 3; 1; 1; 1; \dots; 1; 1; 1; 0
We can apply the induction hypothesis now, and get
1;1;1;;1;1;1;;1;11; 1; 1; \dots; 1; 1; 1; \dots; 1; 1
Both statements are proved now.

We can easily prove the statement of the problem now. Divide all tokens into equal groups with 20172017 tokens in every group. Using our statements, we can replace tokens such that in every cell of the central column exactly one group will be placed. And then just use the statements again to replace tokens such that in every cell of every row exactly one token will be placed.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.