Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# 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 0k2n+1-1, and 1v1,...,vk2n+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 1m2n-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 1m2n-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