Competition problem — Combinatorics

Library / /33 of 39

Combinatorics Difficulty 6.7 National olympiad Prove it Ukraine

a) Let's look at a table of 3 rows and 2008 columns. In the first row, a random integer is written in each cell of the table, in a non-decreasing order. The numbers of the second row are obtained in the following way: under every number $A$ from the first row is written a number $B$ , which equals the number of numbers in the first row that are less than $A$ and located to the left of $A$ . Similarly, the numbers of the third row are obtained with respect to the second row: under every number $C$ of the second row is written a number $D$ , which equals the number of numbers in the second row that are less than $C$ and located to the left of $C$ . Prove that the second and third row of this table are filled equally.

b) We have tables that consist of 2 rows and 2008 columns and are built in such a way that in every table, in the first row, random integers are written (in every cell we have exactly one number) in a non-decreasing order. The numbers of the other row are obtained in the way that under every number $A$ in the first row is written a number $B$ , which equals the number of integers in the first row that are less than $A$ and located to the left of $A$ . We know that every table has pairwise different second rows. Find the maximum possible number of tables.

Answer: $2^{2007}$ .

Solution

a.
1) If $A_{i+1} = A_i$ , then the quantity of numbers from the first row smaller than $A_i$ and situated to the left of $A_i$ is the same as the quantity of numbers from the first row smaller than $A_{i+1}$ and situated to the left of $A_{i+1}$ . As number $A_i$ can't increase this quantity, that's why $B_{i+1} = B_i$ .

2) If $A_{i+1} > A_i = A_{i-1} = \dots = A_{i-k+1}$ , then the quantity of numbers from the first row smaller than $A_i$ and situated to the left of $A_i$ is $k$ less than the quantity of numbers from the first row smaller than $A_{i+1}$ and situated to the left of $A_{i+1}$ , as this quantity is increased by $k$ numbers $A_{i-k+1}, \dots, A_i$ . That's why $B_{i+1} = B_i + k$ and $B_{i+1} > B_i = B_{i-1} = \dots = B_{i-k+1}$ .

3) If $A_{i+1} > A_i > A_{i-1}$ , then the quantity of numbers from the first row smaller than $A_i$ and situated to the left of $A_i$ is one less than the quantity of numbers from the first row smaller than $A_{i+1}$ and situated to the left of $A_{i+1}$ , as this quantity is increased by the number $A_i$ . That's why $B_{i+1} = B_i + 1$ and $B_{i+1} = B_i > B_{i-1}$ .

As we can see, numbers $C_i$ are built the same way. Before finishing, we should note that $B_1 = C_1 = 0$ .

b.
Let's denote the first and second row of the table as $A_1, \dots, A_{2008}$ and $B_1, \dots, B_{2008}$ . As we know $B_1, \dots, B_i$ , $B_{i+1}$ depends on $A_i$ and $A_{i+1}$ . Let's look at some variants.

1) If $A_{i+1} = A_i$ , then the quantity of numbers from the first row smaller than $A_i$ and situated to the left of $A_i$ is the same as the quantity of numbers from the first row smaller than $A_{i+1}$ and situated to the left of $A_{i+1}$ . As number $A_i$ can't increase this quantity, that's why $B_{i+1} = B_i$ .

| $A_i$ | $A_{i+1}$ |
|-------|-----------|
| $B_i$ | $B_{i+1}$ |
| $C_i$ | $C_{i+1}$ |

Fig. 19

That's why at each step there exist two different possibilities for the next element, which means that there are exactly $2^{2007}$ such tables.

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.