There are $169$ non-zero digits written around a circle. Prove that they can be split into $14$ non-empty blocks of consecutive digits so that among the $14$ natural numbers formed by the digits in those blocks, at least $13$ of them are divisible by $13$ (the digits in each block are read in clockwise direction).
Problem
Source: 239 MO 2024 J3
Tags: number theory, combinatorics
04.08.2024 00:47
Label the digits on the circle $d_1,d_2,\dots,d_{169}$ in a counter-clockwise matter. For all $i$, $1\leq i \leq 169$ define an integer $S_i$, $0\leq S_i\leq 12$ such that $$S_i\equiv \overline{d_i \dots d_2 d_1}\pmod{13}$$Consider the case were $S_i$ are equally distributed amongst the $13$ residues for any starting choice of $d_1$. Notice that shifting the indices by one ($d_{169}\mapsto d_1$), will result in the new $S_i$, $S_i'$, to become equivalent to $10S_{i-1}+d_{169}$. If the $S_i$ are still equally distributed amongst the residues then we must have that $$10(\overline{d_{169}\dots d_2 d_1})+d_{169}\equiv d_{169}\iff \overline{d_{169}\dots d_2 d_1}\equiv 0 \pmod{13}$$If we continue in this manner, starting anywhere and reading clockwise will result in a multiple of $13$. Thus we have $$\overline{d_{168}\dots d_1 d_{169}}\equiv \overline{d_{169}\dots d_2 d_1}\equiv 0 \pmod{13}$$Let $x=\overline{d_{168}\dots d_2 d_1}$. Then $10x+d_{169}\equiv d_{169}\cdot 10^{168}+x\equiv d_{169}+x\equiv 0\pmod{13}$. This would mean $d_{169}=0$, which is impossible. Thus we can assume the $S_i$ are not equally distributed amongst the $13$ residues for some choice of $d_1$. Thus there exists $i_1<i_2<\dots<i_{14}$ such that $S_{i_1}=S_{i_2}=\dots=S_{i_{14}}$. Then we have that all $13$ adjacent blocks $$\overline{d_{i_{j+1}}\dots d_{i_j+2}d_{i_j+1}}$$are divisible by $13$, so we are done.