Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /84 of 270

Iranian Mathematical Olympiad

Combinatorics Difficulty 6.2 National Olympiad Prove it Iran

Is it possible to write a permutation of positive integers on the cells of an infinite table (infinite from all sides) such that the sequence of numbers in each column from bottom to top and also in each row from left to right be increasing?

Solution

The answer is yes. First, we choose a cell as origin and fill it with zero, then we fill the table in a way that the numbers in the cells of (2k+1)×(2k+1)(2k+1) \times (2k+1) table centered at the origin be a permutation of numbers
(−2k2−2k,−2k2−2k+1,…,0,…,2k2+2k−1,2k2+2k), (-2k^2 - 2k, -2k^2 - 2k + 1, \dots, 0, \dots, 2k^2 + 2k - 1, 2k^2 + 2k),
We proceed the filling of the table inductively. Suppose that in step k≥0k \ge 0, the (2k+1)×(2k+1)(2k+1) \times (2k+1) table centered at the origin is filled with the before-mentioned numbers such that the sequence of numbers in each row and in each column is increasing. Putting m=2k2+2km = 2k^2+2k. Now, consider (2k+3)×(2k+3)(2k+3) \times (2k+3) table centered at the origin. Fill this table as follows.

−(m+4k+4)-(m + 4k + 4)−(m+4k+3)-(m + 4k + 3)...−(m+2k+3)-(m + 2k + 3)m+1m + 1
−(m+2k+2)-(m + 2k + 2)m+2m + 2
−(m+2k+1)-(m + 2k + 1)(2k+1)×(2k+1)(2k + 1) \times (2k + 1) table from the k-th step...
...m+2k+1m + 2k + 1
−(m+2)-(m + 2)m+2k+2m + 2k + 2
−(m+1)-(m + 1)m+2k+3m + 2k + 3...m+4k+3m + 4k + 3m+4k+4m + 4k + 4

It can be easily verified that the columns and rows of this table form increasing sequences. So it is clear that with this algorithm the table will be filled with a permutation of integers and has the desired properties. ■

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.