# Problem A. 604. (December 2013)

**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 pont)

**Deadline expired on January 10, 2014.**

**Solution. **Denote by *a*_{ij} the *j*th entry in the *i*th row. For arbitrary indices , let denote the subtable formed by the the *j*_{1}th, ..., *j*_{2n}th columns, and define

In the *i*th 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*2^{n+1}-1, and 1*v*_{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}-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*2^{n}-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 1*m*2^{n}-1, then

The exponent of 2 in 2^{n}-*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