MathDB

6

Part of 2016 All-Russian Olympiad

Problems(2)

Partition of rectangle

Source: 2016 All-Russian Olympiad,Problem 9.6

6/7/2016
A square is partitioned in n2≥4n^2\geq 4 rectanles using 2(n−1)2(n-1) lines,n−1n-1 of which,are parallel to the one side of the square,n−1n-1 are parallel to the other side.Prove that we can choose 2n2n rectangles of the partition,such that,for each two of them,we can place the one inside the other (possibly with rotation).
rectanglecombinatorics
Aviaroutes in country

Source: All russian olympiad 2016,Day2,grade 11,P6

5/5/2016
There are n>1n>1 cities in the country, some pairs of cities linked two-way through straight flight. For every pair of cities there is exactly one aviaroute (can have interchanges). Major of every city X counted amount of such numberings of all cities from 11 to nn , such that on every aviaroute with the beginning in X, numbers of cities are in ascending order. Every major, except one, noticed that results of counting are multiple of 20162016. Prove, that result of last major is multiple of 20162016 too.
graph theorynumber theorycombinatorics