A. 604. There is given a (2^{n}1)×(2^{n+1}1) table with integer entries. Prove that it is possible to delete 2^{n}1 columns from the table in such a way that in each row of the remaining (2^{n}1)×2^{n} subtable the sum of entries is even.
(5 points)
Deadline expired on 10 January 2014.
Solution. Denote by a_{ij} the jth entry in the ith row. For arbitrary indices , let denote the subtable formed by the the j_{1}th, ..., j_{2n}th columns, and define
In the ith row of , the sum of entries is even if and only if is odd; therefore, has the required property if and only if is odd.
Consider the sum
 (1) 
We show that S is always odd. This proves the existence of an odd value of and the existence of the desired subtable.
Expanding the parentheses in (1), we can see that S is the sum of terms of the form where 0k2^{n+1}1, and 1v_{1},...,v_{k}2^{n+1}1. (In case of k=0 the product is empty and it is considered as 1.)
Now count the occurences of the term . This term appears exactly once in the product if and only if the values v_{1},...,v_{k} are all listed among the indices j_{1},...,j_{2n}. Suppose that there are m different values among v_{1},...,v_{k} where m={v_{1},...,v_{k}}k. We already have m of the indices j_{1},...,j_{2n}; the remaining 2^{n}m indices have to be chosen from the 2^{n+1}1m unused values. Therefore, the term appears times. Hence,
 (2) 
To complete the proof we show that is odd for m=0 and even for 1m2^{n}1. This could be done by an easy application of some wellknown properties of binomial coefficient, e.g. Lucas' Lemma; here we outline a direct proof instead. For m=0 we have
In every fraction in this product, the exponent of 2 is the same in the numerator as in the denominator.
If 1m2^{n}1, then
The exponent of 2 in 2^{n}m is less than n, so is even.
Hence, on the righthand side of (2), every binomial coefficient is even, except for the leading which is odd. Therefore S is odd. This completes the solution.
Statistics on problem A. 604.  2 students sent a solution.  
0 point:  2 students. 


Problems in Mathematics of KöMaL, December 2013
