Bag of Marbles
 

I have a bag containing twenty marbles, numbered 1 through 20.
Tbe bag has a hole in it, from which one marble falls at a time,
until all twenty marbles have fallen out, subject only to the condition
that the set of marbles that have fallen out at any time are always
numbered in a sequence with no gaps. For example, the first four
marbles to fall out might be 7,8,6,9, but not 7,8,5,9.

The question, of course, is:
In how many different ways can I lose all my marbles?

Can I assume from your explanation that sequence 7,8,9,5,6 would be invalid?

That's correct, 7,8,9,5,6 would be invalid since there would be
a gap (6) when the 5 fell out.

[spoiler]2^19.

The next marble must be either the top or the bottom of the range.

If "k" comes out first, the next 19 marbles will include k-1 that come at the bottom of the range. These bottom marbles can occur (k-1)C19 ways. So the total number of ways is 0C19 + 1C19 + .... 18C19 + 19C19. This sum is 2^19. Among the ways to see this is to observe that it is the binomial expansion of (1+1)^19.
[/spoiler]

[QUOTE=wblipp;115805][spoiler]2^19.

The next marble must be either the top or the bottom of the range.

If "k" comes out first, the next 19 marbles will include k-1 that come at the bottom of the range. These bottom marbles can occur (k-1)C19 ways. So the total number of ways is 0C19 + 1C19 + .... 18C19 + 19C19. This sum is 2^19. Among the ways to see this is to observe that it is the binomial expansion of (1+1)^19.
[/spoiler][/QUOTE]

Right idea, but you neglected to consider [spoiler]the special case of the first marble which is unconstrained.

The correct answer is 20 * 2^18[/spoiler].

[QUOTE=Mr. P-1;115808]Right idea, but you neglected to consider [spoiler]the special case of the first marble which is unconstrained.[/spoiler][/QUOTE]

I don't think so. The first marble can be any one of the twenty marbles. This was considered in my solution [spoiler]by the twenty terms in the sum. The first term, 0C19, is the total numbers of ways given the first ball is #1 (1 way). The second term, 1C19, is the total number of ways given the first ball is #2 (19 ways). etc.[/spoiler]

As further argument in favor of my answer, I note that it's easy to enumerate the ways for 3 marbles. There are four arrangements:

1 2 3
2 1 3
2 3 1
3 2 1

William

My answer is correct only if the sequence is permitted to 'wrap' from 20 to 1 and vice versa. Since a reasonable reading of the problem doesn't permit 'wrapping', my answer is wrong. I failed to consider the edge cases in which 1 or 20 has already been reached.

On re-reading your solution, it looks correct, though (scrabbling for a face-saving excuse here) I don't think you explained it very well.

If we allow wrapping then given the first marble, there are
two distinct ways of choosing each of the next 18.
I am trying to use this as a simple derivation of William's result
without immediate success.

David

Think I've done it:
[spoiler]
Consider the 20 rotations of a particular ordering with wrapping.
The only rotations which do not invoke wrapping are those which
end with 1 or 20. So we have 20*2^18*(2/20).

[/spoiler]

No that won't do. Not all rotations of a legitimate
ordering are legitimate themselves:sad:

But we do get a legitimate ordering by adding 1 to the
number of each marble in a legitimate ordering (20+1 = 1).
I think my original argument applies to these 20 different
orderings.

Nice catch and nice resolution.

[spoiler]
Consider the general case of k marbles numbered 1 through k. Let S(k, n) be the number of ways to lose k marbles with the n-th marble being "1" and S(k) be the total number of ways to lose k marbles, then

S(k) = S(k, 1) + S(k, 2) + ... + S(k, k)

Note S(k + 1, n) = S(k, n), hence for k >= n, S(k,n) = S(n,n) (for k<n, S(k,n) = 0)

Note S(n, n) = S(1,1) + S(2, 2) + ... + S(n-1,n-1)

So S(k+1) = S(k) + S(k+1, k+1) = 2*S(k)

Since S(1) = 1, this means S(20) = 2^20
[/spoiler]

hrm. meh, somewhere I wasn't careful enough and I like wblipp's answer too much to go fix mine.

[quote=davieddy;115828]If we allow wrapping, then given the first marble, there are two distinct ways of choosing each of the next 18.
[/quote]

[spoiler]
Wrapping is not invoked iff the last number is 1 or 20,
giving 2 possibilities for the first marble.
So number of ways is 2*2^18.
[/spoiler]

[quote=Orgasmic Troll;115837]
hrm. meh, somewhere I wasn't careful enough and I like wblipp's answer too much to go fix mine.[/quote]
Yes I was convinced by William's solution as well.
For completeness I would like to "fix" your solution,
but if you can't be bothered, even with the added advantage of
(presumably) understanding what you meant in the first place,
then we may have some work to do:lol:
David

[quote=wblipp;115836]Nice catch and nice resolution.[/quote]
THX William. Does "catch" refer to my original error or the spotting
of it (or both)?
David

[QUOTE=davieddy;115839][spoiler]
Wrapping is not invoked iff the last number is 1 or 20,
giving 2 possibilities for the first marble.
So number of ways is 2*2^18.
[/spoiler][/QUOTE]

I don't see how you got from limitations on the last marble to limitations on the first marble. I liked your solution I called "nice resolution." In greater detail for those that may have missed it that argument runs:

[spoiler]There are 20 * 2^18 valid sequences with wrapping. All those sequences that end with 1 or 20 are also a valid sequence without wrapping. If we were sure that the last ball was equally likely, we would conclude the non-wrapped sequences are 2/20 of the wrapped sequences.

Consider the mapping of sequences that changes the number of every ball from n to (n+1) mod 20. The new sequence is a valid wrapping sequence, and distinct sequences map to distinct sequences, so the image of the wrapping sequences is the entire set of wrapping sequences. Consider doing this 20 times, and we have 20 copies of the wrapping sequences. In this collection the last ball is a 1 or 20 2/20 of the time because every wrapping sequence has 20 images, and all 20 choices for last ball show up once. But the images are all identical, so 2/20 must also apply to each image, and each image is the complete set.[/spoiler]

[quote=wblipp;115847]I don't see how you got from limitations on the last marble to limitations on the first marble. [/quote]
In my attempt at brevity I omitted that I was considering
each of the "top/bottom" marble sequences separately.
For any given sequence, adding one to the first marble adds one
to the last. Hence the connection between the limitations.
I am glad you understood my "nice resolution" although my
ability to present an argument rigorously isn't up to yours:smile:

David

PS I think the largest hole to be filled is my assertion that
no wrapping need be invoked iff the last marble is 1 or 20.

To misquote the late and lamented Mally:
Perhaps Davar55 could step in at this juncture, and
tell us how we are getting on:smile:

David

[QUOTE=davieddy;115850]PS I think the largest hole to be filled is my assertion that
no wrapping need be invoked iff the last marble is 1 or 20.[/QUOTE]

The last marble completes both the ascending and descending subsequences (with wrapping).

Therefore if the last marble is 1 the immediately prior descending subsequence is ..., 4, 3, 2. The immediately prior ascending subsequence is ..., 18, 19, 20.

Clearly wrapping hasn't occurred in either subsequence before the 1 was dropped. A similar argument applies when the last marble is 20.

We also need to show that a last marble other than 1 or 20 implies an previously wrapping subsequence. In this case, suppose the last marble is less than the starting marble. The number 1 cannot have been reached in the descending subsequence without the final marble having dropped earlier. Therefore it must have been reached when the ascending subsequence wrapped earlier. A similar argument applies with the number 20 when the last marble is greater than the starting marble.

[QUOTE=davieddy;115844]Yes I was convinced by William's solution as well.
For completeness I would like to "fix" your solution,
but if you can't be bothered, even with the added advantage of
(presumably) understanding what you meant in the first place,
then we may have some work to do:lol:
David[/QUOTE]

hah, I looked back at what the problem was, and it's a very minor error right at the end. If you have a function f(n), where f(n+1) = 2*f(n) and f(1) = 1, then f(n) = 2^(n-1), not 2^n.

So it's all good :)

As best I can tell, all three arguments given are valid,
and the correct answer is indeed [spoiler]2^19[/spoiler].

There is another way of getting this.
[spoiler]
Consider the REVERSE of any valid sequence. This must begin
with either 1 or 20, two possibilities. For either possibility, the
next number has again exactly two possibilities that avoid a gap. And so on, until the penultimate number has two possibilities.
But the final number will then be determined uniquely. So the
total number of valid reverse sequences is 2x2x2x...x2x1 = 2^19. Each corresponds to one valid forward sequence.
[/spoiler]

[QUOTE=davar55;115948][spoiler]
Consider the REVERSE of any valid sequence. ... For either possibility, the next number has again exactly two possibilities that avoid a gap. And so on,
[/spoiler][/QUOTE]

Neat!

[spoiler] When disassembling, the remaining balls always form a contiguous block, and next ball removed must come from one end of the block. Davieddy and I both struggled for clever ways to account for hitting one of the boundaries when growing. That whole question goes away on disassembly.[/spoiler]

Thanks Davar.

I hope it is worth pointing out that an easy way of seeing
that 0C19 + 1C19 + 2C19 +.....+ 19C19 = 2^19 is that the
left hand side is a way of counting all 19 bit numbers.

David

It helps to think of placing the marbles which fall out in an
ordered line so that we end up with a line 1,2,3,.....20.