wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Summing Up Dice
        
(Message started by: Virgilijus on May 19^th, 2015, 6:02am)

Title: Summing Up Dice
Post by Virgilijus on May 19^th, 2015, 6:02am

Willy Wutang is playing Dungeons & Dragons with a few of his nerdier friends and has come across a problem: in order to steal gold coins from a sleeping dragon, he needs to roll a 100 sided dice. Every time he rolls the dice and the sum of all his past rolls and his current roll adds up to less than 100, he will successfully steal a gold coin. If, however, the sum of his rolls adds up to 100 or more, he will alert the dragon, it will wake up and undoubtedly kill him and his entire party, effectively ruining their nerdy evening.

Willy, being as clever as he is immoral and selfish, wants to know how many coins he should try to steal. What, approximately, is the average amount of rolls he could make before alerting the dragon? What if he had a (countably) infinitely sided dice?

Title: Re: Summing Up Dice
Post by rmsgrey on May 19^th, 2015, 9:38am

Far from a complete solution, but a rough indication:

Over two rolls, the expected total is 101, so there's a less than 50% chance of getting a second coin, let alone getting further.

So, just off the top of my head, I'd say, if he has to pick his number of tries in advance, in order to maximise his monetary gain, he should settle for just the one coin (at a 99% chance of success).

If he's allowed to choose whether to keep going or stop after each roll, then, on purely financial grounds, he should make the nth roll only when his current rolled total is less than 100/n.

Of course, if you take account of the cost of failure being very large, then the optimal strategy is to walk away with nothing rather than take the 1% chance of disaster...

Title: Re: Summing Up Dice
Post by Virgilijus on May 19^th, 2015, 2:54pm

on 05/19/15 at 09:38:24, rmsgrey wrote:

If he's allowed to choose whether to keep going or stop after each roll, then, on purely financial grounds, he should make the nth roll only when his current rolled total is less than 100/n.

For this problem, let's say he has to decide upon the number of total rolls before he rolls the first die :^)

Title: Re: Summing Up Dice
Post by markr on May 19^th, 2015, 11:56pm

Here's what I get:
100 : 2.67803349448
200 : 2.69802698799
300 : 2.70474932685
400 : 2.70812144078
500 : 2.7101482242
600 : 2.71150088075
700 : 2.71246778375
800 : 2.71319335499
900 : 2.7137579218
1000 : 2.71420972251

Looks like it approaches e.

Title: Re: Summing Up Dice
Post by Virgilijus on May 20^th, 2015, 1:36am

on 05/19/15 at 23:56:26, markr wrote:

Looks like it approaches e.

[hide]Indeed, it does approach e! But can you prove it :^)[/hide]

Title: Re: Summing Up Dice
Post by towr on May 20^th, 2015, 11:11am

[hide]
Let's say F(M, N) is the expected number of throws you need to get a sum greater or equal to M on an N-sided die. We're looking for F(N, N), with N=100 or going to infinity.

F(1, N) = 1
F(M, N) = 1 + sum(i=1..M-1, F(i, N))/N {at least one throw, plus whatever we need to finish any remainders }
=>
F(M, N) = (1+1/N) * F(M-1, N)
=>
F(M, N) = (1+1/N)^M-1

so F(N, N) = (1+1/N)^N-1

And it's well known that lim_N->inf (1+1/N)^N = e, the constant difference in the exponent becomes irrelevant as we go to infinity, lim_N->inf (1+1/N)^N = lim_N->inf (1+1/N)^N-C for any constant C.
[/hide]

Title: Re: Summing Up Dice
Post by Virgilijus on May 20^th, 2015, 2:16pm

Excellent! A much more concise proof than my method :^)