A prime number $p$ and a positive integer $n$ are given. Prove that one can colour every one of the numbers $1,2,\ldots,p-1$ using one of the $2n$ colours so that for any $i=2,3,\ldots,n$ the sum of any $i$ numbers of the same colour is not divisible by $p$.
Problem
Source: Poland 73-3-6
Tags: number theory
01.04.2022 02:16
Remark. If $n\ge p$ then this fails if you are allowed to take several equal numbers in a sum (consider the sum of $p$ ones...). If $n<p$ then the problem statement is fine even when equal summands are allowed. Also, this problem was proposed by Swistak, michaj, and me
15.04.2022 06:48
Sol with small hint from timon92: Let S1={1,2,3,...,[p/n]} and S2={1-n,2-n,...,-1,1,2,...,n-2,n-1}, by Thue's lemma, for every a∈{1,2,...,p-1} there exists b∈S1 and c∈S2 such that ac≡b(mod p) Now let A(i)={1/i,2/i,...,[p/n]/i} then every a∈{1,2,...,p-1} belongs to one of A(1),A(2),...,A(n-1),A(-1),A(-2),...,A(1-n) in Fp. Now just partition {1,2,...,p-1) into 2(n-1) sets B(1),B(2),...,B(n-1),B(-1),...,B(1-n) such that B(i) ⊆ A(i) for all i and we are done. In fact we only need 2(n-1) colors.
29.03.2024 16:28
Lemma: let $m \geq 2$ be a positive integer and let $a$ be relatively prime to $m$. Let $X,Y$ be positive integers such that $X,Y \leq m < XY$. Then there exist integers $x,y$ such that $$x \equiv ay \ (\textrm{mod} \ m)$$and $0<|x|<X$ and $0<y<Y$. Proof: consider a set $\mathcal{A}=\left \lbrace x+ay : x \in \left \lbrace 1,2,...,X-1,X \right \rbrace \wedge y \in \left \lbrace 1,2,...,Y-1,Y \right \rbrace \right \rbrace$. This set contains $XY$ elements so, by Pigeonhole Principle, at least two give the same remainder modulo $p$. Let $$x_1+ay_1 \equiv x_2+ay_2 \ (\textrm{mod} \ m)$$and let WLOG $y_1 \geq y_2$. Then we get that $$a(y_1-y_2) \equiv x_2-x_1 \ (\textrm{mod} \ m).$$It's clear that $y_1-y_2 \leq Y-1$ and $|x_2-x_1| \leq X-1$. Moreover $y_1 \neq y_2$ as this would give $x_1 \equiv x_2 \ (\textrm{mod} \ m)$ which is impossible and $m \geq X >X-1 \geq |x_1-x_2|$. Similarly, keeping in mind that $a \perp m$, we get that $y_1 \neq y_2$. Thus numbers $y:=y_1-y_2$, $x:=x_2-x_1$ satisfy the conditions. Solution: It's clear that $p>n$. For the lemma, let's choose $X=n+1, Y=t+1$, where $t$ is the largest such integer that $tn<p$. Then it's obvious that $X,Y \leq p$. On the other hand, $$XY=(t+1)(n+1)>(t+1)n \geq p.$$Consider the set $\mathcal{P}= \left \lbrace 1,2,...,p-1 \right \rbrace$. For every number $a \in \mathcal{P}$, due to the lemma, there exist numbers $x,y$ such that $ay \equiv x \ (\textrm{mod} \ p)$ and $0<y \leq t$, $x \in \left \lbrace -n,-n+1,...,-1,0,1,...,n-1,n \right \rbrace$. Let $T_k$ be a subset of $\mathcal{P}$ containing numbers for which number $x$ from the lemma equals $k$ (in case there are multiple such numbers, choose arbitrarily, for instance the smallest). We constructed subsets $T_{-n},T_{-n+1},...,T_{n-1},T_n$ such that $T_{-n} \sqcup T_{-n+1} \sqcup \cdots \sqcup T_n = \mathcal{P}$. Moreover, for every $1\leq i \leq n$ numbers $m_1,...,m_i$ from set $T_k$ we get that: $$m_1+ \cdots + m_i \equiv k(y_1+\cdots+y_i) \not \equiv 0 (\textrm{mod} \ p)$$because $|k|\leq n<p$ so $p \nmid k$ and $0<y_1+\cdots+y_i < it \leq nt <p$ and so $p \nmid y_1+\cdots+y_i $. Now, it suffices to colour numbers from set $T_{-n}$ with the $1$-st colour, numbers from $T_{-n+1}$ with the $2$-nd and so on with numbers from $T_n$ coloured with the $2n$-th colour.