Author |
Topic: Summing Up Dice (Read 505 times) |
|
Virgilijus
Newbie
Gender: 
Posts: 11
|
 |
Summing Up Dice
« on: May 19th, 2015, 6:02am » |
 Quote  Modify
|
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?
|
| « Last Edit: May 19th, 2015, 2:48pm by Virgilijus » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: Summing Up Dice
« Reply #1 on: May 19th, 2015, 9:38am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
Virgilijus
Newbie
Gender:
Posts: 11
|
|
Re: Summing Up Dice
« Reply #2 on: May 19th, 2015, 2:54pm » |
Quote Modify
|
on May 19th, 2015, 9:38am, 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 :^)
|
| « Last Edit: May 19th, 2015, 2:54pm by Virgilijus » |
IP Logged |
|
|
|
markr
Junior Member
Gender:
Posts: 90
|
|
Re: Summing Up Dice
« Reply #3 on: May 19th, 2015, 11:56pm » |
Quote Modify
|
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.
|
| « Last Edit: May 19th, 2015, 11:59pm by markr » |
IP Logged |
|
|
|
Virgilijus
Newbie
Gender:
Posts: 11
|
|
Re: Summing Up Dice
« Reply #4 on: May 20th, 2015, 1:36am » |
Quote Modify
|
on May 19th, 2015, 11:56pm, markr wrote:
Looks like it approaches e.
|
|
Indeed, it does approach e! But can you prove it :^)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Summing Up Dice
« Reply #5 on: May 20th, 2015, 11:11am » |
Quote Modify
|
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 limN->inf (1+1/N)N = e, the constant difference in the exponent becomes irrelevant as we go to infinity, limN->inf (1+1/N)N = limN->inf (1+1/N)N-C for any constant C.
|
| « Last Edit: May 20th, 2015, 11:19am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Virgilijus
Newbie
Gender:
Posts: 11
|
|
Re: Summing Up Dice
« Reply #6 on: May 20th, 2015, 2:16pm » |
Quote Modify
|
Excellent! A much more concise proof than my method :^)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print