Skip to main content
OlympiadHQ

Browse · MathNet

Print

Iranian Mathematical Olympiad

Iran counting and probability

Problem

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 table centered at the origin be a permutation of numbers We proceed the filling of the table inductively. Suppose that in step , the 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 . Now, consider table centered at the origin. Fill this table as follows.
...
table from the k-th step...
...
...
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. ■
Final answer
Yes

Techniques

Induction / smoothingRecursion, bijectionAlgorithms