Squirrel

[harey]

A large colony of squirrels dug holes during the summer and in each hole, they put between 1 and 100 nuts (each quantity has the same probability).

If each squirrel has to eat 100 nuts during the winter, how many holes must he find (in average)?

Each hole contains 50.5 in average, so 2 should be enough, right?

[bonanova]

There is survival in numbers.

Spoiler

Say the colony numbered N squirrels, and they each dug up 2 holes.

They would create N piles of nuts whose average size is 101 and whose standard deviation is about 40.
So if they share among themselves, they will all get through the winter.
If each eats only what s/he finds, maybe only 2/3 of them will survive.

 

[harey]

2 hours ago, bonanova said:

There is survival in numbers.

  Hide contents

Say the colony numbered N squirrels, and they each dug up 2 holes.

They would create N piles of nuts whose average size is 101 and whose standard deviation is about 40.
So if they share among themselves, they will all get through the winter.
If each eats only what s/he finds, maybe only 2/3 of them will survive.

 

Nice try, but they do not share and they survive all.

Hint:

Spoiler

Very few will find 100 nuts and do not dig a second hole.
Some will find find 100 nuts in two holes and do not dig a third hole.
How many will dig a third hole? And a fourth?

 

[bonanova]

9 hours ago, harey said:

Nice try, but they do not share and they survive all.

Hint:

  Hide contents

Very few will find 100 nuts and do not dig a second hole.
Some will find find 100 nuts in two holes and do not dig a third hole.
How many will dig a third hole? And a fourth?

 

Spoiler

One million simulations:

# holes  % of squirrels that find 100+ nuts in their holes

1 hole    1.01%
2 holes  50.40%
3 holes  32.85%
4 holes  11.98%
5 holes   3.04%
6 holes   0.60%
7 holes   0.10%
8 holes   0.01%
9+ holes  0.00%

Spoiler

Every hole has a 1% chance of containing a single nut.
If you want to guarantee all squirrels survive, they must each dig up 100 holes

 

[bonanova]

I guess we can compute expectation value as well:

Spoiler

E = Sum_k { outcome_k } x { probability of outcome_{k }}

One million simulations:

# holes       %  prob      product
----------------------------------
1 hole    1.01%  0.0101    0.0101
2 holes  50.40%  0.5040    1.0079
3 holes  32.85%  0.3285    0.9856
4 holes  11.98%  0.1198    0.4790
5 holes   3.04%  0.030427  0.1521
6 holes   0.60%  0.006024  0.0361
7 holes   0.10%  0.000993  0.0070
8 holes   0.01%  0.000125  0.0010
9+ holes  0.00%  0.000021  0.0002
                           ======
                           2.6792  

 

 

[harey]

3 hours ago, bonanova said:

I guess we can compute expectation value as well:

  Hide contents

E = Sum_k { outcome_k } x { probability of outcome_{k }}

One million simulations:

# holes       %  prob      product
----------------------------------
1 hole    1.01%  0.0101    0.0101
2 holes  50.40%  0.5040    1.0079
3 holes  32.85%  0.3285    0.9856
4 holes  11.98%  0.1198    0.4790
5 holes   3.04%  0.030427  0.1521
6 holes   0.60%  0.006024  0.0361
7 holes   0.10%  0.000993  0.0070
8 holes   0.01%  0.000125  0.0010
9+ holes  0.00%  0.000021  0.0002
                           ======
                           2.6792  

 

 

A big step forward. Now that we found the result, it remains to find the way to find the result.

Spoiler

 

When I do simulations, a much lower number of iterations is sufficient (originally, we simulated it on Univac 1108 -  it would have calculated for days). However, it is paying to try different rising n, it gives an idea (sometimes misleading, I agree) where the sums and the terms converge.

I can compute how many squirrels need to dig just two holes:

    |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |
  --+--------------------------------------------+
  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 |
  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 |
  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 |
  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 |
  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 |
  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
  9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
  --+--------------------------------------------+

(n*n)/2: the part of the square under the diagonal (the diagonal becomes meaningless for large n).

Unfortunately, such a table is much harder to construct for the third dig.

For n=3, it is imaginable to place the number of dig nuts in 3D, but for 4 nuts, I surrender.

 

 

Edited March 28, 2018 by harey
cosmetics

[bonanova]

On 3/25/2018 at 4:52 AM, harey said:

A large colony of squirrels dug holes during the summer and in each hole, they put between 1 and 100 nuts (each quantity has the same probability).

If each squirrel has to eat 100 nuts during the winter, how many holes must he find (in average)?

Each hole contains 50.5 in average, so 2 should be enough, right?

I guess I've always been a little confused about what is being asked.

Sharing is not permitted, yet an "average" result is requested. If average values are used, then two holes is enough. If there is no sharing or averaging, survival is assured only by the (very unlikely) worst case of 100 holes. If the question is what is the expected number of holes that together yields at least 100 nuts, we have an answer from simulation.

Is there a way to say precisely what else might be needed?