Browse · MathNet
PrintUkrainian Mathematical Olympiad
Ukraine counting and probability
Problem
Is it possible to paint each cell of an table with one of 16 colors so that for each two colors there are two cells painted with these colors and having a common side?
Solution
In the table, there are 112 unit segments that separate its neighboring cells. But from 16 given colors, one can form 120 pairs of colors, and for each of these pairs, there must be two neighboring cells, which is impossible.
Answer: It is not possible.
Answer: It is not possible.
Final answer
It is not possible.
Techniques
Pigeonhole principleColoring schemes, extremal arguments