Browse · MathNet
PrintThe Problems of Ukrainian Authors
Ukraine counting and probability
Problem
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 from the first row is written a number , which equals the number of numbers in the first row that are less than and located to the left of . Similarly, the numbers of the third row are obtained with respect to the second row: under every number of the second row is written a number , which equals the number of numbers in the second row that are less than and located to the left of . 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 in the first row is written a number , which equals the number of integers in the first row that are less than and located to the left of . We know that every table has pairwise different second rows. Find the maximum possible number of tables.
Answer: .
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 in the first row is written a number , which equals the number of integers in the first row that are less than and located to the left of . We know that every table has pairwise different second rows. Find the maximum possible number of tables.
Answer: .
Solution
a. 1) If , then the quantity of numbers from the first row smaller than and situated to the left of is the same as the quantity of numbers from the first row smaller than and situated to the left of . As number can't increase this quantity, that's why .
2) If , then the quantity of numbers from the first row smaller than and situated to the left of is less than the quantity of numbers from the first row smaller than and situated to the left of , as this quantity is increased by numbers . That's why and .
3) If , then the quantity of numbers from the first row smaller than and situated to the left of is one less than the quantity of numbers from the first row smaller than and situated to the left of , as this quantity is increased by the number . That's why and .
As we can see, numbers are built the same way. Before finishing, we should note that .
b. Let's denote the first and second row of the table as and . As we know , depends on and . Let's look at some variants.
1) If , then the quantity of numbers from the first row smaller than and situated to the left of is the same as the quantity of numbers from the first row smaller than and situated to the left of . As number can't increase this quantity, that's why .
2) If , then the quantity of numbers from the first row smaller than and situated to the left of is less than the quantity of numbers from the first row smaller than and situated to the left of , as this quantity is increased by numbers . That's why and .
Fig. 19
That's why at each step there exist two different possibilities for the next element, which means that there are exactly such tables.
2) If , then the quantity of numbers from the first row smaller than and situated to the left of is less than the quantity of numbers from the first row smaller than and situated to the left of , as this quantity is increased by numbers . That's why and .
3) If , then the quantity of numbers from the first row smaller than and situated to the left of is one less than the quantity of numbers from the first row smaller than and situated to the left of , as this quantity is increased by the number . That's why and .
As we can see, numbers are built the same way. Before finishing, we should note that .
b. Let's denote the first and second row of the table as and . As we know , depends on and . Let's look at some variants.
1) If , then the quantity of numbers from the first row smaller than and situated to the left of is the same as the quantity of numbers from the first row smaller than and situated to the left of . As number can't increase this quantity, that's why .
2) If , then the quantity of numbers from the first row smaller than and situated to the left of is less than the quantity of numbers from the first row smaller than and situated to the left of , as this quantity is increased by numbers . That's why and .
That's why at each step there exist two different possibilities for the next element, which means that there are exactly such tables.
Final answer
2^{2007}
Techniques
Invariants / monovariantsRecursion, bijection