A hat contains 1992 pieces of paper in it, each piece of paper having its unique number in the range 1-1992 printed on it. A person picks two random notes from the hat, calculates the difference between the two numbers on the notes, writes this number on a new note, throws this new note into the hat and disgards the two notes he/she picked. The person then picks another two random notes from the hat and does the actions described above again. The person continues doing this task until only one note remains in the hat.
Prove that the number on this note is even.
Notes in a hat
-
Cool Hand
- Posts: 10000
- Joined: Sun Jun 06, 2004 4:09 pm
- Location: Earning my avatar in the rain
-
Stimpson J. Cat
- Posts: 352
- Joined: Sun Jun 13, 2004 8:51 pm
- Location: Eindhoven
Start with the last card. It is a difference card. Go backwards to the beginning. At each step:
If the difference card is odd, then going back one step increases the number of even cards by 1.
If the difference card is even, then going back one step either:
1) Increases the number of odd cards by 2, and decreases the number of even cards by 1.
2) Increases the number of even cards by 1.
Thus for N steps, the total number of even cards will be of the following form:
e0 + a - b + c,
where e0 is either 1 or 0, depending on whether the last card is even or not. a is the number of times the difference card was odd. b is the number of times we got option 1 above, and c is the number of times we got option 2 above.
Note that a + b + c must equal N, which in this case is 1991. If we start with an odd card (e0 = 0), then a - b + c = 996.
The total number of odd cards will be of the following form:
o0 + 2b,
where o0 is either 1 or 0, depending on whether the last card is odd or not. If we start with an odd card (o0 = 1), then 1 + 2b = 996. This is impossible.
Therefore the first card must be even. If this is the case, then we get:
2b = 996 -> b = 498,
1 + a - b + c = 996 -> a - 498 + 2 = 995 -> a + c = 1493
We also have a + b + c = 1991 -> a + c = 1493
So we know for sure that the number of times we remove two odd cards (replacing them with an even difference card) will be exactly 498, regardless of what order we select our cards. The other two possibilities are unknown, except for the constraint that they must add up to 1493.
Edited to add: If this seems overly complex, the key point to notice is that, at any step, there is only one way to change the number of odd cards, and that is to remove two odd cards, and replace them with an even difference card. If you remove two even cards, the odd cards are unaffected, and if you remove an even and an odd card, they are replaced by an odd difference card. Since this means that odd cards must be removed two at a time, and there are an even number of them to begin with, it is clear that the last two odd cards are removed, all remaining cards will be even.
Dr. Stupid
If the difference card is odd, then going back one step increases the number of even cards by 1.
If the difference card is even, then going back one step either:
1) Increases the number of odd cards by 2, and decreases the number of even cards by 1.
2) Increases the number of even cards by 1.
Thus for N steps, the total number of even cards will be of the following form:
e0 + a - b + c,
where e0 is either 1 or 0, depending on whether the last card is even or not. a is the number of times the difference card was odd. b is the number of times we got option 1 above, and c is the number of times we got option 2 above.
Note that a + b + c must equal N, which in this case is 1991. If we start with an odd card (e0 = 0), then a - b + c = 996.
The total number of odd cards will be of the following form:
o0 + 2b,
where o0 is either 1 or 0, depending on whether the last card is odd or not. If we start with an odd card (o0 = 1), then 1 + 2b = 996. This is impossible.
Therefore the first card must be even. If this is the case, then we get:
2b = 996 -> b = 498,
1 + a - b + c = 996 -> a - 498 + 2 = 995 -> a + c = 1493
We also have a + b + c = 1991 -> a + c = 1493
So we know for sure that the number of times we remove two odd cards (replacing them with an even difference card) will be exactly 498, regardless of what order we select our cards. The other two possibilities are unknown, except for the constraint that they must add up to 1493.
Edited to add: If this seems overly complex, the key point to notice is that, at any step, there is only one way to change the number of odd cards, and that is to remove two odd cards, and replace them with an even difference card. If you remove two even cards, the odd cards are unaffected, and if you remove an even and an odd card, they are replaced by an odd difference card. Since this means that odd cards must be removed two at a time, and there are an even number of them to begin with, it is clear that the last two odd cards are removed, all remaining cards will be even.
Dr. Stupid
-
Beleth
- Posts: 2868
- Joined: Tue Jun 08, 2004 8:55 pm
- Location: That Good Night
o(n) is the number of papers with odd numbers on them at step n.
e(n) is the number of papers with even numbers on them at step n.
If the two papers are both odd, the new paper will be even.
o(n+1) = o(n) - 2
e(n+1) = e(n) + 1
If the two papers are both even, the new paper will be even.
o(n+1) = o(n)
e(n+1) = e(n) - 1
If one is even and one is odd, the new paper will be odd.
o(n+1) = o(n)
e(n+1) = e(n) - 1
As Stimpy pointed out, the only way for the odd numbers to decrease is two at a time. Since the number of papers is always going down by 1, the last paper will be odd or even depending only on how many odd numbers there were to begin with. Since there are 1992/2 = 996 odd numbers in the range from 1 to 1992, eliminating odd numbers in pairs until you can't eliminate any more will leave you with 0 odd numbers every time, and never 1 odd number.
Therefore the last paper will have an even number on it.
And likewise, if you take the numbers from 1 to 1993 and do the same thing, the last paper will always have an odd number on it.
e(n) is the number of papers with even numbers on them at step n.
If the two papers are both odd, the new paper will be even.
o(n+1) = o(n) - 2
e(n+1) = e(n) + 1
If the two papers are both even, the new paper will be even.
o(n+1) = o(n)
e(n+1) = e(n) - 1
If one is even and one is odd, the new paper will be odd.
o(n+1) = o(n)
e(n+1) = e(n) - 1
As Stimpy pointed out, the only way for the odd numbers to decrease is two at a time. Since the number of papers is always going down by 1, the last paper will be odd or even depending only on how many odd numbers there were to begin with. Since there are 1992/2 = 996 odd numbers in the range from 1 to 1992, eliminating odd numbers in pairs until you can't eliminate any more will leave you with 0 odd numbers every time, and never 1 odd number.
Therefore the last paper will have an even number on it.
And likewise, if you take the numbers from 1 to 1993 and do the same thing, the last paper will always have an odd number on it.
-
DanishDynamite
- Posts: 2608
- Joined: Mon Jun 07, 2004 4:58 pm
- Location: Copenhagen
-
Stimpson J. Cat
- Posts: 352
- Joined: Sun Jun 13, 2004 8:51 pm
- Location: Eindhoven
Yeah. In effect, the paragraph I added at the end is sufficient as a proof. The stuff before that is really just an explanation about how I figured it out. Rather than looking for some sort of trick or simple solution, I took basically the same approach I would take when tying to solve a physics problem. Namely breaking it down, and explicitely writing out in mathematical form everythin that I can deduce about the system. Often times, as was the case here, this will result in the answer just sort of "popping out".I have to say that Stimpy's solution was indeed very complex. I'm glad he added his "Edited to add" bit as that describes the core of the argument. Beleth, your proof was immaculate.
Dr. Stupid