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 1\le j_1<\ldots<j_{2^n}\le 2^{n+1}-1, let T(j_1,\ldots,j_{2^n}) denote the subtable formed by the the j1th, ..., j2nth columns, and define


f(j_1,\ldots,j_{2^n}) =
\prod_{i=1}^{2^n-1}\left(1+\sum_{\ell=1}^{2^n}a_{i,j_\ell}\right).

In the ith row of T(j_1,\ldots,j_{2^n}), the sum of entries is even if and only if 1+\sum\limits_{\ell=1}^{2^n}a_{i,j_\ell} is odd; therefore, T(j_1,\ldots,j_{2^n}) has the required property if and only if f(j_1,\ldots,j_{2^n}) is odd.

Consider the sum


S = \sum_{1\le j_1<\ldots<j_{2^n}\le 2^{n+1}-1} f(j_1,\ldots,j_{2^n}) =
\sum_{1\le j_1<\ldots<j_{2^n}\le 2^{n+1}-1} 
\prod_{i=1}^{2^n-1}\left(1+\sum_{\ell=1}^{2^n}a_{i,j_\ell}\right).
(1)

We show that S is always odd. This proves the existence of an odd value of f(j_1,\ldots,j_{2^n}) 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 a_{u_1,v_1}\ldots a_{u_k,v_k} where 0\lek\le2n+1-1, 1\le u_1<\ldots<u_k\le 2^n-1 and 1\lev1,...,vk\le2n+1-1. (In case of k=0 the product is empty and it is considered as 1.)

Now count the occurences of the term a_{u_1,v_1}\ldots
a_{u_k,v_k}. This term appears exactly once in the product \prod\limits_{i=1}^{2^n-1}\left(1+\sum\limits_{\ell=1}^{2^n}a_{i,j_\ell}\right) 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}|\lek. 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 a_{u_1,v_1}\ldots a_{u_k,v_k} appears \binom{2^{n+1}-1-m}{2^n-m} times. Hence,


S = \binom{2^{n+1}-1}{2^n} + 
\,\, \sum_{k=1}^{2^n-1}\sum_{1\le u_1<\ldots<u_k\le 2^n-1}
\,\, \sum_{1\le v_1,\ldots,v_k\le 2^{n+1}-1}
\binom{2^{n+1}-1-|\{v_1,\dots,v_k\}|}{2^n-|\{v_1,\dots,v_k\}|}
a_{u_1,v_1}\ldots a_{u_k,v_k}.
(2)

To complete the proof we show that \binom{2^{n+1}-1-m}{2^n-m} is odd for m=0 and even for 1\lem\le2n-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


\binom{2^{n+1}-1-m}{2^n-m} = \binom{2^{n+1}-1}{2^n} = 
\frac{2^{n+1}-1}{1} \cdot \frac{2^{n+1}-2}{2} \cdot \ldots \cdot
\frac{2^n}{2^n}.

In every fraction in this product, the exponent of 2 is the same in the numerator as in the denominator.

If 1\lem\le2n-1, then


\binom{2^{n+1}-1-m}{2^n-m} =
\frac{2^n}{2^n-m} \cdot \binom{2^{n+1}-m}{2^n-m}.

The exponent of 2 in 2n-m is less than n, so \frac{2^n}{2^n-m} \cdot
\binom{2^{n+1}-m}{2^n-m} is even.

Hence, on the right-hand side of (2), every binomial coefficient is even, except for the leading \binom{2^{n+1}-1}{2^n-1} 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