Maths Olympiad Prep

Library / /110 of 133

Number theory Difficulty 6.6 National olympiad Prove it Saudi Arabia

Let n>3n > 3 be an odd positive integer not divisible by 33. Determine if it is possible to form an n×nn \times n array of numbers such that

a. The set of the numbers in each row is a permutation of 0,1,,n10, 1, \ldots, n-1; the set of the numbers in each column is a permutation of 0,1,,n10, 1, \ldots, n-1;

b. The board is totally non-symmetric: for 1i<jn1 \leq i < j \leq n and 1i<jn1 \leq i' < j' \leq n, if (i,j)(i,j)(i, j) \neq (i', j') then (ai,j,aj,i)(ai,j,aj,i)(a_{i, j}, a_{j, i}) \neq (a_{i', j'}, a_{j', i'}), where ai,ja_{i, j} denotes the entry in the ithi^{\text{th}} row and jthj^{\text{th}} column.

Solution

For 1i,jn1 \leq i, j \leq n, choose ai,ja_{i, j} equal to the remainder of 3i+j3i + j when divided by nn. Clearly, 0ai,jn10 \leq a_{i, j} \leq n-1, for 1i,jn1 \leq i, j \leq n.

If we fix a row 1in1 \leq i \leq n, ai,j1=ai,j2a_{i, j_1} = a_{i, j_2}, for 1j1,j2n1 \leq j_1, j_2 \leq n, implies 3i+j13i+j2(modn)3i + j_1 \equiv 3i + j_2 \pmod{n}, that is j1j2(modn)j_1 \equiv j_2 \pmod{n} and therefore j1=j2j_1 = j_2.

Hence, ai,1,,ai,na_{i, 1}, \ldots, a_{i, n} is a permutation of 0,1,,n10, 1, \ldots, n-1.

If we fix a column 1jn1 \leq j \leq n, ai1,j=ai2,ja_{i_1, j} = a_{i_2, j}, for 1i1,i2n1 \leq i_1, i_2 \leq n, implies 3i1+j3i2+j(modn)3i_1 + j \equiv 3i_2 + j \pmod{n}, that is 3i13i2(modn)3i_1 \equiv 3i_2 \pmod{n}. But nn is not divisible by 33. Therefore i1=i2i_1 = i_2. This proves that a1,j,,an,ja_{1, j}, \ldots, a_{n, j} is a permutation of 0,1,,n10, 1, \ldots, n-1.

Now, let 1i<jn1 \leq i < j \leq n and 1i<jn1 \leq i' < j' \leq n such that (ai,j,aj,i)=(ai,j,aj,i)(a_{i, j}, a_{j, i}) = (a_{i', j'}, a_{j', i'}) this implies that 3i+j3i+j(modn)3i + j \equiv 3i' + j' \pmod{n} and 3j+i3j+i(modn)3j + i \equiv 3j' + i' \pmod{n}. This is equivalent to 8i8i(modn)8i \equiv 8i' \pmod{n} and 8j8j(modn)8j \equiv 8j' \pmod{n}. But nn is an odd number. Therefore, (i,j)=(i,j)(i, j) = (i', j'). Hence, the board is totally non-symmetric.

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 and solution reproduced as published; topic and difficulty added by this site.