Maths Olympiad Prep

Library / /170 of 224

Combinatorics Difficulty 6.6 National Olympiad Prove it Belarus

Exactly one integer number from 11 to 4949 is written in each cell of the 7×77 \times 7 square table (see the figure). Per move it is allowed to choose any cell then simultaneously to increase (to decrease) the number in this cell by 11 and to decrease (to increase respectively) the numbers in some two adjacent cells by 11 (two cells are adjacent if they have a common side).

<table><thead><tr><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td></tr><tr><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td></tr><tr><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td></tr><tr><td>29</td><td>30</td><td>31</td><td>32</td><td>33</td><td>34</td><td>35</td></tr><tr><td>36</td><td>37</td><td>39</td><td>39</td><td>40</td><td>41</td><td>42</td></tr><tr><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td><td>48</td><td>49</td></tr></tbody></table>

a) Is it possible to obtain the table with the same numbers in all its cells after the finite number of these moves?

b) Is it possible to obtain the table with 20132013 in all its cells after the finite number of these moves?

Solution

a) We show that using the allowed moves we can decrease any number in the table by 33 so that all other numbers in the table keep their values. We will not consider the whole table but only the number xx which will be decreased by 33 and three more numbers aa, bb, and cc which occupy (together with xx) the cells of some 2×22 \times 2 square).

Figure 1

So we can consecutively decrease all numbers in the table so that to obtain their residues modulo 33, i.e. to obtain the table:

Figure 2

Consider the 6×66 \times 6 down-left corner square. It consists of the same four 3×33 \times 3 squares:

Figure 3

It is easy to see that after two moves (1+1+1-1+1+1) each of these 3×33 \times 3 squares is transformed into the square with 11's in all its cells. So we obtain the table:

<table>
<tr>
<td>1</td>
<td>2</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>2</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>2</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
</table>

Further, we transform the first row of the table:

1 2 0 1 2 0 1 1 1 1 0 2 0 1 1 1 1 1 1 1 1\text{1 2 0 1 2 0 1 1 1 1 0 2 0 1 1 1 1 1 1 1 1}

In a similar way we can transform the last column of the table. As the result we obtain the table with 11 in all its cells.

b) Consider the chess coloring of the table. For the definiteness we suppose that the corner cells are white. So, there are 2525 white and 2424 black cells in the table. All white cells are occupied with odd numbers, and all black cells are occupied with even numbers. Therefore, the sum SwS_w of the numbers in the white cells is equal to 1+49225=2525\frac{1+49}{2} \cdot 25 = 25 \cdot 25, and the sum SbS_b of the numbers in the black cells is equal to 2+48224=2524\frac{2+48}{2} \cdot 24 = 25 \cdot 24. So, SwSb=25S_w - S_b = 25.

It is easy to see that any allowed move does not change the residue modulo 33 of the difference between the sums of the numbers in the white and black cells. If all cells in the table are occupied with the number 20132013, then this difference is equal to 20132013. But 201325(mod3)2013 \ne 25 \pmod{3}, so we cannot obtain the table with 20132013 in all its cells.

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.