Prove that we can give a color to each of the numbers $1,2,3,...,2013$ with seven distinct colors (all colors are necessarily used) such that for any distinct numbers $a,b,c$ of the same color, then $2014\nmid abc$ and the remainder when $abc$ is divided by $2014$ is of the same color as $a,b,c$.
Problem
Source: Shortlist OSN Indonesia 2014, N5
Tags: number theory, pigeonhole principle, national olympiad
antonbnt15_Indo
13.05.2017 18:10
Any ideas?
antonbnt15_Indo
10.06.2017 22:14
antonbnt15_Indo wrote: Any ideas?
61plus
11.06.2017 05:01
The prime factorisation of $2014$ is $2\cdot 19\cdot 53$. One can then classify the numbers $1$ to $2013$ by $7$ colours, depending on which of $2,19,53$ each number is divisible by. (So divisible by none, divisble by $2$ only,..., divisble by $19*53$) Quite easy to check that $2014$ does not divide $abc$, and $abc$ belongs to same colour.
antonbnt15_Indo
11.06.2017 16:11
Your solution is incomplete. You also need to prove that the remainder when $abc$ is divided by 2014 is of the same color and it's not so obvious.
Mathfun1111
11.06.2017 16:13
how do you change the hardness difficulty
nmd27082001
11.06.2017 16:29
Let $A_2={0<x<2014:(x,2014)=2}$ $A_{19}={0<x<2014:(x,2014)=19}$ $A_{53}={0<x<2014:(x,2014)=53}$ $A_{38}={0<x<2014:(x,2014)=38}$ $A_{106}={0<x<2014:(x,2014)=106}$ $A_{1007}={0<x<2014:(x,2014)=1007}$ And $C={x:(2014,x)=1}$ So we get that $\cup A_iC=[2013]$ Each set color with 1 color,then we can see it satisfied the problem