Maths Olympiad Prep

Library / /91 of 104

Combinatorics Difficulty 6.9 National Olympiad Prove it Bulgaria

Problem:

In every cell of a table n×nn \times n, n2n \geq 2, one of the numbers +1+1 and 1-1 is written. The cell on the ii-th row and jj-th column is denoted by (i,j)(i, j), i,j=0,1,,n1i, j = 0, 1, \ldots, n-1. The neighbors of the cell (i,j)(i, j) are the cells (i,j1)(i, j-1), (i,j+1)(i, j+1), (i1,j)(i-1, j) and (i+1,j)(i+1, j), where the numbers are taken modulo nn. At each step one replaces the number in each cell with the product of the numbers in the four neighbors of that cell. For example,

+1-1+1
+1-1-1
-1+1-1\rightarrow+1-1-1
-1+1+1
-1+1+1
.

A table is called "good" if after finitely many steps one obtains the table with +1+1 in every cell. Find all values of nn such that every table n×nn \times n is "good".

Solution

Solution:

We first prove that for any odd n3n \geq 3 there are n×nn \times n tables that are not "good". Consider an arbitrary n×nn \times n table and denote by PiP_{i}, i=1,2,,ni=1,2, \ldots, n, the product of the numbers in the ii-th row at the second last step. Then P1P3=P2P4==Pn1P1=PnP2=1P_{1} P_{3} = P_{2} P_{4} = \cdots = P_{n-1} P_{1} = P_{n} P_{2} = 1 and since nn is odd, it follows that P1=P2==PnP_{1} = P_{2} = \cdots = P_{n}. This argument shows that the row products in the initial table must be equal. Therefore any table which has not this property is not "good".

We now consider a table of order n=2kmn = 2^{k} m, where mm is an odd number and k1k \geq 1. After the first two steps the number in the position (i,j)(i, j) becomes equal to the product of the numbers in the positions (i2,j)(i-2, j), (i,j2)(i, j-2), (i,j+2)(i, j+2) and (i+2,j)(i+2, j). Therefore the resulting table after every even step can be obtained by applying the operation on the following four tables of order 2k1m2^{k-1} m:
- the table of all (i,j)(i, j) with ij0(mod2)i \equiv j \equiv 0 \pmod{2};
- the table of all (i,j)(i, j) with i0(mod2)i \equiv 0 \pmod{2}, j1(mod2)j \equiv 1 \pmod{2};
- the table of all (i,j)(i, j) with i1(mod2)i \equiv 1 \pmod{2}, j0(mod2)j \equiv 0 \pmod{2};
- the table of all (i,j)(i, j) with ij1(mod2)i \equiv j \equiv 1 \pmod{2}.

Now it follows by induction that the number n=2kmn = 2^{k} m has the required property if and only if the number 2k1m2^{k-1} m does. It is also easy to see that every table of order 22 is "good".

Therefore the required nn are n=2kn = 2^{k}, where kk is a positive integer.

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.