Kirill has $n{}$ identical footballs and two infinite rows of baskets, each numbered with consecutive natural numbers. In one row the baskets are red, in the other they are blue. Kirill puts all the balls into baskets so that the number of balls in the either row of baskets does not increase. Denote by $A{}$ the number of ways to arrange the balls so that the first blue basket contains more balls than any red one, and by $B{}$ the number of arrangements so that the number of some blue basket corresponds with the number of balls in it. Prove that $A = B$.
Problem
Source: Russian TST 2018, Day 9 P3 (Group NG)
Tags: combinatorics
08.11.2024 12:34
Seems to be not answered for long enough, so let me post a solution. If $\mathcal{A}$, $\mathcal{B}$ denote the arrangements enumerated by $A$ and $B$, respectively, we construct a bijection between $\mathcal{A}\setminus \mathcal{B}$ and $\mathcal{B}\setminus \mathcal{A}$. Let the red row contain $r_1\geqslant r_2\geqslant \ldots$ balls, the blue row $b_1\geqslant b_2\geqslant \ldots$ balls. Then $\mathcal{A}$ is the set of arrangements for which $b_1>r_1$, and $\mathcal{B}$ is the set of arrangements for which $b_i=i$ for certain $i$. Take an arrangement in $\mathcal{A}\setminus \mathcal{B}$: then, $b_1>r_1$ and $b_i\ne i$ for all $i$. The last condition means that for some $j$, we have $b_j>j$, $b_{j+1}<j+1$. Replace $b$'s to $b_2-1\geqslant \ldots b_j-1\geqslant j\geqslant b_{j+1}\ldots$ and $r$'s to $b_1-1\geqslant r_1\geqslant r_2\geqslant \ldots$. The new arrangement belongs to $\mathcal{B}$ (since the $j$-th blue basket contains $j$ balls) and does not belong to $\mathcal{A}$ (since the first red basket contains $b_1-1\geqslant b_2-1$ balls). The constructed map from $\mathcal{A}\setminus \mathcal{B}$ to $\mathcal{B}\setminus \mathcal{A}$ is indeed a bijection, the inverse maps takes $j$ for which $b_j=j$, removes this basket, increases by 1 the number of balls in first $j-1$ blue baskets and in the largest red basket, and moves this largest red basket to the blue row.