There is a socket which has $6$ holes on the vertices of a regular hexagon. These holes are numbered $1, 2, \dots , 6$. Prove that there exists such a plug with $6$ prongs numbered such that no matter how you plug it into the socket, one prong will always go into a hole with the same number.
This looked like a pigeonhole principle problem, so I started off by finding the pigeonholes. I couldn't get very far, however. I tried coloring the socket in various ways, coloring every alternate hole black and the others white and tried to construct a proof, but to no avail.
Ok so in the first place: any prong can only coincide with a number in one orientation. Thats because each prong has one unique number and the hole it goes into is different for each orientation.
Suppose that for a given orientation there are two prongs that coincide. Then these two prongs wont coincide in any other orientation. Therefore the remaining 4 unused prongs would need to fit in 5 orientations. But each one can only fit in 1. So every orientation only has one coinciding prong and hole.
The prongs have six orientations. We call $0$ the original one and 1,2,3,4,5 the ones you get when you rotate the prongs $k*60$ degrees clockwise. We also number the prongs from 1 to 6 using the original orientation. So that the prong that fit in the hole that was congruent to n $\mod6$. fits in the hole congruent to $n+k \mod 6$ in the orientation k. Since every prong only coincides once there is a unique k such that n+k is equivalent to the number that is marked on the prong.
In other words: n is the number of the prong using the original orientation. k is the orientation for which the prong n coincides and p is the number written on the prong( which is also the residue mod 6 of n+k). Therefore if there is a solution then there is a permutation of $(1,2,3,4,5,6)$ named $(p_1,p_2,p_3,p_4,p_5,p_6)$ such that ${1+p_1,2+p_2,3+p_3,4+p_4,5+p_5,6+p_6}$ contains no two elements congruent $\mod 6$ however if this was true the sum of those elements would be congruent to 3 $\mod6$. However the sum of the sum of the two original sets is congruent to 0 $mod 6$. Therefore it is impossible.