MathDB
Half of the elements in the array are colored in red

Source: Vietnam TST 2002 for the 43th IMO, problem 4

June 26, 2005
floor functioncombinatorics unsolvedcombinatorics

Problem Statement

Let n2n\geq 2 be an integer and consider an array composed of nn rows and 2n2n columns. Half of the elements in the array are colored in red. Prove that for each integer kk, 1kk rows such that the array of size k×2nk\times 2n formed with these kk rows has at least k!(n2k+2)(nk+1)(nk+2)(n1) \frac { k! (n-2k+2) } {(n-k+1)(n-k+2)\cdots (n-1)} columns which contain only red cells.