Bag of Marbles

[davieddy]

Originally Posted by davieddy

If we allow wrapping, then given the first marble, there are two distinct ways of choosing each of the next 18.

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.

[davieddy]

Originally Posted by Orgasmic Troll

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

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
David

[davieddy]

Originally Posted by wblipp

Nice catch and nice resolution.

THX William. Does "catch" refer to my original error or the spotting
of it (or both)?
David

[wblipp]

Originally Posted by davieddy

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.

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:

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.

[davieddy]

Originally Posted by wblipp

I don't see how you got from limitations on the last marble to limitations on the first marble.

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

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.

[davieddy]

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

David

[Mr. P-1]

Originally Posted by davieddy

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.

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.

[Orgasmic Troll]

Originally Posted by davieddy

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
David

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 :)

[davar55]

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

There is another way of getting this.

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.

[wblipp]

Originally Posted by davar55

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,

Neat!

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.

[davieddy]

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