When midnight strikes

[bonanova]

At an ever increasing pace Al, Bert and Charlie have been receiving into three identical boxes of limitless capacity identical pairs of silver coins engraved with the integers 1, 2, 3, 4, ... etc. These events occur on a precise schedule, each box receiving

• Coins marked 1 and 2 at 1 minute before midnight
• Coins marked 3 and 4 at 1/2 minute before midnight
• Coins marked 5 and 6 at 1/4 minute before midnight
• Coins marked 7 and 8 at 1/8 minute before midnight
• etc.

But they were instructed at each event to remove a coin from their respective boxes and discard it. After some thought, Al decided each time to discard his lowest-numbered coin; Bert discarded an even-numbered coin; and Charlie thought what the heck and discarded a coin selected at random. Regardless of strategy, at each event the number of coins in each box grew by unity, so that after N events each box held N coins.

Needless to say when midnight struck their arms were infinitely tired, but it was a small price to pay for infinite riches. But tell us, now, whether their expectations were met.

Describe the contents of each box at midnight.

[ThunderCloud]

2 hours ago, CaptainEd said:

Ok I believe Al is empty...

 

  Reveal hidden contents

 

ok I see that Al’s box will have the property that for any finite number n, n is not in his box. Thanks, Bonanova. Infinity is even more confusing than I knew.

It’s clear (I thought it was clear) that Bert will have every odd coin in his box.

So I guess your claim is that the random removal will remove ALL of Charlie’s coins! I have to keep ruminating...

 

 

Spoiler

If you were to choose a coin that is inside Charlie's box after a pair has been added at some step n, the probability that your chosen coin will not be removed at that step is n / (n + 1), because there are n + 1 coins in the box at that moment. The probability that it will still not be removed by the next step is ( n / (n + 1) ) * ( (n + 1) / (n + 2) )… and so, the probability that it remains after k additional steps is n / (n + k + 1). Clearly, as k →∞, the probability of any chosen coin remaining in the box approaches zero.

 

This was a fun one. ^.^

 

[rocdocmac]

Kicking of again, if I understand correctly ...

Spoiler

After n events Al should have collected coins with a collective value of 2n, Bert 2n-1, and Charlie 2n-0.5 (according to a 50/50 probability), i.e. Al should have the highest total, Charlie the least and Bert would be about halfway in between.

 

Edited February 16, 2018 by rocdocmac

[Pickett]

Spoiler

AL: Since he removes the lowest value each time, he ends up with all of the values from N+1 to 2*N in his bag. So the total can be calculated as (3N² + N) / 2

BERT: He's removing an even each time...and since he only gets one even every round, he's left with only the ODD numbers left. So the total can be calculated as simply N²

CHARLIE: He's obviously a little bit trickier...I will spare you the ugly details of how I arrived at this, but basically you are calculating the expected value by multiplying the number by the probability that that number will be present at midnight. This calculation can be ultimately simplified down to a sum: ∑ _{x=1 -> N}  (4x²-x) / (N+1)

So...Here's a quick example of their payouts for increasing values of N:

N        | AL                  |  BERT                | CHARLIE (expected)        
1        |                   2 |                    1 |                   1.5
4        |                  26 |                   16 |                  22
10       |                 155 |                  100 |                 135
250      |              93,875 |               62,500 |              83,375
1000     |           1,500,500 |            1,000,000 |           1,333,500
75998    |       8,663,582,005 |        5,775,696,004 |       7,700,940,671.895
250250   |      93,937,718,875 |       62,625,062,500 |      83,500,125,041.563
5000000  |  37,500,002,500,000 |   25,000,000,000,000 |  33,333,334,166,666.794
10000000 | 150,000,005,000,000 |  100,000,000,000,000 | 133,333,335,000,000

 

[bonanova]

@Pickett Interesting result. OP meant for the coins to have equal value, but yours is a great puzzle also, even for finite numbers of coins received.

@rocdocmac and @Pickett When midnight has struck an infinite number of events will have transpired and the process will have stopped. Will any of the three be happier than the others?

[rocdocmac]

Spoiler

It was a dead stop at midnight. Maybe Al will be the happiest, but they will all be content as it was their own choice as to which coins to discard. Still a lot of riches for all three after midnight (at infinity level), so who's going to complain about any difference?

 

Edited February 17, 2018 by rocdocmac

[bonanova]

Actually, two of the boxes will be empty.

[CaptainEd]

But...but...but, the OP points out that after N events, there will be N coins in the boxes! I always found infinity confusing, but how will they become empty?

[CaptainEd]

Ok I believe Al is empty...

ok I see that Al’s box will have the property that for any finite number n, n is not in his box. Thanks, Bonanova. Infinity is even more confusing than I knew.

It’s clear (I thought it was clear) that Bert will have every odd coin in his box.

So I guess your claim is that the random removal will remove ALL of Charlie’s coins! I have to keep ruminating...

[rocdocmac]

Is  Confucious still alive and well?

[CaptainEd]

Thanks Thundercloud, that makes sense. Ok I’m on board with two empty boxes.

[harey]

After N steps, they will have received 2*N coins and withdrawn N coins. At that moment, there will be 2*N-N coins in the box.

If the box is empty at midnight, this implies:

limit(2*N-N)(for N->inf) = 0

At least a little bit surprising.

@ThunderCloud

I have some troubles to refute your argument. If you remove an infinity of finite numbers from infinity of finite numbers, it does not imply no finite number remain. (Not sure I am convincing and clear enough.)

Counterargument: Al removed all coins 1 - N, coins > N remain. If N -> inf, numbering looses it's sense, but he did not remove all coins.

As for Charlie, I am ruminating, too. The first idea: every number will remain with p=1/2. Wrong, 1 will be more likely removed than 99.

2nd idea:
1st step, 2 coins: p(removing 1)=1/2
2nd step, 3 coins: p(removing 1)=p(1 was not removed in the first step) * 1/3 = 1/2 * 1/3 = 1/6, p(1 remaining after 2nd step)=1 - 1/2 - 1/6 = 1/3
3rd step, 4 coins:  p(removing 1)=p(1 not yet removed) * 1/4 = 1/3 * 1/4 = 1/12, p(1 remaining after 3rd step)=1 - 1/2 - 1/6 - 1/12 =

I will not venture further, but this will not converge to 0. (Compare to 1 - 1/2 - 1/4 - 1/8...)

 

Edited February 20, 2018 by harey
For the pleasure to put it in bold.

[bonanova]

13 hours ago, harey said:

Al removed all coins 1 - N, coins > N remain. If N -> inf, numbering looses it's sense, but he did not remove all coins.

As for Charlie, I am ruminating, too. The first idea: every number will remain with p=1/2. Wrong, 1 will be more likely removed than 99.

2nd idea:
1st step, 2 coins: p(removing 1)=1/2
2nd step, 3 coins: p(removing 1)=p(1 was not removed in the first step) * 1/3 = 1/2 * 1/3 = 1/6, p(1 remaining after 2nd step)=1 - 1/2 - 1/6 = 1/3
3rd step, 4 coins:  p(removing 1)=p(1 not yet removed) * 1/4 = 1/3 * 1/4 = 1/12, p(1 remaining after 3rd step)=1 - 1/2 - 1/6 - 1/12 =

I will not venture further, but this will not converge to 0.

 

Spoiler

Al:
On step 1 Al discards coin 1. On step 2 A discards coin 2. ... On step N Al discards coin N. As N -> inf, every coin is discarded.
If there were a coin in Al's box at midnight it would have a number. What number would that be?

Spoiler

Bert:
On step 1 coin 1 enters Bert's box and is never discarded.
On step 2 coin 3 enters Bert's box and is never discarded. etc.
At midnight every odd coin remains in Bert's box.

Spoiler

Charlie:
After N turns, what are the probabilities for coins to remain in Charlie's box?

• P_N(coin 1) = (1/2) (2/3) (3/4) (4/5) ... (N-1/N) = 1/N
• P_N(coin 2) = (2/3) (3/4) (4/5) ... (N-1/N) = 2/N
• P_N(coin 3) = (3/4) (4/5) ... (N-1/N) = 3/N
• P_N(coin 4) = (4/5) ... (N-1/N) = 4/N
  ...
• P_N(coin k) = k/N

At midnight, the probabilities for coins to remain in Charlie's box have vanished.

Spoiler

One might note that after N turns, P_N(coin N) = N/N = 1. That is, at each turn the probability that the last coin to appear in the box is in the box with probability of unity. That may appear to be a counter argument, but it is not. In particular we can't meaningfully take the limit of that ratio as N -> inf to prove there must be at least one coin in Charlie's box at midnight, for two reasons.

Spoiler

First, the ratio has heterogeneous "units." The numerator is the number of a coin whose condition (in the box or not) we wish to know, while the denominator is the index number of the successive events that lead up to midnight. So the numerator and denominator should be represented by distinct variables.

Spoiler

Second, to say the last coin to enter the box is in the box, and taking this to infinity would provide relvant information only if there were a last integer. Which there is not. Nor is there a last coin or a last event. 

What we can say is that for every coin k, P_N(coin k) = k/N ->0.

 

 

 

 

 

 

[harey]

12 hours ago, bonanova said:

 

  Hide contents

Al:
On step 1 Al discards coin 1. On step 2 A discards coin 2. ... On step N Al discards coin N. As N -> inf, every coin is discarded.
If there were a coin in Al's box at midnight it would have a number. What number would that be?

Lets start with this one.

If every coin is discarded, it comes to claim that inf - inf =0

Remember the hotel with an infinite number of rooms all occupied? An infinity of guests arrive, you move the person from room 1 to room 2, from room 2 to room 4, from room 3 to room 6... getting an infinity of empty rooms.

Now, an infinity of guests leave. Is the hotel empty? And why?

 

Edited February 21, 2018 by harey
corrected a typo

[bonanova]

@harey

Hilbert's hotel tells us not to treat countably infinite sets the same way we treat finite sets. There is no 1-1 correspondence between { 1 3 5 7 9 } and { 1 2 3 4 5 6 7 8 9 10 } as there is between the (infinite set of) { odd integers } and the (infinite set of) { integers.} Hilbert's hotel always has room for more. Completion (of an infinite set of tasks) is another tricky concept. If we number some tasks 1 2 3 ... and there is no final integer, how can there be a final task? And if there's no final task how can we complete infinitely many tasks, or describe the state of things after they have transpired?

We finesse that point with a 1-1 correspondence of event times to the terms of an infinite series, 1 1/2 1/4 1/8 ... 1/2^n ...., which (conveniently) converges. We pack a countably infinite set of events into a time interval that ends at midnight. "Completion" is cleverly accomplished in two seconds. It's non-physical enough that it never could happen, but we can reasonably discuss the post-midnight state of affairs nonetheless.

We have two countably infinite sets, {coins} and {events}. At each event, two coins are added to a box and one coin from that box is discarded. So, of the two added coins, at least one is kept. We know that at midnight the entire set {coins} has entered each box, and some (proper or not) subset of them has been discarded.

The key question is this: can a coin that is kept at a certain event ever be discarded at a later event?

For Al, the answer is yes. Al always discards his lowest coin, so at each event time t_i he discards coin c_i. Thus eventually that is, upon completion of the infinite set of tasks, every coin that is initially kept is later discarded. At midnight no coins remain. Al's box is empty.

Spoiler

If coins remain in Al's box, one of them must have a number that is lower than the others. But at every event Al discards the lowest numbered coin. More directly, if any coin remains it must bear a number, say k. But coin c_k was discarded, prior to midnight, at time t_k.

For Bert the answer is no. Bert discards the highest-numbered of his coins, and that is always the even coin that he just received. At no event is Bert ever scheduled to discard an odd coin. Every odd coin that enters Bert's box is kept, and it stays there forever. Bert's box contains a countably infinite set of coins.

For Charlie the answer is ... well ... um ... actually ... I guess ... yeah, but it might take an infinite number of events for it to be discarded. Well it just so happens that we have an infinite number of events that follow the keeping of every one of Charlie's initially kept coins. So, yes. All of Charlie's coins that are not immediately discarded are eventually discarded. At midnight, Charlie's box is empty.

[harey]

6 hours ago, bonanova said:

The key question is this: can a coin that is kept at a certain event ever be discarded at a later event?

If a coin can be discarded, it does not mean it will be discarded. I would reformulate it: The key question is this: will all coins that are kept at a certain event ever be discarded at a later event?

BTW, we can establish a bijection between Al's and Bert's coins. The coins bear green numbers. After each step, Al renumbers them and assigns them blue numbers 1, 3, 5, ... His blue numbers will match the (green) numbers in Bert's box. For any number of steps. I think it is legal to assume it is true even for N-> inf.

Another way to prove that Bert's box will not be empty: graphical presentation. The number of coins in his box is a straight line (at 45 degrees). How is that it suddenly drops to 0?

And maybe a corollary: Bert never discards more coins that he receives. How is that when he has, let's say 8 coins, he can have less in a later stage?

If we reason with {coins} and {events}, don't you see a 1-1 relation?

[rocdocmac]

On 2/21/2018 at 12:47 AM, bonanova said:

  Hide contents

 

 

Spoiler

"Al:
On step 1 Al discards coin 1." Al therefore retains coin 2. "On step 2 A discards coin 2." He retains coins 3 & 4, "... On step N Al discards coin N." Thus, he retains coins N+1, N+2, ...., and 2N. "As N -> inf, every coin is discarded." What happened to the N coins not discarded?

"If there were a coin in Al's box at midnight it would have a number. What number would that be?" There ought to be N coins left, numbered n+1, 2+2, ..., 2N.

I still can't get to grips with this one!

 

Edited February 22, 2018 by rocdocmac
Moved to spoiler

[bonanova]

4 hours ago, harey said:

If a coin can be discarded, it does not mean it will be discarded. I would reformulate it: The key question is this: will all coins that are kept at a certain event ever be discarded at a later event?

I would dispute your first point. I can't immediately think of a scenario that permits a discard which will not eventually happen given an infinite number of opportunities. Can you provide one?

We agree on the second point. My previous post answers precisely that question.

[bonanova]

2 hours ago, rocdocmac said:

  Hide contents

"Al:
On step 1 Al discards coin 1." Al therefore retains coin 2. "On step 2 A discards coin 2." He retains coins 3 & 4, "... On step N Al discards coin N." Thus, he retains coins N+1, N+2, ...., and 2N. "As N -> inf, every coin is discarded." What happened to the N coins not discarded?

"If there were a coin in Al's box at midnight it would have a number. What number would that be?" There ought to be N coins left, numbered n+1, 2+2, ..., 2N.

I still can't get to grips with this one!

 

That is what infinity does to our brains.

Al retains coin 2 at step 1. But Al discards coin 2 at step 2. What is true for coin 2 is true for every coin. Every coin has a scheduled pre-midnight discard date. So "what happened to the N coins not discarded?" If N is finite, then it's not midnight yet, and the box does in fact contain coins. We have to be patient. The process has to run its course. And, specifically, {coin n+1} will be discarded at step n+1, at time t n+1, prior to midnight. So after midnight, it will be gone. Along with all the others.

Every coin, identified by the number engraved on it, has a well-defined pre-midnight discard date.

But then if we're Bert, who never schedules the discard of an odd coin, we'll have a ton of coins.

[harey]

1 hour ago, bonanova said:

I would dispute your first point. I can't immediately think of a scenario that permits a discard which will not eventually happen given an infinite number of opportunities. Can you provide one?

Maybe an idea. There is an infinite number of numbers between 0 and 1. I have the opportunity to discard an infinite number of numbers between 0 and 1.

How much are you willing to bet that nothing remains between 0 and 1?

[bonanova]

10 hours ago, harey said:

Maybe an idea. There is an infinite number of numbers between 0 and 1. I have the opportunity to discard an infinite number of numbers between 0 and 1.

How much are you willing to bet that nothing remains between 0 and 1?

Isn't this fun?

The { real numbers } between 0 and 1 comprise two infinite groups: { rationals } and { irrationals }. Rationals (expressible as p/q where p and q are integers) are countably infinite. We can order them, by placing them in an infinite square of p-q space and drawing a serpentine diagonal path. But the irrationals are not countable. The cardinality (notion of size used for infinite sets) of the rationals is called Aleph₀ and for the irrationals (and reals) it's called Aleph₁ or C (for continuum.)  So first off, what we can do with the { numbers } between 0 and 1 depends on { which numbers } we want to deal with.

Next, there's a problem that points are not objects that can be moved from place to place, as coins can. Points are more descriptions of space than of autonomous objects. If 0 and 1 are on a number line, the location midway between them is the point denoted by 0.5. It can't be removed. (We could erase the line, I guess, but that would not produce an interval [0 1] devoid of numbers, either.) But we can finesse this matter by "painting" a point. Kind of like what we did when we inscribed a number on each coin. Painting does a little less - it puts a point into a particular group or class but it does not distinguish among them.  We can tell coin 2 from coin 3 and also distinguish both from a coin with no inscription. Two blue points, however, are distinguishable from unpainted points, but not from each other. But for our purpose here, painting is actually enough.

Since the { rationals } are countable, we can paint them, in sequence, and if we do that at times of 1, 1/2, 1/4 .... minutes before midnight, all the rationals between 0 and 1 will be painted blue by midnight. (I don't know of a similar scheme for completing uncountable task sets, so the irrationals alas must remain unpainted.) Next, instead of asking whether all the points in [0 1] were removed, we can ask, with pretty much the same meaning, whether at this point the entire interval [0 1] has been painted blue. It should be, right? After all, between any two rationals lie countably infinite other rationals. So the paint must have covered the entire interval, right?. Well ... actually ... the answer is counter-intuitively No.

And this is because even though the { rationals } are "dense" meaning there are no "gaps" between them, as noted above, the { irrationals } are even "more dense." That is, between any two irrational numbers there are uncountably many other irrationals. That means, for every blue point we created in the interval [0 1] there are uncountably many unpainted points. We can't magnify the line greatly enough to "see" individual points, but "if we could," if we were lucky enough to come across a single blue point we'd have to pan our camera over uncountably many unpainted points before we saw another blue one. In measure theory, the measure of the rationals over any interval is zero. The measure of the irrationals over [0 1] is unity.

So what of our quest of emptying [0 1] of points? It's the same as our quest to paint [0 1] blue by painting all the rational numbers in that interval. (Reminding ourselves that there were too many irrationals to paint one at a time.) Turning again to measure theory, the measure of the "blueness" of the interval would be zero. That means we would not see even the hint of a faint blue haze.  Back to our "empty the interval by removing the rationals" quest, Nope. [0 1] would not be empty: uncountably many points (numbers) would remain.

[harey]

Sorry for 'discard', I meant these numbers build a {set} from which elements can be removed. And yes, we remain in rationals.

What if l only paint those between 0.5 and 0.6, even leaving .53745 unpainted? Did I not paint an infinite number of numbers?

We turn in round here. You claim that if you can remove an infinite amount of elements from a set, the set will be empty - I claim there may remain some elements (and even more then removed, depending on circumstances). I suppose you apply a 'law' or a 'theorem'. Can you give me the (Wikipedia) reference?

[Molly Mae]

On 2/22/2018 at 6:49 PM, bonanova said:

Isn't this fun?

The { real numbers } between 0 and 1 comprise two infinite groups: { rationals } and { irrationals }. Rationals (expressible as p/q where p and q are integers) are countably infinite. We can order them, by placing them in an infinite square of p-q space and drawing a serpentine diagonal path. But the irrationals are not countable. The cardinality (notion of size used for infinite sets) of the rationals is called Aleph₀ and for the irrationals (and reals) it's called Aleph₁ or C (for continuum.)  So first off, what we can do with the { numbers } between 0 and 1 depends on { which numbers } we want to deal with.

Next, there's a problem that points are not objects that can be moved from place to place, as coins can. Points are more descriptions of space than of autonomous objects. If 0 and 1 are on a number line, the location midway between them is the point denoted by 0.5. It can't be removed. (We could erase the line, I guess, but that would not produce an interval [0 1] devoid of numbers, either.) But we can finesse this matter by "painting" a point. Kind of like what we did when we inscribed a number on each coin. Painting does a little less - it puts a point into a particular group or class but it does not distinguish among them.  We can tell coin 2 from coin 3 and also distinguish both from a coin with no inscription. Two blue points, however, are distinguishable from unpainted points, but not from each other. But for our purpose here, painting is actually enough.

Since the { rationals } are countable, we can paint them, in sequence, and if we do that at times of 1, 1/2, 1/4 .... minutes before midnight, all the rationals between 0 and 1 will be painted blue by midnight. (I don't know of a similar scheme for completing uncountable task sets, so the irrationals alas must remain unpainted.) Next, instead of asking whether all the points in [0 1] were removed, we can ask, with pretty much the same meaning, whether at this point the entire interval [0 1] has been painted blue. It should be, right? After all, between any two rationals lie countably infinite other rationals. So the paint must have covered the entire interval, right?. Well ... actually ... the answer is counter-intuitively No.

And this is because even though the { rationals } are "dense" meaning there are no "gaps" between them, as noted above, the { irrationals } are even "more dense." That is, between any two irrational numbers there are uncountably many other irrationals. That means, for every blue point we created in the interval [0 1] there are uncountably many unpainted points. We can't magnify the line greatly enough to "see" individual points, but "if we could," if we were lucky enough to come across a single blue point we'd have to pan our camera over uncountably many unpainted points before we saw another blue one. In measure theory, the measure of the rationals over any interval is zero. The measure of the irrationals over [0 1] is unity.

So what of our quest of emptying [0 1] of points? It's the same as our quest to paint [0 1] blue by painting all the rational numbers in that interval. (Reminding ourselves that there were too many irrationals to paint one at a time.) Turning again to measure theory, the measure of the "blueness" of the interval would be zero. That means we would not see even the hint of a faint blue haze.  Back to our "empty the interval by removing the rationals" quest, Nope. [0 1] would not be empty: uncountably many points (numbers) would remain.

NEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEERD!

This is actually great.  I learned something!  Explanations like this are the reasons I keep coming back to BD.  If I had the power, I'd give you a gold star.

[bonanova]

On 2/22/2018 at 9:18 AM, harey said:

Maybe an idea. There is an infinite number of numbers between 0 and 1. I have the opportunity to discard an infinite number of numbers between 0 and 1.

How much are you willing to bet that nothing remains between 0 and 1?

I just re-read this, and my reply wasn't totally responsive. But let's see whether Charlie even makes us address this question. Remember, Charlie doesn't get any more coins to deal with than Albert did. If we believe Albert's box (can) get emptied, we can't say discarding Charlie's coins is an impossible task. We simply have to show that none of Charlie's coins is able to "hide" indefinitely, in hopes of hearing the clock strike while still being in the box.

Charlie's coins are not inscribed, so we have to treat them collectively. We can't trace the destiny of any individual coin, as we could in Albert's case. Can we still show they are all eventually discarded, and not face the task of depleting an infinite set along the way? We claim that we can do that.

We can refer to each of Charlie's coins as "one of the coins that entered Charlie's box at event n that was also not discarded at event n." The n coins in his box at any such time are indistinguishably equivalent. Their "fate" is countably infinite events with non-zero probability of being discarded. We have shown in a preceding post that each of Charlie's coins has a survival probability of k/n where k is the event when the coin entered his box and n is the current event number. k is fixed. n becomes infinite. The probability of the coin that entered Charlie's box at event k still being in his box after midnight is limit (n->inf) k/n = 0. Since this holds for each k it holds for each coin that entered Charlie's box.

Using other words, every coin that is in Charlie's box at midnight is not a coin that entered Charlie's box. A contradiction.

Also, at no event time did Charlie have an infinite number of coins.