3

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.

Gerard
  • 4,264
  • 2
    Let's try and get the question straight; it's a little confusing as written. We have a socket with six holes that are all uniquely numbered from $1$ to $6$. We are to prove that there is a plug with six uniquely numbered prongs so that at least one prong will go in the right hole regardless of the orientation in which the prong is plugged in. Is that correct? – Ben Grossmann Aug 05 '13 at 16:03

1 Answers1

2

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.

Asinomás
  • 105,651
  • Here $p_1, p_2, \dots ,p_6$, refer to the numbers on the prongs? If so, then how do you relate the number on the prong to it's index in the original orientation? – Gerard Aug 06 '13 at 10:22
  • no. p_1 is the number of times you need to rotate the prong which was in position 1 in the start gets to the position which is on the prong. Since there is only one coinciding prong with for every rotation then ${p_1,p_2,p_3,p_4,p_5,p_6} ={1,2,3,4,5,6}$ – Asinomás Aug 06 '13 at 15:23
  • Okay. I was kind of thrown off by your earlier reference to $p$ as the number on the prong. – Gerard Aug 06 '13 at 16:04
  • Did you understand it? – Asinomás Aug 06 '13 at 16:22
  • When you say 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\space 6$, do you mean that it contains no two elements congruent to the same value $mod\space 6$? If so, then how do you conclude that the sum is congruent to $3 \space (mod \space 6)$? – Gerard Aug 07 '13 at 10:17
  • You have 6 numbers. All of them are congruent to six different values mod 6. However a number can only be congruent to 0,1,2,3,4,5 or 6 mod 6. Therefore one needs to be congruent to each one. that means thart the sum of all the numbers is congruent to 1+2+3+4+5+6 mod 6 which is congruent to 21 mod 6 which is congruent to 3 mod 6. However the sum of the original two set is congruent to 0 mod 6 so therefore it is impossible. – Asinomás Aug 07 '13 at 18:21
  • Which 'original set' are you referring to? You say, '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'. Forgive me for asking so many questions, but I can't seem to understand. – Gerard Aug 08 '13 at 15:01
  • Ok, so there are 6 different ways to plug the prongs in. We call one of them the original one( position0). Then position 1 is the one you get when you rotate it 60 degrees.position 2 is when you take position 1 and then rotate another 60 degrees. Which is the same as taking position 0 and rotating 120= 60*2 degrees. – Asinomás Aug 08 '13 at 16:21
  • Oh! Now I understand. Thanks so much. Excellent solution. – Gerard Aug 09 '13 at 06:49