Kvant Math Problem 933
Let the clans be represented by labels.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m06s
Source on kvant.digital
Problem
13 knights from $k$ different clans ($1 \lt k \lt 13$) are seated around a round table. Each holds either a gold or a silver goblet, with exactly $k$ gold goblets in total. King Arthur ordered the knights to simultaneously pass their goblets to their neighbors on the right, then do the same once more, and so on. Prove that at some moment there will be two knights from the same clan holding gold goblets.
A. A. Bolotov
Moscow Mathematical Olympiad
Exploration
Let the clans be represented by labels. At time $t$, after $t$ simultaneous right shifts, the gold goblets occupy a set of $k$ seats obtained from the initial set by rotation through $t$ positions. Thus the process is periodic modulo $13$.
Suppose, seeking a contradiction, that at no moment do two knights of the same clan simultaneously hold gold goblets. Then for every time $t$, the $k$ gold goblets are held by knights belonging to $k$ different clans. Since there are exactly $k$ clans altogether, each clan must then be represented exactly once among the gold holders at every moment.
It is convenient to number the seats by residues modulo $13$. Let $G$ be the set of seats initially containing gold goblets. At time $t$, the gold holders are precisely the knights sitting in seats $G+t$.
For a clan $C$, let $f_C(t)$ be the number of knights of clan $C$ sitting in the seats $G+t$. Under the contradictory assumption, $f_C(t)=1$ for every clan $C$ and every $t$.
The crucial point is to convert these equalities into a counting statement. Fix a clan $C$ containing $m_C$ knights. Summing $f_C(t)$ over all $13$ values of $t$, each knight of clan $C$ is counted exactly $k$ times, because each seat belongs to exactly $k$ of the translates $G+t$. Hence
$$\sum_{t=0}^{12} f_C(t)=m_Ck.$$
But $f_C(t)=1$ for all $t$, so the left side equals $13$. Therefore
$$m_Ck=13.$$
Since $13$ is prime and $1<k<13$, this is impossible.
That appears to be the entire contradiction.
Problem Understanding
We have $13$ knights belonging to $k$ clans, where $1<k<13$. Exactly $k$ gold goblets are present. At each step every goblet moves one seat to the right. We must prove that at some moment two knights from the same clan are simultaneously holding gold goblets.
This is a Type B problem. The statement itself is to be proved.
The core difficulty is to exploit the periodic motion of the goblets. Since the gold positions merely rotate around the table, the problem becomes a question about translates of a fixed $k$-element subset of the $13$ seats. The key idea is to assume that every clan is represented exactly once among the gold holders at all times and derive an impossible divisibility condition.
Proof Architecture
Let the seats be numbered modulo $13$, and let $G$ be the set of seats initially containing gold goblets; then at time $t$ the gold goblets occupy the seats $G+t$.
For each clan $C$, define $f_C(t)$ as the number of knights of clan $C$ occupying seats $G+t$; under the negation of the desired conclusion, $f_C(t)=1$ for all $t$ because the $k$ gold holders must belong to $k$ distinct clans.
Prove that each seat belongs to exactly $k$ translates $G+t$; for a fixed seat $s$, the values of $t$ for which $s\in G+t$ are exactly $s-g$ with $g\in G$.
Deduce that for a clan $C$ with $m_C$ knights,
$$\sum_{t=0}^{12} f_C(t)=m_Ck,$$
because each knight of that clan is counted exactly $k$ times.
Use $f_C(t)=1$ to obtain
$$13=m_Ck.$$
Since $13$ is prime and $1<k<13$, this is impossible.
The lemma most likely to fail under scrutiny is the counting identity $\sum_t f_C(t)=m_Ck$; it requires checking carefully that every knight is counted exactly $k$ times.
Solution
Number the seats around the table by the residues modulo $13$. Let $G$ be the set of seats whose goblets are gold at the initial moment. Since there are exactly $k$ gold goblets,
$$|G|=k.$$
After $t$ rounds of passing to the right, every goblet has moved $t$ seats to the right. Hence the gold goblets occupy precisely the seats
$$G+t={g+t:g\in G},$$
where all arithmetic is modulo $13$.
Assume that the statement of the problem is false. Then at no moment are two gold goblets held by knights of the same clan.
At any moment there are exactly $k$ gold goblets. Since there are exactly $k$ clans altogether, the $k$ knights holding gold goblets must belong to $k$ distinct clans, and therefore each clan is represented exactly once among the gold holders.
Fix a clan $C$, and let $m_C$ be the number of knights belonging to that clan. For each $t\in{0,1,\dots,12}$, let
$$f_C(t)$$
denote the number of knights of clan $C$ sitting in the seats $G+t$.
By the preceding paragraph,
$$f_C(t)=1$$
for every $t$.
Now sum these numbers over all $13$ values of $t$.
Consider a particular seat $s$. The condition $s\in G+t$ is equivalent to
$$s-t\in G.$$
For each choice of $g\in G$, there is exactly one value of $t$, namely
$$t=s-g,$$
for which $s=g+t$. Since $|G|=k$, the seat $s$ belongs to exactly $k$ of the sets $G+t$.
Therefore each knight, regardless of clan, is counted exactly $k$ times in the sum
$$\sum_{t=0}^{12} f_C(t).$$
Since clan $C$ contains $m_C$ knights,
$$\sum_{t=0}^{12} f_C(t)=m_Ck.$$
On the other hand, $f_C(t)=1$ for all $13$ values of $t$, so
$$\sum_{t=0}^{12} f_C(t)=13.$$
Hence
$$m_Ck=13.$$
The number $13$ is prime, while $1<k<13$. Thus $k$ is neither $1$ nor $13$, so $k$ cannot divide $13$. The equality $m_Ck=13$ is impossible.
This contradiction shows that our assumption was false. Consequently, there exists a moment at which two knights from the same clan are holding gold goblets.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the assertion that every clan is represented exactly once among the gold holders under the contradictory assumption. At any moment there are $k$ gold goblets and hence $k$ gold holders. If no two of them come from the same clan, then these $k$ knights belong to $k$ distinct clans. Since the total number of clans is exactly $k$, every clan appears exactly once.
The second delicate step is the counting identity
$$\sum_{t=0}^{12} f_C(t)=m_Ck.$$
Fix a seat $s$. The seat belongs to $G+t$ precisely when $t=s-g$ for some $g\in G$. Different elements of $G$ produce different values of $t$, because arithmetic is modulo $13$. Since $|G|=k$, there are exactly $k$ such values of $t$. Thus each knight is counted exactly $k$ times when all translates $G+t$ are considered, giving the identity.
The third delicate step is the final contradiction. From
$$m_Ck=13$$
one must use the primality of $13$. The only positive divisors of $13$ are $1$ and $13$. Since $1<k<13$, the factor $k$ cannot divide $13$. Hence no integer $m_C$ can satisfy the equation.
Alternative Approaches
The argument may be phrased in terms of averages. Under the contradictory assumption, each clan contributes exactly one gold holder at every time, so over the $13$ moments of a full cycle each clan contributes exactly $13$ clan-occurrences. On the other hand, a clan with $m_C$ knights contributes $m_Ck$ clan-occurrences, because each of its knights occupies a gold position during exactly $k$ moments of the cycle. Equating these counts again yields $m_Ck=13$ and the same contradiction.
Another viewpoint uses convolution on the cyclic group $\mathbb Z_{13}$. Let $1_G$ be the indicator of the gold positions and let $1_C$ be the indicator of the seats occupied by a given clan. The assumption implies that the cyclic convolution $1_G*1_C$ is identically equal to $1$. Summing over the group gives $|G|\cdot|C|=13$, namely $km_C=13$. The contradiction is then immediate from the primality of $13$. The direct counting proof is preferable because it avoids introducing algebraic language and keeps every step combinatorial.