3
$\begingroup$

The 100 sided die problem has been asked before:

100-sided die probability.

You are given a 100-sided die. After you roll once, you can choose to either get paid the dollar amount of that roll OR pay one dollar for one more roll. What is the expected value of the game? There is no limit on number of rolls.

The solution amounts to solving the equation, where the floor function is necessary because of the discrete die:

(1)$E=\dfrac {\lfloor E-1\rfloor }{100}\cdot \left( E-1\right) + \left( 1-\dfrac {\lfloor E-1\rfloor }{100}\right)\cdot\dfrac {\lfloor E\rfloor +100}{2} $

eg. Say the expected value is 87.5, you would roll again if you got x≤86 as your expected value is 86.5 after one roll (E-1), so with probability 86/100 your expected value would be E-1, if you got 87 or above, then obviously your expected value is $\dfrac {(100+87)}{2}$

The solution is $\dfrac {1223}{14}$

Now how do you solve that equation, without a numerical approach ?

I know that setting $\lfloor E\rfloor $= B and then writing the equation in terms of E, finding the roots ie when E is maximised, somehow works.

ie. $E = \dfrac {(B^2 + B - 10102)}{(2 (B - 101)} $

Then find the B that maximises this equation, which is $B = 101 - 10\sqrt {2}$, then try the nearest integer values, $\lceil B\rceil $, $\lfloor B\rfloor $ and see which one maximises the equation.

Does anybody know why that works and is that the best way to solve the equation, as this is an interview question after all?

$\endgroup$
  • $\begingroup$ They call it dice, please consult a dictionary. (Not my problem, but...) Maybe an edit is attracting some answerers... $\endgroup$ – dan_fulea May 30 '18 at 10:53
  • $\begingroup$ @dan_fulea, I don't understand, who demands one die be called one dice? $\endgroup$ – JimSi May 30 '18 at 16:24
  • $\begingroup$ In English, to die is a verb, it means to no longer exist, to finish life, to go to the end, and so on. A dice is a small toy for small playing boys, and a big toy for casino boys, it has six sides and rolls. It may be that in Your language there is a similar problem for European people, that cannot pronounce correctly the vowel in sǐ - respectively sì . I only wanted to be polite, to Your benefit... $\endgroup$ – dan_fulea May 30 '18 at 17:09
  • $\begingroup$ @dan_fulea, I literally have no idea what you are on about and you are probably trolling. Die can be used as singular, and is a noun. I think it has become acceptable to use dice as both singular and plural, but die is what it started out at, and is most definitely still acceptable and what people say in britain and used by most style guides. en.wikipedia.org/wiki/Dice, you can see the style guide for most, use 'die'. $\endgroup$ – JimSi May 31 '18 at 15:48
  • $\begingroup$ @dan_fulea You are dead wrong and should learn proper english before you criticize someone else's correct english. "Dice" is plural. You can have two or more dice but you can never have one dice. The singular of "dice" is "die". This is a probably about rolling one thing; you only have one of them. That thing is a die. You are wrong and JimiSi is right. You are rude and JimSi is polite. $\endgroup$ – fleablood May 31 '18 at 20:00
0
$\begingroup$

Let $E$ be the solution of the above equation $(1)$.

Let $B=\lfloor E\rfloor$, so $B\le E<B+1$, then we use $\lfloor E-1\rfloor=B-1$ to rewrite $(1)$ as $$ (2)\qquad E \underbrace{\left(1-\frac{B-1}{100}\right)}_{>0} = -\frac {B-1}{100} + \left( 1-\frac {B-1}{100}\right) \cdot \frac {B +100}{2} \ . $$ (The positive term is so, since we cannot win more than $100$ in the game.)

This implies the double inequality restricting $B$, $$ (3)\qquad B\cdot \frac{101-B}{100} \ \overset{(L)}\le\ -\frac {B-1}{100} + \frac {101-B}{100} \cdot \frac {B +100}{2} \ \overset{(R)}<\ (B+1)\cdot \frac{101-B}{100}\ . $$ To find a "good" $B$, we consider the corresponding functions of second degree, then their roots.

  • For the left inequality (L), we have equality for the values $$ B^L_{1,2}=\frac 12(203\pm 2\sqrt{89}) \ ,\qquad B_1^L<B_2^L\ , $$ and the inequality prescribes $B\not\in[B_1^L,B_2^L]$, and this excluded interval is numerically $[\ \color{red}{87.34}90283019150, \ 115.650971698085\ ]$,

  • for the right inequality (R), we have equality for the values $$ B^R_{1,2}=\frac 12(201\pm 2\sqrt{89}) \ ,\qquad B_1^L<B_2^L\ , $$ and the inequality prescribes $B\in[B_1^R,B_2^R]$, and this interval is numerically $[\ \color{red}{86.34}90283019152, \ 114.650971698085\ ]$.

The only matching $B\in\Bbb N$ is $$ B= 87\ .$$ (So it "must be" the value, the backwards implication.)

Using (1), or (2), or $E=g(B)=(B^2+B-10102)/(2(B-1))$, we get the promised value for $E$, $E=g(87)=1223/14$.

Comment: The above is a low level way to proceed. The posted maximality for the function relating $E$ and $B$, $E=g(B)$, is not involved. But there may be a speculative connection, as seen above in $(L)$, we take $B$ to be the maximal solution of (L), equivalently written $B=g(B)$. (Since this maximal solution is the only one that respects also (R). This explains why we take the integer $B$ making $g$ maximal.)

$\endgroup$
  • $\begingroup$ I take it back, I don't think you are trolling as this looks like a legitimate good answer, I will look at it closely tomorrow. $\endgroup$ – JimSi Jun 1 '18 at 0:21
  • $\begingroup$ Ok yes this is a very good method, I don't understand your comment, but the method makes perfect sense. $\endgroup$ – JimSi Jun 1 '18 at 13:21
  • $\begingroup$ Sorry again for my comment, it was late and i was reading only "die probability", and had a bad dictionary... (Obviously, not my native language.) So i fully deserve to be qualified as a troll, and moreover, i am thankful for the free comments, it is not a happy situation for me, but i feel happy with the spoken truth. (My only chance to avoid the pain when it counts!) By the way, the posted idea to find the expected value $E$ is ingenious, i highly appreciate it! $\endgroup$ – dan_fulea Jun 1 '18 at 15:35
  • $\begingroup$ It is no problem at all, where are you from?.. Your solution is very good, and exactly what I was looking for. I still do not understand the 'comment', as looking again at this problem, is setting the floor to B and finding the maximum guaranteed to work? Here it does, because as you say, the maximal solution is the only one that satisfies (L) and (R) $\endgroup$ – JimSi Jun 2 '18 at 8:07
0
$\begingroup$

The reason your substitution works is that the equation is a nice smooth quadratic. If the maximum is between two integer inputs, the highest value with an integer input will be on one side of the maximum or the other. If the degree is higher it usually still works, though you can find cases where it doesn't.

This is a fine approach for solving it.

$\endgroup$
  • $\begingroup$ Ok, I guess yes, for a quadratic, the maximum integer has to be one side of the maximum, and then the equation still holds, because B is the maximum integer value. So what other approaches are there to solving it non-numerically?, I would be very interested. $\endgroup$ – JimSi May 31 '18 at 15:51
  • $\begingroup$ I usually do what you did. Ignore the floor functions and find the maximum taking the independent variable to be real, then look at the integers on each side. $\endgroup$ – Ross Millikan May 31 '18 at 15:55
  • $\begingroup$ ok I apologise as I have managed to confuse myself again. Say the equation was $E=-\lfloor E\rfloor ^{2}+L\left[ E\right] +196.5$, then , setting $\lfloor E\rfloor$ = B , and finding the maximum, does not work? while using inequalities as dan_fulea does in his answer finds the correct answer, of E = 14.5 $\endgroup$ – JimSi Jun 2 '18 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.