Very long tasks

[bonanova]

A while back we discussed the interesting process where each step consisted of placing consecutively numbered balls into a bucket, two at a time, and then removing the lowest-numbered ball. We postulated an infinite number of balls being processed in this manner. Completion was "ensured" by executing each step after an interval of time that was one-half of the interval of the previous step. An Infinite number of steps could thus be executed in finite time, after which the bucket could be inspected.

The puzzle was to describe the final contents of the bucket. The unintuitive result is that it would be empty. Even though after each step the number of balls it contains increased by one. 

The interested reader can enjoy my misguided discussion of the outcome here.

We propose here a different kind of very long task, also involving placing and removing balls into and from a bucket. Completion is again the central issue, and the bucket's final contents if it's the case that the task does in fact complete. Nothing in this task is infinite, but it is unbounded.

You are given a bucket that contains an arbitrarily large number N of balls, numbered 1-N. You are to empty it, by a series of steps described below. To make the task interesting, an adversary named Alex tries to prevent you from emptying the bucket. Alex is well equipped to prevent your success. For each numbered ball initially in your bucket, Alex has another bucket with an infinite number of balls marked with the same number. That is, if your bucket initially contains a ball that is numbered 37, Alex has his own bucket with an infinite number of balls also numbered 37. 

Here is how the steps are executed. You remove a ball of your choosing, say its number is p, and discard it. Alex may then add to the bucket an arbitrarily large number of balls numbered p-1, using his infinite bucket of p-1 balls. An individual step can thus add to your bucket a set of new balls of size equal to the number of electrons in the universe. Moreover, your bucket might have started with that many balls initially. But even if your bucket starts with as few as 2 balls, it is not possible to place a bound on the number of steps needed to empty the bucket.

So here's the question: Can you empty the bucket?

Edited August 10, 2012 by bonanova
Add link to previous topic

[CaptainEd]

But, if the person Zeta (or his/her heirs or assigns) will start by removing the ball numbered N, Alex will only be able to add to the N-1s. While Zeta removes N-1s, Alex is constrained to N-2s. As soon as Zeta's team starts on the Ms, Alex is constrained to M-1s, and can never go higher. Eventually, when Zeta's team is working on 2s, Alex is stuffing the bucket with 1s. But once Zeta's team starts working on 1s, Alex has to sit by and twiddle his/her thumbs.

[bushindo]

A while back we discussed the interesting process where each step consisted of placing consecutively numbered balls into a bucket, two at a time, and then removing the lowest-numbered ball. We postulated an infinite number of balls being processed in this manner. Completion was "ensured" by executing each step after an interval of time that was one-half of the interval of the previous step. An Infinite number of steps could thus be executed in finite time, after which the bucket could be inspected.

The puzzle was to describe the final contents of the bucket. The unintuitive result is that it would be empty. Even though after each step the number of balls it contains increased by one.

The interested reader can enjoy my misguided discussion of the outcome here.

We propose here a different kind of very long task, also involving placing and removing balls into and from a bucket. Completion is again the central issue, and the bucket's final contents if it's the case that the task does in fact complete. Nothing in this task is infinite, but it is unbounded.

You are given a bucket that contains an arbitrarily large number N of balls, numbered 1-N. You are to empty it, by a series of steps described below. To make the task interesting, an adversary named Alex tries to prevent you from emptying the bucket. Alex is well equipped to prevent your success. For each numbered ball initially in your bucket, Alex has another bucket with an infinite number of balls marked with the same number. That is, if your bucket initially contains a ball that is numbered 37, Alex has his own bucket with an infinite number of balls also numbered 37.

Here is how the steps are executed. You remove a ball of your choosing, say its number is p, and discard it. Alex may then add to the bucket an arbitrarily large number of balls numbered p-1, using his infinite bucket of p-1 balls. An individual step can thus add to your bucket a set of new balls of size equal to the number of electrons in the universe. Moreover, your bucket might have started with that many balls initially. But even if your bucket starts with as few as 2 balls, it is not possible to place a bound on the number of steps needed to empty the bucket.

So here's the question: Can you empty the bucket?

Some clarification please. What happens when the player removes a ball labeled with the number 1?

[bonanova]

Some clarification please. What happens when the player removes a ball labeled with the number 1?

?

The balls in the bucket decrease in number by one.

There initially were no 0-numbered balls, so Alex wasn't given an infinite bucket of 0 balls.

[bushindo]

But, if the person Zeta (or his/her heirs or assigns) will start by removing the ball numbered N, Alex will only be able to add to the N-1s. While Zeta removes N-1s, Alex is constrained to N-2s. As soon as Zeta's team starts on the Ms, Alex is constrained to M-1s, and can never go higher. Eventually, when Zeta's team is working on 2s, Alex is stuffing the bucket with 1s. But once Zeta's team starts working on 1s, Alex has to sit by and twiddle his/her thumbs.

Aye, Captain,

Let's look at the strategy where we remove the highest numbered ball at every turn. Let's define Alex's decision function as f(i, j), which is a integer-valued function that returns the number of balls that Alex would add on the j-th time that the player removes a ball numbered i. The function f(i,j) can be arbitrarily large, but it must still be a well-defined function. Also, note that f(1,j) = 0 for all j, since Alex does not have any ball labelled '0'.

Define T_i as the maximum possible number of balls with the number i that would be in the bag under this strategy. It is easily to see that we can write a recursive function for T_i-1 given T_i:

where T_N = 1. So, given a finite N number of balls at the beginning, and an integer-valued decision function f(i,j), we can derive the ultimate maximum number of balls of any label. The function f(i,j) may be arbitrarily large; for instance, we could imagine a case where f(i,j) = 10¹⁰⁰⁰, which within 1 turn would result in the bag having more balls than the number of atoms in the observable universe. However, in theory, the recursive function above have finite number of terms, and so the drawing process should come to an end eventually.

[bonanova]

Exactly right, both.

Captain, I held off with congratulations on the off chance someone would succumb to the possible enormity of the ball count and make a case for the other side. When i sketched an array of balls it began with a long line and morphed, successively, into an enormous square, a massive cube, humongous hypercube, and so on. The number of dimensions of the unbounded hyper cube itself is unbounded. It might have overwhelmed one's reasoning.

But not here. Not with these puzzle solvers. Bravo.

Now for a hydrophyllically encrypted summary of the result; with extra points for explanation:

China bests Japan.

Clue: not a reference to the Olympic Games.

[CaptainEd]

tea over sake (both water-soluble substances, hence hydrophilic)

T / S

Time conquers space? ? ... ?

As Costello says to Abbott in "Who's On First?", "I don't even know what I'm talking about!"

Thanks for the puzzle(s) as always!

Edited August 13, 2012 by CaptainEd

[bonanova]

My comment is probably too far fetched to spend much time on:

After the deluge of Alex's contributions to the bucket,

a slow, steady "dripping" of balls prevails to empty it.

Chinese water torture outlasts the Tsunami.