Maths Olympiad Prep

Library / /5 of 11

Combinatorics Difficulty 8.1 Shortlist Prove it Bulgaria

Problem:

In the cells of a square table the numbers 11, 00 or 1-1 are written in such a way that there is exactly one 11 and exactly one 1-1 in every row and in every column. Is it always possible to obtain the opposite table by rearranging the rows and the columns of the initial table? (Two tables are called opposite if all the sums of the numbers in the corresponding cells equal 00.)

Solution

Solution:

We shall prove that one can obtain the opposite table by rearranging the rows and columns of the initial table. Denote the columns from left to right and the rows from up to down by 1,2,,n1,2, \ldots, n. Denote by aija_{ij} the number written in the ii-th row and jj-th column.

Exchanging rows and columns one obtains: a11=1a_{11}=1, a12=1a_{12}=-1, a22=1a_{22}=1, a23=1a_{23}=-1 (when a21=1a_{21}=-1 the assertion follows by induction using 2×22 \times 2 and (n1)×(n2)(n-1) \times (n-2) tables), a33=1a_{33}=1, a34=1a_{34}=-1 (if a31=1a_{31}=-1, the assertion follows by induction using 3×33 \times 3 and (n3)×(n3)(n-3) \times (n-3) tables) and so on.

It remains to prove the assertion for the table

1-100\ldots00
01-10\ldots00
001-1\ldots00
\ldots\ldots\ldots\ldots\ldots\ldots\ldots
\ldots\ldots\ldots\ldots\ldots\ldots\ldots
\ldots\ldots\ldots\ldots\ldots1-1
-1000\ldots01

Proceeding in the same way one obtains from the initial table the following one

(B)(B)

-1100\ldots00
0-110\ldots00
00-11\ldots00
\ldots\ldots\ldots\ldots\ldots\ldots\ldots
\ldots\ldots\ldots\ldots\ldots\ldots\ldots
\ldots\ldots\ldots\ldots\ldots-11
1000\ldots0-1

Now applying the same moves for obtaining the table BB from the table AA but in reverse order one obtains the opposite of the initial table.

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.