bonanova 85 Posted January 23, 2013 Report Share Posted January 23, 2013 You throw m fair six-sided dice and bet that all numbers from 1 to 6 will show at least once. What is the smallest value of m that gives you a winning bet on average? Quote Link to post Share on other sites

0 Solution superprismatic 11 Posted January 23, 2013 Solution Report Share Posted January 23, 2013 Lucky 13 1 Quote Link to post Share on other sites

0 TimeSpaceLightForce 12 Posted January 23, 2013 Report Share Posted January 23, 2013 m=(50% )(6^6) / 6(6P6) Quote Link to post Share on other sites

0 TimeSpaceLightForce 12 Posted January 23, 2013 Report Share Posted January 23, 2013 Comb(m,6)*permut(6,6)/(6^6) = avarage m=8 Comb(8,6) =28 Permut(6,6) =720 possible w/1-6=20160 no. of ways /comb : 6^6 =46656 win chance=43.2% Quote Link to post Share on other sites

0 Prime 15 Posted January 24, 2013 Report Share Posted January 24, 2013 (edited) I can get an answer, but no simple explanation. But that should do for everyday gambling needs. It's relatively easy to calculate in a spreadsheet. For m=13, the winning chance is approximately 0.51. For m=12, it's about 0.44. The probability to see just one and the same number after n rolls is 1/6^{n-1}. The probability P(k,n) to get exactly k different numbers (1 < k <= 6) after n rolls is P(k,n-1)*k/6 + P(k-1,n-1)*(7-k)/6. Make a 6-column table for k=1 through 6. Populate the first row with 1,0,0,0,0,0. The second row with the formulas above. Then drag the formulas down. I can't think at the moment of a simple formula instead of all that. Edited January 24, 2013 by Prime 1 Quote Link to post Share on other sites

0 bonanova 85 Posted January 25, 2013 Author Report Share Posted January 25, 2013 I can get an answer, but no simple explanation. But that should do for everyday gambling needs.It's relatively easy to calculate in a spreadsheet.For m=13, the winning chance is approximately 0.51. For m=12, it's about 0.44.The probability to see just one and the same number after n rolls is 1/6^{n-1}.The probability P(k,n) to get exactly k different numbers (1 < k <= 6) after n rolls is P(k,n-1)*k/6 + P(k-1,n-1)*(7-k)/6.Make a 6-column table for k=1 through 6. Populate the first row with 1,0,0,0,0,0. The second row with the formulas above. Then drag the formulas down.I can't think at the moment of a simple formula instead of all that. Ah, but there is one. No correct answers yet. Quote Link to post Share on other sites

0 superprismatic 11 Posted January 26, 2013 Report Share Posted January 26, 2013 I can get an answer, but no simple explanation. But that should do for everyday gambling needs.It's relatively easy to calculate in a spreadsheet.For m=13, the winning chance is approximately 0.51. For m=12, it's about 0.44.The probability to see just one and the same number after n rolls is 1/6^{n-1}.The probability P(k,n) to get exactly k different numbers (1 < k <= 6) after n rolls is P(k,n-1)*k/6 + P(k-1,n-1)*(7-k)/6.Make a 6-column table for k=1 through 6. Populate the first row with 1,0,0,0,0,0. The second row with the formulas above. Then drag the formulas down.I can't think at the moment of a simple formula instead of all that. Ah, but there is one. No correct answers yet. Since I got my answer using Prime's method, I'll now consult Strunk and White to see what else the OP could possibly mean. Possibly a weighted average m? Anyway, I must look in the basement for that copy of Strunk and White which I know is down there somewhere. Quote Link to post Share on other sites

0 phil1882 13 Posted January 26, 2013 Report Share Posted January 26, 2013 i also get 13 by running simulations. Quote Link to post Share on other sites

0 plainglazed 67 Posted January 26, 2013 Report Share Posted January 26, 2013 this was an expected value problem with the expected number of rolls needed to get all six numbers equal to the sum of the expected number of rolls needed to get each new number. The average number of rolls to roll a new number being the inverse of the probability to roll a new number. So 14.7? Quote Link to post Share on other sites

0 bonanova 85 Posted January 26, 2013 Author Report Share Posted January 26, 2013 Yes. Simple concept that cuts thru all the computational complexity. Quote Link to post Share on other sites

0 superprismatic 11 Posted January 26, 2013 Report Share Posted January 26, 2013 this was an expected value problem with the expected number of rolls needed to get all six numbers equal to the sum of the expected number of rolls needed to get each new number. The average number of rolls to roll a new number being the inverse of the probability to roll a new number. So 14.7? Please explain further. I can't parse this in any sensible way. Quote Link to post Share on other sites

0 phil1882 13 Posted January 26, 2013 Report Share Posted January 26, 2013 you have a 100% chance of rolling a number 1-6 with 1 dice. you have 5/6 of a chance of rolling a new number with the next dice. you have 4/6 of a chance of rolling a new number with the next dice. and so on. so the number of dice required is 6/6 +6/5 +6/4 +6/3 +6/2 +6/1 = 14.7 Quote Link to post Share on other sites

0 Prime 15 Posted January 26, 2013 Report Share Posted January 26, 2013 (edited) this was an expected value problem with the expected number of rolls needed to get all six numbers equal to the sum of the expected number of rolls needed to get each new number. The average number of rolls to roll a new number being the inverse of the probability to roll a new number. So 14.7? Yes. Simple concept that cuts thru all the computational complexity. This concept, does not apply to the question in the OP. The problem called for finding the minimum number of rolls (or dice) to get a winning bet. A winning bet is one, where your probability of winning is better than 0.5. It is not the same concept as average number of rolls (dice) required to get to the objective. A simple example: If you roll repeatedly a fair dice, then any given number, say "1", will occur on average once in six rolls. However, if I bet on "1" coming up just after 4 rolls or sooner, I am going to come out ahead. (Same as rolling 4 dice and betting that at least one of them will roll "1".) P = 1 - (5/6)^{4} = 0.5177 The answer to the problem as stated is like Sp and myself have found. I have another equation, which is not recursive, but encompasses all variations. It yields the same result. I'll make a separate post for it. But of course you still get a winning bet with 14.7 rolls. Your winning chance is better than 60%, but it is not the minimum number of rolls. Edited January 26, 2013 by Prime 1 Quote Link to post Share on other sites

0 Prime 15 Posted January 26, 2013 Report Share Posted January 26, 2013 The bottom line, the ultimate truth for calculation of a probability is the number of all variations that meet your criteria divided by the number of all possible variations. Note, m dice and m consecutive rolls are the same thing for the purposes of this problem. The number of all possible variations for m dice is 6^{m}. The number of variations where all 6 numbers show is more difficult to express. The simplest I came up with is an exponential function with 6 terms. I find it by induction. Let f(k) be an expression for the number of variations, in which all k different numbers (die faces) are present after rolling m dice. (Exactly k, no more, no less.) f(1) = 1^{m} = 1; f(2) = 2^{m} - _{2}C_{1}*f(1); (subtracting all variations of less than 2 different numbers.) f(3) = 3^{m}^{}- _{3}C_{2}*f(2) - _{3}C_{1}; ..... and so on... f(6) = 6^{m}^{}- _{6}C_{5}*f(5) - _{6}C_{4}*f(4) - _{6}C_{3}*f(3) - _{6}C_{2}*f(2) - _{6}C_{1} After substitution and simplification, we get:f(6) = 6^{m}^{}- 6*5^{m} + 15*4^{m} - 20*3^{m} + 15*2^{m} - 6. (If I did not mess up anywhere.) Dividing that by 6^{m} and trying different m-s, I come up with the same results as with the recursive formula from my earlier post. #rolls Probability 6 ....... 0.015432 7 ....... 0.054012 8 ....... 0.114026 9 ....... 0.189043 10 ..... 0.271812 11 ..... 0.356206 12 ..... 0.437816 13 ..... 0.513858 14 ..... 0.582845 15 ..... 0.644213 16 ..... 0.698004 It is possible, a simpler and better expression for all k numbers showing in m trials exists in math literature. Alas, I don’t read literature. Though, I’d be interested to know if someone finds something on the subject. To sum up: Ask for 13 dice and you should have a slight winning chance. For the gamblers who are convinced it is 14.7 rolls, I can give slight handicap and bet on 14. Quote Link to post Share on other sites

0 bonanova 85 Posted January 26, 2013 Author Report Share Posted January 26, 2013 Prime, that analysis is convincing. Consider the following as well. I wonder, in light of your betting on "1" appearing in just four die rolls means we should be looking at median outcomes rather than average. Since dice rolls are independent, rolling m dice once and one die m times will give indistinguishable results. OP thus asks: On average, how many rolls of a single die are required to get all six results? Betting on a smaller number loses, on average; a greater number gives a win. The "waiting time" to expect a particular result [measured in actual time, or (more often) in number of trials] is simply the reciprocal of the probability of obtaining the result in unit time, or in a single trial. In the present case the reciprocal probabilities for the 1st, 2nd, 3rd, ..., 6th distinct value to appear are, trivially, 6/6, 6/5, 6/4, 6/3, 6/2, and 6/1, which sum to 14.7 trials. The partial sums of this sequence, with obvious interpretations, are: 1, 2.2, 3.7, 5.7, 8.7, 14.7. Since simulation is the method de rigueuer, and I avoid complicated formulas when possible, I love simulations, I simulated a million rolls of 100 dice [to ensure all six face values would be obtained.] I counted into each 100-vector string of values until I encountered 1, then 2, then 3, then 4, then 5, and finally 6 distinct die values. This models rolling a die multiple times until these result are obtained. I then averaged the counts. Here are the results: 1 2.20138 3.70155 5.69817 8.70078 14.70568 On the other hand, all six values appear more than half the time in 13 rolls of a die. Quote Link to post Share on other sites

0 Prime 15 Posted January 26, 2013 Report Share Posted January 26, 2013 (edited) You throw m fair six-sided dice and bet that all numbers from 1 to 6 will show at least once. What is the smallest value of m that gives you a winning bet on average? That's the OP. A computer, or real life simulation of this simply and economically stated probability problem must be simple and straightforward. I look at it as a gambling game, where I can bet $1 on the outcome. Roll 13 dice. If they have all 6 numbers -- add one for me, if not -- one for you. Do it 100,000 times and see who wins. The correct answer to the problem in OP is 13. That's the minimum number of dice that gives better than 1/2 winning chance. Average number of trials for getting the result R of probability P is 1/P. Probability of getting R after 1/P trials is not equal to 1/2. For a large 1/P that probability tends to 1 - 1/e. Example: it takes on average 6 rolls of a fair die to roll "1". Probability of rolling "1" in 6 trials (or earlier) is 1 - (5/6)^{6} = 0.6651 (almost 2/3). Edited January 26, 2013 by Prime Quote Link to post Share on other sites

0 bushindo 14 Posted January 26, 2013 Report Share Posted January 26, 2013 Prime, that analysis is convincing. Consider the following as well.I wonder, in light of your betting on "1" appearing in just four die rollsmeans we should be looking at median outcomes rather than average. Since dice rolls are independent, rolling m dice once and one die m times will give indistinguishable results. OP thus asks:On average, how many rolls of a single die are required to get all six results? Betting on a smaller number loses, on average; a greater number gives a win. The "waiting time" to expect a particular result [measured in actual time, or (more often) in number of trials] is simply the reciprocal of the probability of obtaining the result in unit time, or in a single trial. In the present case the reciprocal probabilities for the 1st, 2nd, 3rd, ..., 6th distinct value to appear are, trivially,1, 2.2, 3.7, 5.7, 8.7, 1 2.20138 3.70155 5.69817 8.70078 14.70568On the other hand, all six values appear more than half the time in 13 rolls of a die. I agree with the note about median. I think the problem here is that the OP and post 14 (see blue-colored part in spoiler above) are conflating the median and the average (or mean) in the interpretation of the winning condition Let's adopt Bonanova's convention and reframe the OP as a problem of rolling a single die N times. Let P( N ) be the probability that all 6 numbers cummulatively show up *on precisely* the N-th roll (i.e., the winning condition is *first* satisfied on the N-th roll). The OP and the post 14 poses actually two different problems 1) OP: What is smallest value of N that gives you a winning bet on average? I think a reasonable interpretation of this is that what is the smallest N such that the cumulative probability of winning is above .5. In mathematical notations, we are looking for the median M, which is defined as the smallest M such that 2) Post 14: On average, how many rolls of a single die are required to get all six results? This definitely asks for the expected value of the number of rolls required to get 6 different numbers. In mathematical notation, we are looking for the average A The key here is that for this puzzle, the median is roughly 13, while the mean is roughly 14.7. Quote Link to post Share on other sites

0 Prime 15 Posted January 26, 2013 Report Share Posted January 26, 2013 (edited) The statement of the problem is unambiguous. It requires finding the smallest number of dice for the winning bet on average (not the average). Bonanova is a Grandmaster of stating problems. If he wanted us to find the average number of rolls before you get all 6 numbers, he would say so (in a better way.) Misidentifying Expected Value or average number of trials with probability of 1/2 is a typical error. I have seen it many times, well aware of it, yet once in a while have a lapse of judgment and make the same mistake. I have followed this forum for years, especially Bonanova’s puzzles, my favorites in part for the witty, elegant, and accurate formulation of problems. In my experience, if you think Bonanova has made a mistake in stating his puzzle, read the conditions again and think it over. Just the other day I used presumption of Bonanova’s infallibility in formulating conditions as a clue to solving his other puzzle: http://brainden.com/forum/index.php/topic/15527-six-integer-equations-eight-digits/?p=327600 When it comes to solving complex problems, Bonanova, however seldom, still can make a mistake, like the rest of us. So bring out Champaign. And let us not despoil the celebration of this rare joyous occasion by any unwarranted attempts to obfuscate the clear and precise statement of the problem with any median vs. average, or other irrelevant discussions. In defense of Bonanova’s wonderful talent and skill in formulating problems, and his right to make a mistake once in a while, and in the interest of the truth in gambling: THE ANSWER IS 13! (Exclamation sign - not a factorial.) Edited January 26, 2013 by Prime Quote Link to post Share on other sites

0 bonanova 85 Posted January 27, 2013 Author Report Share Posted January 27, 2013 I brought up the idea of median, since the distribution is skewed and I needed a way for both 13 and 14.7 to have significance. Bushindo stated exactly, and clearly, why it suggested itself. Prime explained well why and how wait times and <p> = .5 are different conditions. I've thought about it for a day now and I haven't decided for sure how a puzzle like this one might be worded in order to require finding a skewed median. but i think it could make an interesting puzzle. For sure, the wording would need to be precise. For this puzzle, I had in mind the cute 14.7 calculation. But I didn't word the OP to ask for it. I was surprised to confirm by simulation that 13 is the answer, as I worded it. Prime is way too kind to say a mistake on my part is anything close to a noteworthy event. But it is clear that (using his example) since betting on a "1" in four rolls wins, wait time (six rolls) isn't the answer for an even bet. Well guys, I enjoyed this puzzle too. Thanks for teaching me something. Footnote: sorry plainglazed, the solution post goes now to SP! Quote Link to post Share on other sites

## Question

## bonanova 85

You throw

mfair six-sided dice and bet that all numbers from 1 to 6 will show at least once.What is the smallest value of

mthat gives you a winning bet on average?## Link to post

## Share on other sites

## 18 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.