Let $k\leq n$ be two positive integers. $n$ points are marked on a line. It is known that for each marked point, the number of marked points at a distance $\leq 1$ from it (including the point itself) is divisible by $k$. Show that $k$ divides $n$ (without remainder).
Problem
Source: 2022 Grosman Mathematical Olympiad P7
Tags: combinatorics, combinatorics unsolved
Phorphyrion
02.12.2022 15:42
Official solution:
First, by dilating the line by a factor of $1-\epsilon$ for small enough $\epsilon>0$, we may assume no two points are at a distance of exactly $1$.
Order the points as $x_1<x_2<\cdots<x_n$. Consider the set of $2n$ numbers consisting of all $x_i$ and all $x_i+1$. Order this set as $p_1<p_2<\cdots<p_{2n}$. Pick indices $a_i,b_i$ for which
\[p_{a_i}=x_i, p_{b_i}=x_i+1\]Then it is easy to see that the number of points at a distance $\leq 1$ from $x_i$ is exactly $b_i-a_i$. Thus by the condition $a_i,b_i$ have the same remainder upon division by $k$. This implies that the list $a_1,\dots,a_n,b_1,\dots,b_n$ contains an even amount of each remainder mod $k$.
Notice that this list is a permutation of $1,2,\dots, 2n$. If $2n$ is not divisible by $k$ then some remainders appear in this list 1 more time than other remainders, contradicting each remainder appearing an even number of times. Furthermore, if $k\nmid n$ but $k\mid 2n$, each remainder has an equal but odd number of appearances in the list, again a contradiction. This finishes the proof.