Consider $n$ children in a playground, where $n\ge 2$. Every child has a coloured hat, and every pair of children is joined by a coloured ribbon. For every child, the colour of each ribbon held is different, and also different from the colour of that child’s hat. What is the minimum number of colours that needs to be used?
Problem
Source: Pan African Olympiad 2009
Tags: combinatorics proposed, combinatorics
socrates
09.11.2016 21:47
Up! Up!
laegolas
14.11.2016 20:11
The minimum is $n$. Same as here: http://artofproblemsolving.com/community/c6t309f6h1337389s2_graph_theory
neba42
26.01.2018 17:55
i think is n+1 !
ThE-dArK-lOrD
26.01.2018 20:51
The answer is $n$. If $n$ is odd, use the same method here. If $n$ is even, color every hats by the $n^{th}$ color. Given regular $(n-1)$-gon and the center of circle circumscribed that polygon. Let these $n$ points represent each child. Let the vertices of the polygon are $A_1,A_2,...,A_{n-1}$ and the center is $O$. Color ribbon connected two children by the $i^{th}$ color iff segment joining two points represent those children is $OA_i$ or perpendicular to $OA_i$.
neba42
28.01.2018 14:02
excuse me my translation was bad so I did another think