BrainDen.com - Brain Teasers
• 1

Grabbing marbles

Question

You are wearing gloves while trying to retrieve the marbles contained in a bag. Because of the gloves, you're doing a pretty poor job of it. With each grab, you are only able to retrieve a random number of marbles, evenly distributed between 1 and n, the number of marbles currently in the bag. With 30 marbles initially in the bag, how many grabs do you expect it will take to retrieve them all?

Recommended Posts

• 1
Spoiler

General idea: If we have n marbles, with p=1/n, we grab (n-k) marbles.
That gives one grab + number of grabs for the remaining k marbles.

Read "1/n Mk" as "after the first grab, with p=1/n, there remain k marbles"

1 marble
1/1 M0

2 marbles
1/2 M0 1/2 *  1
1/2 M1 1/2 * (1 + 1)
sum:   1/2 * (2 + 1) = 1 + 1/2 = 3/2

3 marbles
1/3 M0 1/3 *  1
1/3 M1 1/3 * (1 + 2/2)
1/3 M2 1/3 * (1 + 3/2)
sum:   1/3 * (3 + (2+3)/2) = 1 + 5/6 = 11/6

4 marbles
1/4 M0 1/4 *  1
1/4 M1 1/4 * (1 + 6/6)
1/4 M2 1/4 * (1 + 9/6)
1/4 M3 1/4 * (1 + 11/6)
sum:   1/4 * (4 + (6+9+11)/6) = 1 + 26/24 = 50/24

5 marbles
1/5 M0 1/5 *  1
1/5 M1 1/5 * (1 + 24/24)
1/5 M2 1/5 * (1 + 36/24)
1/5 M3 1/5 * (1 + 44/24)
1/5 M4 1/5 * (1 + 50/24)
sum:   1/5 * (5 + (24+36+44+50)/24) = 1 + 154/120

Numerator: n!

Denominator:
24=  24*(1)
36=  24*(1+1/2)
44=  24*(1+1/2+1/3)
50=  24*(1+1/2+1/3+1/4)
sum= 4!*(4+3/2+2/3+1/4)

In general: (n-1)! * (1/(n-1)+2/(n-2)+ +(n-1)/1)

Final formula: 1 + (1/(n-1)+2/(n-2)+ +(n-1)/1) / n

There is a formula for (1+1/2+1/3+1/4+  +1/n), but it does not work well for small n, so

for i1 in range(5,101,5):
z2=0
for i2 in range(1,i1):
z2=z2+i2/(i1-i2)
z2=1+z2/i1
print('{0:5d}'.format(i1),'{0:.6f}'.format(z2))

Output for some n:

5 2.283333
10 2.928968
15 3.318229
20 3.597740
25 3.815958
30 3.994987
35 4.146781
40 4.278543
45 4.394948
50 4.499205
55 4.593612
60 4.679870
65 4.759276
70 4.832837
75 4.901356
80 4.965479
85 5.025738
90 5.082571
95 5.136346
100 5.187378

Surprisingly low. I checked two times, hope there is not an error.

Share on other sites

• 0

That agrees with simulations I ran, which gave, approximately,

Spoiler

4, 10, 30, 84 and 244 (geometric series in e) as the number of marbles that require integer numbers 2, 3, 4, 5 and 6 grabs.
So if you multiply the number of marbles by e, it takes one more grab.

exp { 1.4  2.4  3.4  4.4  5.4 } =~ { 4  10  30  84  224 }.

That's interesting.

Nice solve.

Share on other sites

• 0
4 hours ago, bonanova said:

That agrees with simulations I ran, which gave, approximately,

Hide contents

4, 10, 30, 84 and 244 (geometric series in e) as the number of marbles that require integer numbers 2, 3, 4, 5 and 6 grabs.
So if you multiply the number of marbles by e, it takes one more grab.

exp { 1.4  2.4  3.4  4.4  5.4 } =~ { 4  10  30  84  224 }.

That's interesting.

... but not so surprising if you consider that the formula for (1+1/2+1/3+1/4+  +1/n) is ln(n)+0.5772156649. Adding exp to exp usually gives an exp, too.

Still, I wonder whether there is a formula for 1 + (1/(n-1)+2/(n-2)+ +(n-1)/1) / n .

Nice solve.

Thanks.

Share on other sites

• 0

I think this puzzle is exactly the same as the traffic jam puzzle I posted recently, although that's not obvious at first glance.

@plainglazed found a solution in which he formed clusters of cars by recursively locating the slowest of a group of cars, assuming on average it was in the center of the remaining cars. This corresponds to "grabbing" on average one-half of the remaining marbles from the bag. Picture the marbles in a line and, grabbing a random percentage of them starting from one end. This has to end up having the same number of marble grabs and car clusters. It leads to a logarithmic answer, but to the wrong base -- it should be the natural loge, not log2, which gives too large an answer. Instead of decreasing the number by 1/2 each grab, the remaining number is decreased by 1/e each grab. Same must go for locating the slowest of the remaining cars.

@plasmid found a solution that leads to Sum { 1/k }, which as you point out is ln { n } + gamma, and is here confirmed by simulation. What I can't find is a corresponding analysis for the marbles problem (although plainglazed's approach is applicable to both problems) that will lead to that same sum, instead of yours, where both sums appear to be correct.

This has been fun to think about.

.

Share on other sites

• 0
3 hours ago, bonanova said:

I think this puzzle is exactly the same as the traffic jam puzzle I posted recently, although that's not obvious at first glance.

@plainglazed found a solution in which he formed clusters of cars by recursively locating the slowest of a group of cars, assuming on average it was in the center of the remaining cars. This corresponds to "grabbing" on average one-half of the remaining marbles from the bag. Picture the marbles in a line and, grabbing a random percentage of them starting from one end. This has to end up having the same number of marble grabs and car clusters. It leads to a logarithmic answer, but to the wrong base -- it should be the natural loge, not log2, which gives too large an answer. Instead of decreasing the number by 1/2 each grab, the remaining number is decreased by 1/e each grab. Same must go for locating the slowest of the remaining cars.

@plasmid found a solution that leads to Sum { 1/k }, which as you point out is ln { n } + gamma, and is here confirmed by simulation. What I can't find is a corresponding analysis for the marbles problem (although plainglazed's approach is applicable to both problems) that will lead to that same sum, instead of yours, where both sums appear to be correct.

This has been fun to think about.

.

Though they are similar, I see at least one huge difference. In the traffic jam puzzle, you cut ANY part. In the marble problem, you cut the REMAINING part. Enough for different formulae.

Remains me of http://brainden.com/forum/topic/18168-squirrel/

Share on other sites

• 0
12 hours ago, harey said:

Though they are similar, I see at least one huge difference. In the traffic jam puzzle, you cut ANY part. In the marble problem, you cut the REMAINING part. Enough for different formulae.

The cars in front of the slowest car are the remaining cars. (Each slowest car captures those behind it.)

Share on other sites

• 0
On 3/25/2018 at 6:44 AM, bonanova said:

What I can't find is a corresponding analysis for the marbles problem (although plainglazed's approach is applicable to both problems) that will lead to that same sum, instead of yours, where both sums appear to be correct.

I see now: plainglazed's formula is the simplification of my formula I was so hard looking for. On paper, I got a kind of unreadable proof, so I fed them into my computer. Up to n=30, no difference with 6 decimals.

Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

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

×
• Recently Browsing   0 members

×

• Activity

• Riddles
×
• Create New...