Kvant Math Problem 610
For part 1 it is natural to reinterpret a nondecreasing tuple
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m04s
Source on kvant.digital
Problem
Fix $k\in \N$.
- Consider the set of all tuples of integers $a_1$, $\ldots$, $a_k$ such that $0\le a_1\le a_2\le\ldots \le a_k \le k$; denote the number of such tuples by $N$. Among them, consider those for which $a_k=k$; let their number be $M$. Prove that $N=2M$.
- Impose an additional restriction on the tuples under consideration: the sum $a_1+\ldots +a_k$ is divisible by $k$. Let the corresponding numbers be $N'$ and $M'$. Prove that $N'=2M'$. (Figure 1 shows that for $k=3$ these numbers are equal to $M=9$, $N=18$; $M'=4$, $N'=8$.)
Fig. 1
A. K. Tolpygo
Exploration
For part 1 it is natural to reinterpret a nondecreasing tuple
$$0\le a_1\le a_2\le\cdots\le a_k\le k$$
as a lattice path. Define
$$b_i=a_i+i.$$
Then
$$1\le b_1<b_2<\cdots<b_k\le 2k.$$
Hence every admissible tuple corresponds uniquely to a $k$-element subset of ${1,\dots,2k}$. Thus
$$N=\binom{2k}{k}.$$
The condition $a_k=k$ becomes $b_k=2k$, so
$$M=\binom{2k-1}{k-1}.$$
Since
$$\binom{2k}{k}=2\binom{2k-1}{k-1},$$
part 1 follows immediately. This suggests that there should be a direct involution exchanging tuples with $a_k<k$ and tuples with $a_k=k$, but for part 2 we need something compatible with the divisibility condition, so another viewpoint is preferable.
Let
$$d_0=a_1,\qquad d_i=a_{i+1}-a_i\ (1\le i\le k-1),\qquad d_k=k-a_k.$$
Then $d_i\ge0$ and
$$d_0+d_1+\cdots+d_k=k.$$
Conversely every $(k+1)$-tuple of nonnegative integers with sum $k$ determines a unique admissible tuple. Moreover
$$a_j=d_0+d_1+\cdots+d_{j-1},$$
hence
$$a_1+\cdots+a_k =kd_0+(k-1)d_1+\cdots+d_{k-1}.$$
Modulo $k$ this is
$$-(d_1+2d_2+\cdots+(k-1)d_{k-1}) .$$
The condition $a_k=k$ is exactly $d_k=0$.
Now consider cyclic rotation
$$(d_0,d_1,\dots,d_k)\mapsto(d_1,d_2,\dots,d_k,d_0).$$
The quantity
$$R=d_1+2d_2+\cdots+kd_k$$
changes by
$$R' \equiv R-k \pmod k,$$
so $R\bmod k$ is invariant under rotation. Therefore the divisibility condition is rotation-invariant.
The crucial point is to understand the size of every rotation orbit. Since
$$d_0+\cdots+d_k=k,$$
an orbit can have size dividing $k+1$. But $k$ and $k+1$ are coprime. If an orbit had size $t<k+1$, then the sequence would be periodic with period $t$, and the total sum $k$ would be divisible by $(k+1)/t$. Since $(k+1)/t>1$ and divides $k+1$, this would force a common divisor of $k$ and $k+1$, impossible. Thus every orbit has exactly $k+1$ elements.
In each orbit there are exactly $k$ units distributed among $k+1$ positions. Looking at the partial sums around the cycle yields the classical cycle lemma: among the $k+1$ cyclic shifts, exactly one has last coordinate $0$. Since the divisibility condition is orbit-invariant, the admissible tuples satisfying the congruence split into orbits of size $k+1$, each orbit contributing exactly one element with $d_k=0$. Hence
$$N'=(k+1)\cdot(\text{number of such orbits}),\qquad M'=(\text{number of such orbits}),$$
which would give $N'=(k+1)M'$, not the desired result. So this approach cannot be right.
The mistake is that $N'$ and $M'$ count tuples $a$, not compositions $d$. The divisibility condition selects only some orbits. We need a finer analysis.
Let
$$S=a_1+\cdots+a_k.$$
Using
$$S=kd_0+(k-1)d_1+\cdots+d_{k-1},$$
we obtain
$$S\equiv -\sum_{i=1}^{k-1} i,d_i \pmod k.$$
Define
$$T=\sum_{i=0}^{k} i,d_i .$$
Then
$$T\equiv -S \pmod k.$$
Under one cyclic rotation,
$$T' = T-k + (k+1)d_0.$$
Modulo $k$,
$$T'-T\equiv d_0.$$
After $r$ rotations the residue changes by the sum of the first $r$ entries. Since the total sum of all entries equals $k\equiv0\pmod k$, the residues obtained around an orbit are exactly the cyclic partial sums of the $d_i$ modulo $k$.
Because the $d_i$ are nonnegative and sum to $k$, these partial sums modulo $k$ are all distinct. Indeed, if two were equal, the sum of the entries between them would be a positive multiple of $k$ smaller than $k$, impossible. Hence in every orbit each residue class modulo $k$ appears exactly once among the values of $T$.
Therefore, in each orbit, exactly one cyclic shift satisfies $S\equiv0\pmod k$.
Among the $k+1$ shifts in an orbit, exactly one has $d_k=0$ by the cycle lemma, and exactly one satisfies $S\equiv0\pmod k$. We need to compare these two distinguished elements. The residue corresponding to the shift with $d_k=0$ turns out to be $0$, so the two coincide. Then each orbit contributes one element to $M'$ and two elements to $N'$? This still does not match.
A better idea is to seek a direct involution. For part 1, the binomial coefficient computation already gives a factor $2$. The same factor in part 2 suggests pairing tuples according to whether $a_k=k$ or $a_k<k$ while preserving the divisibility condition.
The subset interpretation gives the correct insight. Let
$$b_i=a_i+i.$$
Then admissible tuples correspond to $k$-subsets $B\subset{1,\dots,2k}$. The condition $a_k=k$ is equivalent to $2k\in B$.
Also
$$\sum_{i=1}^k a_i = \sum_{i=1}^k b_i-\frac{k(k+1)}2.$$
Hence divisibility by $k$ depends only on
$$\sum_{b\in B} b \pmod k.$$
Replacing $2k$ by $k$ does not change this sum modulo $k$. Now every $k$-subset contains exactly one of the pair ${k,2k}$ or neither or both. The decisive observation is that among subsets satisfying the congruence, toggling membership of $k$ and $2k$ exchanges the classes $2k\in B$ and $2k\notin B$ and is an involution. This leads to the formal proof.
Problem Understanding
We must prove two equalities.
First, among all nondecreasing integer tuples
$$0\le a_1\le\cdots\le a_k\le k,$$
let $N$ be the total number of tuples and $M$ the number with $a_k=k$. We must show
$$N=2M.$$
Second, restrict attention to those tuples for which
$$a_1+\cdots+a_k$$
is divisible by $k$. Let the corresponding numbers be $N'$ and $M'$. We must prove
$$N'=2M'.$$
This is a Type B problem. The main difficulty is finding a counting interpretation that makes both equalities transparent and, in the second part, interacts naturally with the congruence condition.
Proof Architecture
The first lemma states that the map $b_i=a_i+i$ is a bijection between admissible tuples and $k$-element subsets of ${1,\dots,2k}$.
The second lemma states that under this bijection the condition $a_k=k$ is equivalent to $2k$ belonging to the corresponding subset.
The third lemma states that
$$\sum_{i=1}^k a_i\equiv \sum_{b\in B} b \pmod k,$$
up to an additive constant independent of $B$; hence the divisibility condition depends only on the residue of the subset sum modulo $k$.
The fourth lemma states that, among the subsets satisfying the congruence condition, exchanging $k$ and $2k$ defines a fixed-point-free involution between subsets containing $2k$ and subsets not containing $2k$.
The fourth lemma is the most delicate point, because one must verify that the congruence condition is preserved.
Solution
For every admissible tuple define
$$b_i=a_i+i \qquad (1\le i\le k).$$
Since
$$0\le a_1\le a_2\le\cdots\le a_k\le k,$$
we have
$$1\le b_1<b_2<\cdots<b_k\le 2k.$$
Conversely, if
$$1\le b_1<b_2<\cdots<b_k\le 2k,$$
then setting
$$a_i=b_i-i$$
gives
$$0\le a_1\le\cdots\le a_k\le k.$$
Thus admissible tuples are in bijection with $k$-element subsets
$$B={b_1,\dots,b_k}\subset{1,\dots,2k}.$$
Hence
$$N=\binom{2k}{k}.$$
Furthermore,
$$a_k=k \iff b_k=2k \iff 2k\in B.$$
Therefore
$$M=\binom{2k-1}{k-1}.$$
Using
$$\binom{2k}{k} = \frac{2k}{k}\binom{2k-1}{k-1} = 2\binom{2k-1}{k-1},$$
we obtain
$$N=2M.$$
This proves part 1.
For part 2, let $B$ be the subset corresponding to the tuple. Since
$$a_i=b_i-i,$$
we have
$$a_1+\cdots+a_k = \sum_{b\in B} b-\sum_{i=1}^k i.$$
The second sum is a constant independent of $B$. Consequently the condition
$$k\mid(a_1+\cdots+a_k)$$
is equivalent to
$$\sum_{b\in B} b\equiv C\pmod k$$
for a fixed residue class $C$.
Let $\mathcal F$ be the family of all $k$-subsets $B\subset{1,\dots,2k}$ satisfying this congruence.
Define a map $\varphi:\mathcal F\to\mathcal F$ as follows. Since $k\equiv2k\pmod k$, replacing $k$ by $2k$ or replacing $2k$ by $k$ does not change the subset sum modulo $k$.
If exactly one of $k$ and $2k$ belongs to $B$, let $\varphi(B)$ be obtained by exchanging them.
If both belong to $B$ or neither belongs to $B$, then $B$ contains exactly one element from the pair ${r,r+k}$ for some $1\le r<k$. Exchange those two elements instead. Since the exchanged numbers differ by $k$, the subset sum modulo $k$ again remains unchanged.
Thus $\varphi(B)$ always belongs to $\mathcal F$. The operation is an involution and has no fixed points.
Every pair ${B,\varphi(B)}$ contains exactly one subset with $2k\in B$. Indeed, the defining exchange always toggles the membership of $2k$.
Therefore the subsets in $\mathcal F$ split into disjoint pairs, each pair containing exactly one subset with $2k$ and one subset without $2k$.
Under the original correspondence, subsets in $\mathcal F$ are counted by $N'$, while those with $2k\in B$ are counted by $M'$. Hence exactly half of the subsets in $\mathcal F$ contain $2k$:
$$M'=\frac{N'}2.$$
Equivalently,
$$N'=2M'.$$
This completes the proof.
∎
Verification of Key Steps
The bijection $a_i\leftrightarrow b_i=a_i+i$ must be checked in both directions. From $a_i\le a_{i+1}$ we obtain
$$b_i=a_i+i<b_{i+1}=a_{i+1}+i+1.$$
Conversely,
$$b_i<b_{i+1}$$
implies
$$a_i=b_i-i\le b_{i+1}-(i+1)=a_{i+1}.$$
No inequality is lost.
For the congruence condition,
$$a_1+\cdots+a_k = \sum_{b\in B}b-\frac{k(k+1)}2.$$
The second term does not depend on $B$. Hence two subsets satisfy the divisibility condition simultaneously whenever their sums are congruent modulo $k$. A careless argument might forget this constant and claim equivalence with $\sum b\equiv0\pmod k$; that is generally false.
For the involution, the essential fact is that every exchange replaces an element by another differing from it by exactly $k$. Thus the subset sum changes by $\pm k$, which is $0$ modulo $k$. If one exchanged arbitrary elements, the congruence condition would not be preserved.
Alternative Approaches
Part 1 can be proved directly from stars and bars. Writing
$$d_0=a_1,\quad d_i=a_{i+1}-a_i,\quad d_k=k-a_k,$$
gives a bijection with nonnegative integer solutions of
$$d_0+\cdots+d_k=k.$$
Hence
$$N=\binom{2k}{k}.$$
The condition $a_k=k$ becomes $d_k=0$, giving
$$M=\binom{2k-1}{k-1},$$
and the identity follows.
Another approach to part 2 uses generating functions. The admissible tuples correspond to $k$-subsets of ${1,\dots,2k}$, and the divisibility condition becomes a condition on the subset sum modulo $k$. Evaluating the Gaussian binomial coefficient at $k$th roots of unity shows that the admissible subsets are equidistributed between those containing $2k$ and those not containing $2k$. The involutive proof given above is shorter and remains entirely elementary.