Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * - 1 votes

Very long tasks


  • Please log in to reply
7 replies to this topic

#1 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5664 posts
  • Gender:Male
  • Location:New York

Posted 10 August 2012 - 07:01 AM

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.
http://brainden.com/...p/topic/3805--/

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, 10 August 2012 - 03:53 PM.
Add link to previous topic

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#2 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 10 August 2012 - 03:50 PM

Spoiler for I fear I haven't the time, I'm not retired yet...

  • 0

#3 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 10 August 2012 - 05:56 PM

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.
http://brainden.com/...p/topic/3805--/

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?
  • 0

#4 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5664 posts
  • Gender:Male
  • Location:New York

Posted 11 August 2012 - 03:35 AM

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.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#5 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 11 August 2012 - 11:36 PM

Spoiler for I fear I haven't the time, I'm not retired yet...


Aye, Captain,
Spoiler for In agreement with the captain

  • 0

#6 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5664 posts
  • Gender:Male
  • Location:New York

Posted 12 August 2012 - 01:22 AM

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.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#7 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 13 August 2012 - 03:40 PM

Spoiler for Not a clue...


Thanks for the puzzle(s) as always!

Edited by CaptainEd, 13 August 2012 - 03:45 PM.

  • 0

#8 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5664 posts
  • Gender:Male
  • Location:New York

Posted 13 August 2012 - 05:38 PM

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

Spoiler for What occurred to me

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users