I'm working on a homework problem with the following instruction:
Suppose there is a class of 2n students with different names sat in a large show and tell circle. The teacher returns their homework, but each student in the circle is given another student's homework. Therefore, the class agrees to pass the homework to the student sitting to their right. Once again, the names are all wrong. For the first n times they do this, they all have the wrong named homework. So in all there are n + 1 configurations in which every student is matched with someone else's homework). Show that if they continue passing the homeworks to their right, they will eventually reach a configuration where 3 students have the homework with their own names.
I've done a few problems with the pigeonhole principle, but this one is giving me exceptionally more trouble. I've illustrated two separate cases, both where n = 2, which both result in a class size of 4. The uppercase letters are the children and the lowercase letters are the corresponding homeworks.
With the above starting configuration, I could not get it to be where three students concurrently have the correct homework, only two at once. I also didn't break any of the apparent contraints:
- Each student does not recieve their homework initally
- Each student does not have their homework after 1 round of passing
The second case in the drawings is to exemplify what would happen if the student to one's left had their homework, i.e. necessitating only one pass. However, I'm fairly certain the question says this is not allowed since
Therefore, the class agrees to pass the homework to the student sitting to their right. Once again, the names are all wrong.
Meaning that the round after the first pass must also ensure no one has their homework. I trust the question is correct in what it is proposing, but I am having trouble understanding it and applying the Pigeonhole principle. Are the "holes" the kids and the "pigeons" he homework and if so, how would one calculate in the case where it's not as simple as a pigeon in the hole, but the correct pigeon in the correct hole? Any help would be appreciated.