For the honor of Hufflepuff

Question

(I created this variant of a classic puzzle a long time ago, before the movie HPCOS was released.)

Enough is enough. You've decided it's time to take a stand. Every year since that boy started attending Hogwarts, Dumbledore has given the House cup to Gryffindor by a "last minute awarding" of large numbers of points to him for ever more dubious reasons. The Gryffindors have even stopped trying, knowing that they'll get the cup no matter what happens. This year, Dumbledore has just announced an award of 400 points to the boy "for parting his hair in a most interesting way", taking the cup away from your own house of Hufflepuff.

So you've confronted Dumbledore, and not only your own house, but also all the Ravenclaws and Slytherins have joined you. Even the Gryffindors look embarassed. "So, young Hufflepuff. I've been partial, have I? Well, then, let's put this nonsense to rest. We'll have a contest, between you and our fine Gryffindor champion. Mr. Finch! Bring the Urns of Peano from my office!" Finch comes back carrying 3 large urns, and Dumbledore calls the two of you forward. You see that two of the urns are empty while the third is full of balls with numbers printed in a strange magical script. Indeed, you pull one out of the top and try to read the number, but it keeps going on around the ball repeatedly, yet somehow without ever overlapping itself. Finally you give up and put it back. Dumbledore explains "In this urn is a ball for every natural number. Yes, infinitely many - a wonderful magic. As you can see, each of the urns has a dispenser track on the bottom where the lowest ten values in the urn are displayed. Go ahead, take the first ball." You pick it up and find the number 0. When you drop it back in the top of the urn, suddenly the balls on the track back up a space, while the 0 ball rolls through them to its original position.

"The contest", Dumbledore explains, "is this: Each of your houses are assigned one of the empty urns. The two of you will act in turns. In each round, you, young Hufflepuff," (you suspect he doesn't even know your name) "will take two balls from the track and place them in the Hufflepuff urn. Then our fine Gryffindor here will take a single ball from the Hufflepuff urn, and move it to the Gryffindor urn. This will continue until one of you can no longer take your turn." "But, won't that take forever?" asks your opponent. "Indeed, it would", Dumbledore replies, "But I shall cast 'Zeno's Accelerator' upon you. Fix a strategy in your mind, and when I cast the spell, your hands will follow it automatically. Each round will take but half the time of the round before, until an infinite number of rounds have been completed. In this way, the entirety of the urn may be emptied in only twice as much time as the first round takes." Your opponent's egghead friend can no longer contain herself. "That's ridiculous! The energy it would take is infinite! The heat produced would kill us all!". "Honestly, young lady,", Dumbledore replies, "you should have learned by now that muggle physics takes a back seat to magic!" The Gryffindor champion still appears confused. "But, sir, if in every round, two balls are added to Hufflepuff, and I take one of them to put in Gryffindor, how will either house pull ahead? We'll just be tied in the end!"

"Oh, no, Gryffindor. You misapprehend! If even one ball remains in the Hufflepuff urn when the contest ends, Hufflepuff will be declared the winner. Let them accuse me of favoritism now!" Your opponent looks very nervous, but suddenly appears to listen to something and calm down. A glance shows his egghead friend whispering something, apparently using a teleloquela charm. Obviously the fix is in. But fortunately, it appears that you've paid more attention to your arithmancy classes than Dumbledore did, for you spot a flaw in his plan. You smile as you fix your strategy in mind.

Why does Dumbledore expect Gryffindor to win? And what strategy can you use to defeat him?

Answer 1

Your strategy should be to

Start by picking balls 2 and 3 and leaving 0 and 1 on the track. Next take balls 4 and 5, etc. This way, when all infinite turns have occurred besides the last, you will pick up the 0 and 1 and put them in your urn. Then when Gryffindor takes the 0 or 1 the first urn will be empty and you can no longer take your turn. There will still be a ball left in Hufflepuff's urn.

Edit: My comments

Even though this is the answer, it is not something that feels comfortable. The main reason is because it is hard for us to grasp what happens in a finite number of turns after an infinite number of turns. I think some of the confusion is due to two conflicting proofs: 1. In the end, all of the balls will be inside of Gryffindor's urn. Others have already stated this better, but you can come to this conclusion because there are an infinite number of balls in the initial urn, and every ball that is placed in the Hufflepuff urn is eventually removed and placed in Gryffindor urn because if the ball is placed in Hufflepuff's urn at turn n, it will be removed in turn 2n. The result which seems to contradict this statement is: 2 After Hufflepuff and Gryffindor have both taken their turns, there will be an equal number of balls in each of their urns. This is because every turn 2 balls are transferred into Hufflepuffs urn from the main urn, and 1 from Hufflepuff's into Gryffindor's.

The first result seems to imply that the end result of the competition will be

Gryffindor: $\infty$ Hufflepuff: 0 Original Urn: 0 or $\infty$?.

Whereas the second result seems to imply that the very end will be:

Gryffindor: $\infty$/2 Hufflepuff: $\infty$/2 Original Urn: 0 or $\infty$?

There is definitely some confusion here about what happens with the initial urn. After all how can we deplete it?

In the first case, we can ignore the initial urn, because we plainly see that Hufflepuff's urn is empty, therefore the competition is over. Whereas in the second case, we cannot be sure that anyone's urn is empty, and therefore the competition is still going on. Part of the logic block here is that we cannot invoke the second case due to lacking a proof that one of the three urns is empty. Therefore we cannot conclude that when Dumbledore magically makes an infinite number of turns occur, that there will be equal number of balls in Gryffindor and Hufflepuff's urns. Why is it different for the last turn to be Hufflepuff removing balls $\infty -1$ and $\infty$ vs 0 and 1? Well, if there are an infinite number of balls, how can there be a last ball? The trick lies in getting rid of infinity before the proof starts. So the reason this proof works, is because Dumbledore has swept away infinity and left us with something we can grasp. On the last turn the balls 0 and 1 will be in the original urn, and they will be the only balls in the urn.

Answer 2

To follow on from the other answers, what Dumbledore has missed is that

he never stated that the entire contest should take place under the Zeno-accelerated time.

In fact,

you can just make your strategy to take all the balls from 2 upwards in ascending order. When the Zeno spell ends, there will still be 0 and 1 in the original urn, with all others in your opponent's urn. At this point, the concept of whose turn it was last is vague at best, but if you manage to argue that it's yours (after all, you don't have any balls left so you can't have just taken two) then you're free to take 0 and 1. Your opponent can only take one of these, leaving you with one at the end of the contest.

A countably infinite number of points to Hufflepuff!

Answer 3

Sorry guys - had to write this. It isn't any different from the accepted answer, but was fun.

...You smile as you fix your strategy in mind.

Suddenly, Gryffindor's egghead friend pipes up, a worried look on her face. "Professor Dumbledore, sir. It is not that I want to question your magic, but I am still concerned about the muggle physics and would not wish to see us all destroyed in the energy release. In the interests of safety, can we avoid the spell and simply argue why our strategy will work?"

Dumbledore shrugs his shoulders, clearly not interested since his young protégé's friend has obviously figured out the problem and the result is no longer in doubt. "If young Hufflepuff agrees..." he says reluctantly putting away his wand.

You have no wish to see your hands move that fast anyway, and wondering if you'd actually live an infinite lifetime during that crazy spell, forced to move balls forever, you agree to her proposal. "Fine", you say. "Since I get to go first, my strategy would be..."

But egghead quickly interrupts. Now that she has the answer, she is quite excited to reveal it and will not wait for your dimwitted pandering.

"Our strategy is to simply take the lowest ball in Hufflepuffs's track."

She seems to also be unaware of your name. How come no one knows who I am? you wonder to yourself. Is a simply memory charm beyond these people?

Egghead continues without pause:

"I can prove that every ball in the his urn must eventually end up in our urn. Thus, our urn has all the balls and Hufflepuff's must therefore be empty."

While most the crowd cannot make sense of the answer, a few Ravenclaws are seen to be nodding sagely. Dumbledore smiles; "Well done! I award 100 points to Gryffindor for outstanding use of logic!" There is a smattering of applause from the Gryffindor crowd, but the rest of the gathered students and teachers hang their heads in collective defeat. "This year's house cup," he continues, "is once again is awarded to..."

"Excuse me Professor Dumbledore", you interject. He pauses his delivery, clearly forgetting you were even there.

"Yes, young Hufflepuff? Do you have something to add?"

"Actually, sir, I haven't had a chance to reveal my strategy sir."

"But haven't you heard young egghe.. I mean Gryffindor's strategy? Can't you see that for any numbered ball you believe to be left in your cup, it will eventually end up in Gryffindor's cup, so at the end of the spell, your urn must be empty?" Egghead, smirks, clearly thinking along the same lines as Dumbledore, that you are confounded by infinity.

"Well, yes sir, I do see that, but if I may..." you start.

"Do you need me to cast my spell so that you may witness the result?" He asks pulling our his wand from beneath his robes.

This time, both you and egghead jump in to stop him and both say "That will not be necessary!" over each other.

"Al-right", he says with a sigh, again reluctantly putting away his wand. "Now, if I may continue with the presentation of the house cup?" He asks, politely waiting for you to surrender the contest.

"I just would like to say my strategy if you don't mind first professor." you say demurely. "I think you will find it interesting."

"Go on if you must", he says, patiently waiting for you.

"As I was going to say professor, my strategy would be to simply leave the first two balls. I will take the lowest of the balls numbered 2 or higher."

You pause and look to egghead to see if she has figured it out. Her puzzled look soon melts into understanding as she realizes your strategy. Dumbledore, however, is still in doubt.

"Yes, yes, and all those balls would end up in Gryffindor's urn, would they not?"

"Yes professor. But the 0 and 1 would be the only balls remaining in the original urn."

"But every ball you put in your urn will eventually be taken and put into the Gryffindor urn correct?" he says, getting impatient.

"Yes, except for the last."

"But there is no last! We are talking about all the numbers! Blast! This is not getting us anywhere." he says taking out his wand again. "I see I have no choice but to cast the spell and prove you are incorrect young Hufflepuff." He begins the spell and you look over to egghead. She is clearly distraught, but cannot stop the crazy old wizard from destroying the universe. You have just enough time to concentrate on your strategy when he completes the spell and you feel a tightness in your chest as light washes all over you. As it dissipates, the contest begins of its own accord.

You watch like a spectator as your hands calmly take the 2 and 3 out of the main urn and put them in your own. You see scarhead take the 2 and put it in his urn. the whole process takes less than 10 seconds. Then your hands move of their own accord and take the 4 and 5, much quicker this time. Four-eyes takes the 3, equally as fast. By the time your hands are reaching for the 12 and 13, you can no longer keep up and close your eyes. Even through your closed lids, you can see that your hands are moving so fast they are starting to glow. You begin to wonder if it will ever end, and the entire school will explo...

...and it is over. You look down and your hands are smoking, but not in too much pain. The original urn is also smoking, but when you look in the top, it is empty. There are only 2 balls remaining in the track. The 0 and the 1.

Your urn is also empty. You glance at Gryffindor's urn and see him also looking at his smoking hands in wonder. He too peers in own urn and smiles. The track contains 2-11 and is full. Egghead is not so pleased; being quicker than her friend, she has seen where you are headed. Unfortunately, Dumbledore has not.

"As you can see, your urn is empty, and Gryffindor's is full. While I appreciate the opportunity to practice my magic, I assume you will now admit defeat so that we can present the cup?" His is very proud of his skills with the Zeno's Accelerator spell and was happy to show it off.

"But sir," you say quietly, "the game is not over".

"Whatever do you mean?" he asks. "Your urn is empty and his is full." He is confused by your stubborness.

"The main urn is not empty professor. I still have a move available to me."

He now sees for the first time that there is a 0 and 1 available. "Go on then, make your last move." As wonderous a wizard he is, he has not seen the eventual outcome.

The Gryffindor crowd, however has. You take the final two balls and place them in your urn. Egghead is hanging her head while Dumbledore's favourite takes the 0 from your urn and places it in his own.

"I can no longer make any moves professor." you announce. Finally, Dumbledore sees what has happened. Your urn contains a single ball labelled 1. The Gryffindor urn contains every other possible ball, but not the 1.

"Well, young Hufflepuff," Dumbledore finally looks at you with more than passing interest. "I see you have outwitted Gryffindor in this test. Congratulations!"

The crowd erupts! Even some of the Gryffindor students are openly cheering for you! As you get pats on the back and handshakes from many kids you never knew, Dumbledore approaches you. "What is your name again young man?" he asks.

"Cedric, sir" you say. "Cedric Diggory."

"Well, congratulations Cedric. You have made your house proud today, and I am certain you will do so again in the near future." His eyes twinkle knowingly and you wonder what he has in store for you...

Answer 4

Gryffindor's strategy will be

to take the lowest number in the Hufflepuff urn every time

and it will work because

every marble will be guaranteed to be removed at most $n$ turns after you put it in, where $n$ is the number on the marble. If a marble is not put in, it will not be in at the end; if a marble is put in, then it will be removed and it will not be in. Therefore, no marbles will be in Hufflepuff at the end.

Answer 5

The concept of infinity involves that there is no last turn. That means for Gryffindor:

They will win with any strategy that guarantees a marble is taken in each turn. This may be "Take the one with the lowest number." or "Take a random one." When the game runs until infinity, then Hufflepuff's urn will be empty.

However, the flaw in Dumbledore's plan is:

"This will continue until one of you can no longer take your turn."

Thus Hufflepuff's strategy will be:

Make sure that we can't take our turn anywhere between 1 and infinity, exclusive. It can be as simple as "Take the marbles numbered 0 and 1." This will work fine in the first turn, leaving 1 marble in Hufflepuff's and 1 marble in Gryffindor's urn. In the second turn, Hufflepuff's strategy will fail, marbles 0 and 1 are no longer available, and the game stops with 1 marble in Hufflepuff's urn.

All points for Hufflepuff!