Jump to content
BrainDen.com - Brain Teasers
  • 0

Very long tasks


bonanova
 Share

Question

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 by bonanova
Add link to previous topic
Link to comment
Share on other sites

7 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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?

Link to comment
Share on other sites

  • 0

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 Ti 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 Ti-1 given Ti:

post-14842-0-63830100-1344724009_thumb.p

where TN = 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) = 101000, 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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...