Mac loves Ice-cream

Probability Level 3

Our friend Mac likes to eat ice-cream so much that he started to work in an ice-cream parlor. Satisfied by his work, the ice-cream owner gave him 10 different kind of ice-cream each 2 in quantity(20 ice-creams in total). Mac have gone crazy so much that he brought a fair 10 sided dice and devised the following ice-cream eating algorithm : -

  • Label the 20 ice-creams with number 1 to 10 based on the type of ice-cream.

  • Roll the 10 sided dice. Let the number obtained be n.

  • If there is any ice-cream of type n remaining, eat it. Else do nothing.

  • If the ice-cream lot is not finished, repeat the above steps from step 2.

What is the expected number of dice rolls he will have to do to finish eating his ice-creams?


The answer is 46.229570639448156.

Mayank Chaturvedi by Mayank Chaturvedi , 21, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Kyle T
May 30, 2019

not necessarily a solution, but an approximation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
<?php
$flavors = 10;
$quantity = 2;
$trials = 1000000;

$s = array();
for($a=0;$a<$trials;$a++){
    $b = array();
    for($i=0;$i<$flavors;$i++){
        $b[$i] = $quantity;
    }
    $n = 0;
    do {
        $r = mt_rand(0,$flavors-1);
        if(isset($b[$r])){
            $b[$r]--;
            if(!$b[$r]){
                $b = array_filter($b);
            }
        }
        $n++;
    } while(!empty($b));
    $s[] = $n;
}
echo array_sum($s)/count($s);
//printed: 46.223 (actual answer 46.229)
?>

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Amazing simulation @Kyle Tripp. If one wants a solution using a computer program, recursion could also be used to do so.

let f ( a , b ) f(a,b) be the expected number of dice rolls required to finish ice-cream such that there are 'a' type of ice-creams with only one quantity left each and 'b' type of ice-creams with two quantities left each then the following equation follows:- f ( a , b ) = b 10 ( 1 + f ( a + 1 , b − 1 ) ) + a 10 ( 1 + f ( a − 1 , b ) ) + 10 − a − b 10 ( 1 + f ( a , b ) ) f(a,b)=\frac{b}{10}(1+f(a+1,b-1))+\frac{a}{10}(1+f(a-1,b))+\frac{10-a-b}{10}(1+f(a,b)) we get the recursion below:- a + b 10 f ( a , b ) = b 10 f ( a + 1 , b − 1 ) + a 10 f ( a − 1 , b ) + 1 \frac{a+b}{10} f(a,b)=\frac{b}{10}f(a+1,b-1)+\frac{a}{10}f(a-1,b)+1 which could be solved efficiently using dynamic programming. Let me know if this is right

Mayank Chaturvedi - 2 years ago

Log in to reply

This is a nice idea. Have you managed to get it to work? You need a bit more than you've written here to actually get an answer out. I'm not sure of the best way to describe this, but I'll try! The relation you've written down allows you to write f ( a , b f(a,b in terms of f ( a + 1 , b − 1 ) f(a+1,b-1) and f ( a − 1 , b ) f(a-1,b) .

If you imagine the a , b a,b values as lattice points on a plane, the relation you found gives you a way to move around the plane. The idea is to start at ( a , b ) = ( 0 , 10 ) (a,b)=(0,10) (the problem setup) and move around the plane until we end up somewhere we can actually evaluate f f . Then we can work out f ( 0 , 10 ) f(0,10) from there.

So for this to work, you need to know a little more about f f .

One thing that helps is that it's easy to find f ( a , 0 ) f(a,0) : this is the simpler problem where you only need each value to come up once, and it has the solution f ( a , 0 ) = 10 ∑ i = a 10 1 i f(a,0)=10\sum_{i=a}^{10} \frac{1}{i} (by the way, this is known as the coupon collector's problem .

So if we can "steer" the point ( a , b ) (a,b) towards the line b = 0 b=0 , we can solve the problem.

The difficulty is, the b b parameter only reduces in one term of the relation you found. Without some other relationship or known f f values, I'm not sure it's possible to steer things exactly as we'd like.

Anyway, please post a solution or a follow-up comment if you get somewhere this way!

Chris Lewis - 2 years ago

Log in to reply

That is true. We need a base case to begin with, of which most helpful would be f(1,0)=10 (solved by constructing a gp series). We can choose f(1,0) to be base case since every f(a,b) could be reduced to some expression in f(1,0) following a series of recursion. Following code follows the recursion and completes the work. 

1
2
3
4
5
6
7
8
 
#python
variety=10
def f(one,two):
    if one==1 and two==0:
        return variety
    answer=(((two/(one+two))*f(one+1,two-1))+((one/(one+two))*f(one-1,two))+(variety/(one+two)))
    return answer
print(f(0,variety))  #prints 46.22957063944817

Mayank Chaturvedi - 2 years ago

Log in to reply

@Mayank Chaturvedi – That's awesome, well done! You should write this up as a solution. It's great that there are (so far) three different approaches listed here! (Simulation, recursion and - via a link - a general, analytical method.) I think I like yours best as it gets an exact solution (if you wanted to, you could use fractions in your method), but doesn't do too much.

Thanks for the fun problem, by the way.

Chris Lewis - 2 years ago

Log in to reply

@Chris Lewis – Thank you Chris glad you found the problem interesting. I will post the solution soon.

Mayank Chaturvedi - 2 years ago
Chris Lewis
May 30, 2019

This is the Double Dixie Cup problem .

Using the notation of the linked paper, the expected number of dice rolls is

E 2 ( 10 ) = 10 ∫ 0 ∞ [ 1 − ( 1 − ( 1 + t ) e − t ) 10 ] d t E_2(10)=10 \int_0^{\infty} \left[ 1-\left(1-(1+t)e^{-t} \right)^{10} \right] dt

The integrand can be expanded using the Binomial theorem and integrated termwise. Doing this by hand would be somewhat tedious; lots of integration by parts, though doing this exercise for smaller n n at least shows we expect a rational result. Enlisting the help of Wolfram|Alpha, we find

E 2 ( 10 ) = 335641897646511216668163083 7260329114112614400000000 = 46.22957 … E_2(10)=\frac{335641897646511216668163083}{7260329114112614400000000}=\boxed{46.22957\ldots}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...