Grabbing marbles

[bonanova]

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?

[harey]

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.

 

[bonanova]

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.

[harey]

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.

 

[bonanova]

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 log_e, not log₂, 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.

.

[harey]

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 log_e, not log₂, 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/

[bonanova]

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

[harey]

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.