3
$\begingroup$

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.

Test with class of 4

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:

  1. Each student does not recieve their homework initally
  2. 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.

Improve this question
$\endgroup$
  • $\begingroup$ One minor clarification, shouldn't it be the case that we'll arrive at a configuration where at least (not exactly) 3 student have the right homework? Regardless of n, we can always have the situation where the homework ordering is correct but the rotation is not, meaning everyone will have the correct homework at some point. $\endgroup$ – Nuclear Hoagie Oct 1 '20 at 20:34
  • $\begingroup$ Indeed that was how I interpreted it since getting everyone their homework would be impossible just by passing right $\endgroup$ – user831274 Oct 1 '20 at 20:47
1
$\begingroup$

If we perform a full $2n - 1$ passes, then everyone has seen their homework exactly once. We know that the first $n$ passes, the first $n + 1$ configurations, no one has seen their homework. If we continue on into the remaining $n - 1$ configurations, and at most 2 students see their homework in every configuration, at most how many students have seen their homework? How does this contradict what we've already said?

Improve this answer
$\endgroup$
0
$\begingroup$

Here's how you can approach it. Fill in the gaps yourself.

Generally when applying PP, it's very important to be clear on what the holes and pigeons are. Defining them often a great start, so:
Let the holes be "Configurations where the students are given homework rotated $k$ times".
Let the pigeons be "Student has the correct homework".

Assuming that these definitions are the correct ones to use, let's pursue how PP could work:
How many pigeons are there?
What is the maximum number of holes we can have to ensure that there is some hole with 3 pigeons?
Can we show that we have at most this many holes? If no, how can we tweak the holes (or pigeons)?

There is some uncertainty about what the exact number of holes are.

  • If the number of holes is $n-1$ (meaning that there are $n+1$ configurations which are compeltely mismatched), then PP works directly.
  • If the number of holes is $n$ (meaning that there are $n$ configurations which are compeltely mismatched), then the question is wrong. In particular, the statement is true for even $n$ and false for odd $n$. This can be proved by 1) Getting a contradiction for "exactly 2 papers match for $n$ is even", and 2) Constructing a case for "exactly 2 papers match for $n$ is odd".
Improve this answer
$\endgroup$
  • $\begingroup$ I attempted another exampled, but keep arriving at the same issue. For instance, let's say that the class is 2n, where n = 3. This is a class size of 6 then. If we assume that no student holds their homework for n+1 rotations, as the instructions stipulate, this means there are two more configurations: the second to last, and then the final configuration before returning to start.This means we have two pigeon holes where a student receives the correct homework, although they must be different students in each pigeon hole since the rotation would move the previously correct students homework. $\endgroup$ – user831274 Oct 1 '20 at 21:46
  • $\begingroup$ @AlbertanTex I read the "for the first n times that they did this" to mean that it was passed around $n$ times, and $n+1$ configurations are incorrect. This gives us $2n$ pigeons and $n-1$ holes, so there are 3 pigeons in some hole. $\endgroup$ – Calvin Lin Oct 1 '20 at 22:09
  • $\begingroup$ Conversely, if there are just $n$ configurations that are completely incorrect, then the statement is true for even $n$, but false for odd $n$. In particular, for $n=3$, a distribution of $2, 4, 6, 5, 1,3 $ at the end of the 3rd checking, yields "no subsequent configuration gets 3 matches". $\endgroup$ – Calvin Lin Oct 1 '20 at 22:11
  • $\begingroup$ I see what you mean now. Your first interpretation was correct I believe. I had been so busy about visualizing with actual method that I hadn't considered the actual mathematics of it. If we have 2n pigeons and 2n-(n+1), we would end with n-1 pigeon holes left, meaning it would be 2n/(n-1) to figure out how many in each at least. Thank you! $\endgroup$ – user831274 Oct 1 '20 at 22:42
  • $\begingroup$ @AlbertanTex The case of $n$ configurations are compeltely mismatched is also worthwhile to consider. See if you can prove 1) and 2) above. $\endgroup$ – Calvin Lin Oct 1 '20 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy