Problem A. 604. (December 2013)
A. 604. There is given a (2n-1)×(2n+1-1) table with integer entries. Prove that it is possible to delete 2n-1 columns from the table in such a way that in each row of the remaining (2n-1)×2n subtable the sum of entries is even.
(5 pont)
Deadline expired on January 10, 2014.
Solution. Denote by aij the jth entry in the ith row. For arbitrary indices , let
denote the subtable formed by the the j1th, ..., j2nth 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 0
k
2n+1-1,
and 1
v1,...,vk
2n+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 v1,...,vk are all listed among the indices j1,...,j2n. Suppose that there are m different values among v1,...,vk where m=|{v1,...,vk}|
k. We already have m of the indices j1,...,j2n; the remaining 2n-m indices have to be chosen from the 2n+1-1-m unused values. Therefore, the term
appears
times. Hence,
(2) |
To complete the proof we show that is odd for m=0 and even for 1
m
2n-1. This could be done by an easy application of some well-known 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 1m
2n-1, then
The exponent of 2 in 2n-m is less than n, so is even.
Hence, on the right-hand side of (2), every binomial coefficient is even, except for the leading which is odd. Therefore S is odd. This completes the solution.
Statistics:
2 students sent a solution. 0 point: 2 students.
Problems in Mathematics of KöMaL, December 2013