On a board there are $n$ nails, each two connected by a rope. Each rope is colored in one of $n$ given distinct colors. For each three distinct colors, there exist three nails connected with ropes of these three colors. a) Can $n$ be $6$ ? b) Can $n$ be $7$ ?
Problem
Source: JBMO 2012
Tags: ceiling function, modular arithmetic, combinatorics proposed, combinatorics
27.06.2012 20:27
Each rope participates in precisely $n-2$ triangles. There are $\displaystyle \binom {n-1} {2} = \dfrac {(n-1)(n-2)} {2}$ triplets of distinct colours containing a fixed colour $c$, so one needs at least $\displaystyle \left \lceil \dfrac {(n-1)(n-2)/2} {n-2} \right \rceil = \left \lceil \dfrac {n-1} {2} \right \rceil$ ropes of each colour $c$ of the $n$ colours used. Finally, there are $\displaystyle \binom {n} {2} = \dfrac {n(n-1)} {2}$ ropes in all, so it is needed that $\displaystyle n\left \lceil \dfrac {n-1} {2} \right \rceil \leq \dfrac {n(n-1)} {2}$, henceforth $n$ must be odd. (a) For $n=6$ we thus proved no such colouring is possible. (b) For $n=7$, in order to have such a colouring, one thus needs $3$ ropes of each of the $7$ colours used, accounting for precisely all of the $21$ ropes, and each of the $5$ triangles made with a rope must be tricolour. A model is obtained as follows. Label both the nails and the colours by the elements of $\mathbb{F}_7 = \{0,1,2,3,4,5,6\}$. Assign to rope $ij$ the colour $i+j \pmod{7}$. It is trivial that each triangle $ijk$ (of the $35$ possible) is tricolour (of the $35$ possible combinations of $3$ colours out of $7$). Notice the above holds in general; there is no solution for $n$ even, and a model for $n$ odd is given by assigning to rope $ij$ the colour $i+j \pmod{n}$.
28.06.2012 09:29
A slight generalisation of this problem appeared as Problem 5 in China National Olympiad 2009... http://www.artofproblemsolving.com/Forum/resources.php?c=37&cid=65&year=2009&sid=5c6c4493b9e60b946dcdd4d37ab33025
28.06.2012 09:39
Ha, ha, there is no new thing upon the world. This generalization is exactly that pointed at in the final paragraph of my post. In truth, quite an easy question for China Olympiad.
01.05.2022 04:52
I think the link in #3 is not working it's here
20.05.2023 04:42
a) no There are $\binom {n} {2}$ ropes, note that if we set a colour there will be $\binom {n-1} {2}$ triangles with one side of that colour, on the other hand we have that each rope is in $(n-2)$ triangles(because if we fix a rope, it uses two nails, and any other nail completes the triangle), so by Pigeonhole principle there are at least $\left \lceil \frac {\binom {n-1} {2}} {n-2} \right \rceil $ ropes for the fixed colour, and we can do it for each colour, so we have: $\binom {n} {2} \geq n(\left \lceil \frac {\binom {n-1} {2}} {n-2} \right \rceil)$ this implies that $n$ is odd, in this case we have that $n$ is even