Problem 1035

Solution. Consider an empty table with 2 rows and $t+m$ columns. Let's look at the fillings of the table that satisfy the following conditions:

- Each cell is filled with either a 1 or a 0;
- The first $t$ cells in the top row are filled with 1;
- If there is a 0 anywhere in the top row, then there is also a 0 directly below it;
- The bottom row contains exactly $m$ ones.

To prove the statement of the problem, we will show that both expressions determine the number of valid fillings.

How can we get a valid filling?

I. Method: In the last $m$ cells of the top row, exactly $k$ cells are filled with 1 (where $0 \leq k \leq m$), and the rest are filled with 0. This can be done in $\binom{m}{k}$ ways as a function of $k$. In this row, there are then exactly $t+k$ ones. The $m$ ones in the bottom row can only be placed under the $t+k$ ones in the top row, and we can choose their positions in $\binom{t+k}{m}$ ways. The remaining cells are filled with 0.

For a given $k$, this results in $\binom{m}{k}\binom{t+k}{m}$ fillings, which in total is

$$\sum_{k=0}^{m}\binom{m}{k}\binom{t+k}{m}$$

valid fillings, which is the expression on the left side of the equation to be proven.

II. Method: Out of the $m$ ones in the bottom row, $k$ of them (where $0 \leq k \leq m$) are placed in the first $t$ columns, which can be done in $\binom{t}{k}$ ways as a function of $k$.

The last $m$ cells of the bottom row contain exactly $m-k$ ones, which can be placed in $\binom{m}{m-k}=\binom{m}{k}$ ways.

The bottom row can be filled in $\binom{t}{k}\binom{m}{k}$ ways as a function of $k$, while the last $m$ cells of the top row are still empty.

Among these, exactly $m-k$ cells have a 1 directly below them in the bottom row, so these $m-k$ cells must also contain 1. The remaining $m-(m-k)=k$ empty cells can be filled freely, in $2^{k}$ ways.

Thus, for a given $k$, there are $\binom{m}{k}\binom{t}{k} \cdot 2^{k}$ fillings, which in total is

$$\sum_{k=0}^{m}\binom{m}{k}\binom{t}{k} \cdot 2^{k}$$

valid fillings. This is the expression on the right side of the equation to be proven.

With this, we have proven the statement of the problem.

Note. A different solution can be found in Hajnal Péter's book "Elementary Combinatorial Problems" (3.17/l, p. 14), and in Lovász László's book "Combinatorial Problems and Exercises" (§1. 43/a, p. 20). Students who only referred to these but did not write out the solution received 0 points according to the rules of the competition.