## Poll

11 votes (45.83%) | |||

9 votes (37.5%) | |||

5 votes (20.83%) | |||

2 votes (8.33%) | |||

7 votes (29.16%) | |||

3 votes (12.5%) | |||

4 votes (16.66%) | |||

3 votes (12.5%) | |||

9 votes (37.5%) | |||

7 votes (29.16%) |

**24 members have voted**

March 4th, 2021 at 2:19:51 PM
permalink

Quote:charliepatrickI haven't checked the answers yet, but this is what it produced.I: 1 J: 2 Perms: 157366449604 Profit: 1 Win: 2

I: 1 J: 3 Perms: 144520208820 Profit: 1.988888888888889 Win: 2.988888888888889

I: 1 J: 4 Perms: 132601016340 Profit: 2.966666666666667 Win: 3.966666666666667

I: 1 J: 5 Perms: 121550931645 Profit: 3.933333333333333 Win: 4.933333333333334

I: 1 J: 6 Perms: 111315063717 Profit: 4.888888888888889 Win: 5.888888888888889

I: 1 J: 7 Perms: 101841441273 Profit: 5.833333333333333 Win: 6.833333333333333

I: 1 J: 8 Perms: 93080887185 Profit: 6.766666666666667 Win: 7.766666666666667

I: 1 J: 9 Perms: 84986896995 Profit: 7.688888888888889 Win: 8.68888888888889

I: 1 J: 10 Perms: 77515521435 Profit: 8.6 Win: 9.6

I: 1 J: 11 Perms: 70625252863 Profit: 9.5 Win: 10.5

....

I: 88 J: 89 Perms: 165 Profit: -42.5 Win: 88

I: 88 J: 90 Perms: 45 Profit: -42.477777777777774 Win: 88

I: 88 J: 91 Perms: 9 Profit: -42.46666666666667 Win: 88

I: 88 J: 92 Perms: 1 Profit: -42.46666666666667 Win: 88

I: 89 J: 90 Perms: 45 Profit: -43.48888888888889 Win: 89

I: 89 J: 91 Perms: 9 Profit: -43.477777777777774 Win: 89

I: 89 J: 92 Perms: 1 Profit: -43.477777777777774 Win: 89

I: 90 J: 91 Perms: 9 Profit: -44.48888888888889 Win: 90

I: 90 J: 92 Perms: 1 Profit: -44.48888888888889 Win: 90

I: 91 J: 92 Perms: 1 Profit: -45.5 Win: 91

AvWin: 16.22254798150687totalprofit=0;

totalperms=0;

for (i=1; i<=91; i++) {

for (j=i+1; j<=92; j++) {

perms=(100-j)*(99-j)*(98-j)*(97-j)*(96-j)*(95-j)*(94-j)*(93-j)/8/7/6/5/4/3/2;

profit=0;

if (i>1) { for (k=1; k<i; k++) {profit+=k-i;};};

if (j>i+1) { for (k=i+1; k<j; k++) {profit+=k-i;};};

if (j<92) { for (k=j+9; k<=100; k++) {profit+=j-i;};};

profit=profit/90;

outline=" ";

outline+="I: "+i+" ";

outline+="J: "+j+" ";

outline+="Perms: "+perms+" ";

outline+="Profit: "+profit+" ";

win=i; if (profit>0) {win=i+profit;};

outline+="Win: "+win+" ";

outline+="<BR>";

document.write(outline);

totalprofit+=win*perms;

totalperms+=perms;

}; };

average=totalprofit/totalperms;

outline+="AvWin: "+average+" ";

outline+="<BR>";

document.write(outline);

Can you double check these lines?

if (i>1) { for (k=1; k<i; k++) {profit+=k-i;};};

if (j>i+1) { for (k=i+1; k<j; k++) {profit+=k-i;};};

if (j<92) { for (k=j+9; k<=100; k++) {profit+=j-i;};};

Thanks!

Poetry website: www.totallydisconnected.com

March 4th, 2021 at 2:45:24 PM
permalink

I've checked a few examples and they look good.Quote:teliot...double check these lines...

There are 90 possible values for the redrawn ball (I'm assuming it can't be ones you've already got or the one you discarded).

I: 2 J: 3 Perms: 144520208820 Profit: 0.9777777777777777 Win: 2.977777777777778

If the drawn ball is higher than 3 you win 3; only if the new ball drawn in 1 will you not receive 3. The chances of this are 1 in 90 and it loses you 2. So the average is 3 less 2/90. Check.

I: 40 J: 50 Perms: 536878650 Profit: -3.5 Win: 40 T1: -780 T: 39 T1: -735 T: 48 T1: -315 T: 90

From 1 thru 39 you lose 39 thru 1 = -780 (average of -1 and -39 = -20, number of items = 39, total = -780).

From 41 thru 49 you gain 1 thru 9 = +45 (average of 1 and 9 = 5, number of items = 9, total +45.

The remaining 51 to 100 except for the 8 balls already drawn each gain 10. There are 42 os these so total = +420.

420+45-780 = -315. -315/90 = -3.5. Check.

I: 2 J: 3 Perms: 144520208820 Profit: 0.9777777777777777 Win: 2.977777777777778

If the drawn ball is higher than 3 you win 3; only if the new ball drawn in 1 will you not receive 3. The chances of this are 1 in 90 and it loses you 2. So the average is 3 less 2/90. Check.

I: 40 J: 50 Perms: 536878650 Profit: -3.5 Win: 40 T1: -780 T: 39 T1: -735 T: 48 T1: -315 T: 90

From 1 thru 39 you lose 39 thru 1 = -780 (average of -1 and -39 = -20, number of items = 39, total = -780).

From 41 thru 49 you gain 1 thru 9 = +45 (average of 1 and 9 = 5, number of items = 9, total +45.

The remaining 51 to 100 except for the 8 balls already drawn each gain 10. There are 42 os these so total = +420.

420+45-780 = -315. -315/90 = -3.5. Check.

March 4th, 2021 at 2:54:47 PM
permalink

OK, I see where we differ and what my problem was.Quote:charliepatrickThere are 90 possible values for the redrawn ball (I'm assuming it can't be ones you've already got or the one you discarded).

I: 2 J: 3 Perms: 144520208820 Profit: 0.9777777777777777 Win: 2.977777777777778

If the drawn ball is higher than 3 you win 3; only if the new ball drawn in 1 will you not receive 3. The chances of this are 1 in 90 and it loses you 2. So the average is 3 less 2/90. Check.

I: 40 J: 50 Perms: 536878650 Profit: -3.5 Win: 40 T1: -780 T: 39 T1: -735 T: 48 T1: -315 T: 90

From 1 thru 39 you lose 39 thru 1 = -780 (average of -1 and -39 = -20, number of items = 39, total = -780).

From 41 thru 49 you gain 1 thru 9 = +45 (average of 1 and 9 = 5, number of items = 9, total +45.

The remaining 51 to 100 except for the 8 balls already drawn each gain 10. There are 42 os these so total = +420.

420+45-780 = -315. -315/90 = -3.5. Check.

You are only recording the profit if profit > 0. Essentially, you solved the second problem, optimal play, not the first. I re-wrote your code without the line "if profit > 0" in it and we came up with the same answer.

Oh, I see you added a NB above.

Very nice!!!

#include <stdio.h>

int main() {

int i, j, k;

double totalprofit = 0;

double totalperms = 0;

double profit, perms, win, num;

for (i=1; i<=91; i++) {

for (j=i+1; j<=92; j++) {

perms=(100.0-j)*(99-j)*(98-j)*(97-j)*(96-j)*(95-j)*(94-j)*(93-j)/(2.0*3*4*5*6*7*8);

profit=0;

num = 0;

if (i>1) {

for (k=1; k<i; k++) {

profit+=(k-i);

num++;

}

}

if (j>i+1) {

for (k=i+1; k<j; k++) {

profit+=(k-i);

num++;

}

}

if (j<92) {

for (k=j+9; k<=100; k++) {

profit+=(j-i);

num++;

}

}

profit = profit/num;

win = i+profit;

totalprofit += (win*perms);

totalperms += perms;

}

}

printf("%1.6f\n", totalprofit/totalperms);

return 0;

}

$ ./a.exe

16.068182

Last edited by: teliot on Mar 4, 2021

Poetry website: www.totallydisconnected.com

March 4th, 2021 at 3:06:27 PM
permalink

Optimal strategy -- thanks to charliepatrick for the code.

Minimum pair (i,j) with i < j to draw a second ball to replace i.

1, 2

2, 3

3, 4

4, 5

5, 6

6, 7

7, 8

8, 9

9, 10

10, 11

11, 12

12, 13

13, 15

14, 16

15, 17

16, 18

17, 19

18, 21

19, 22

20, 23

21, 25

22, 26

23, 27

24, 29

25, 30

26, 32

27, 33

28, 35

29, 36

30, 38

31, 40

32, 42

33, 43

34, 45

35, 47

36, 49

37, 52

38, 54

39, 56

40, 59

41, 62

42, 65

43, 69

44, 73

45, 79

Return = 16.222548

Poetry website: www.totallydisconnected.com

March 4th, 2021 at 3:30:29 PM
permalink

Quote:teliot

Optimal strategy -- thanks to charliepatrick for the code.

Got the same thing in Excel. The key to the problem was calculating the average draw value given the two lowest numbers, a and b:

(b*(b-1)/2-a+b*(100-b-8))/90

I heart Crystal Math.

March 5th, 2021 at 6:41:09 AM
permalink

Quote:teliotSo, here is a slightly harder version --

A a keno blower has 100 balls, each numbered 1 through 100. Ten balls are drawn at random and recorded. After the ten balls are drawn, the lowest number recorded out of the 10 balls is then discarded and another ball is drawn from the blower to replace it. You then win $1 multiplied by the lowest of the ten numbers.

What is the expected win, to the nearest cent?

Suppose the lowest number in the 10 drawn is N.

Let K be the second-lowest number drawn.

The expected value of the lowest number after the draw is (probability that the 11th number < K) x (expected value of the 11th number) + (probability that the 11th number > K) x K.

Of the C(100 - N, 9) sets of 9 numbers > N, the lowest number (i.e. the second-lowest number in the original 10) is:

N + 1, with probability C(99 - N, 8) / C(100 - N, 9)

N + 2, with probability C(98 - N, 8) / C(100 - N, 9)

...

91, with probability C(9, 8) / C(100 - N, 9)

92, with probability C(8, 8) / C(100 - N, 9)

The expected value of the lowest number after the redraw is (K - 1) / 99 x (K + 1) / 2 + (100 - K) / 99 x K

= (K (200 - K) - 1) / 198

where K is the second-lowest number in the original 10

If the original lowest number is 10, the expected value is:

C(89, 8) / C(90, 9) x (11 x 189 - 1) / 198

+ C(88, 8) / C(90, 9) x (12 x 188 - 1) / 198

+ C(87, 8) / C(90, 9) x (13 x 187 - 1) / 198

+ ...

+ C(8, 8) / C(90, 9) x (92 x 8 - 1) / 198

This has to be calculated for each possible lowest number from 1 to 91, then multiply by the probability that it is the original lowest number, and sum the values.

March 5th, 2021 at 6:44:02 AM
permalink

Yes. If you look at some of the spoilers above, you will see an implementation of a slight simplification of this idea to solve the problem. Even more, the strategy problem has also been solved. Great work by charliepatrick.Quote:ThatDonGuy

Suppose the lowest number in the 10 drawn is N.

Let K be the second-lowest number drawn.

The expected value of the lowest number after the draw is (probability that the 11th number < K) x (expected value of the 11th number) + (probability that the 11th number > K) x K.

Of the C(100 - N, 9) sets of 9 numbers > N, the lowest number (i.e. the second-lowest number in the original 10) is:

N + 1, with probability C(99 - N, 8) / C(100 - N, 9)

N + 2, with probability C(98 - N, 8) / C(100 - N, 9)

...

91, with probability C(9, 8) / C(100 - N, 9)

92, with probability C(8, 8) / C(100 - N, 9)

The expected value of the lowest number after the redraw is (K - 1) / 99 x (K + 1) / 2 + (100 - K) / 99 x K

= (K (200 - K) - 1) / 198

where K is the second-lowest number in the original 10

If the original lowest number is 10, the expected value is:

C(89, 8) / C(90, 9) x (11 x 189 - 1) / 198

+ C(88, 8) / C(90, 9) x (12 x 188 - 1) / 198

+ C(87, 8) / C(90, 9) x (13 x 187 - 1) / 198

+ ...

+ C(8, 8) / C(90, 9) x (92 x 8 - 1) / 198

This has to be calculated for each possible lowest number from 1 to 91, then multiply by the probability that it is the original lowest number, and sum the values.

Last edited by: teliot on Mar 5, 2021

Poetry website: www.totallydisconnected.com

March 6th, 2021 at 7:48:16 AM
permalink

Here is a math solution (well, sort of) to the "slightly harder" problem with the 100 balls:

First, some explanation of my notation:

C(A,B) is the number of combinations of A things taken B at a time

SUM[B=2..92] {...} is the sum of the value within { } for all B from 2 to 92 inclusive; imagine a capital sigma with "B=2" at the bottom and "92" at the top.

Let A and B be the smallest and second-smallest numbers drawn; note that 1 <= A < B <= 92

There are C(100-B, 8) combinations of the C(100, 10) where this is true

If the 11th number < B, it is the lowest number after A is removed; there are B-2 numbers < B excluding A,

so the expected value of the lowest number in this case is (1 + 2 + ... + (B-1) - A) / (B-2) = ((B-1) B - 2A) / (2 (B-2)).

If the 11th number < B, then B is the lowest number after A is removed.

P(11th number < B) = (B - 2) / 90

P(11th number > B) = (92 - B) / 90

The expected value of the lowest number is

1 / C(100, 10) x SUM[B=2..92] {SUM[A=1..B-1] {C(100-B, 8) x (((B - 2) / 90)((B - 1) B - 2A) / (2 (B - 2)) + B (92 - B) / 90)}}

= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {((B - 1) B - 2A) / 180 + 2B (92 - B) / 180}}

= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {(183 B - B^2 - 2A) / 180}}

= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x (SUM[A=1..B-1] {183 B - B^2} - SUM[A=1..B-1] {2A})}

= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x ((B - 1)(183 B - B^2) - 2 (B - 1) B / 2)}

= SUM[B=2..92] {(183 B^2 - B^3 - 182 B) C(100-B, 8)} / (180 C(100, 10))

Okay, I needed a computer to calculate the sum, but it turns out to be 707 / 44.

First, some explanation of my notation:

C(A,B) is the number of combinations of A things taken B at a time

SUM[B=2..92] {...} is the sum of the value within { } for all B from 2 to 92 inclusive; imagine a capital sigma with "B=2" at the bottom and "92" at the top.

Let A and B be the smallest and second-smallest numbers drawn; note that 1 <= A < B <= 92

There are C(100-B, 8) combinations of the C(100, 10) where this is true

If the 11th number < B, it is the lowest number after A is removed; there are B-2 numbers < B excluding A,

so the expected value of the lowest number in this case is (1 + 2 + ... + (B-1) - A) / (B-2) = ((B-1) B - 2A) / (2 (B-2)).

If the 11th number < B, then B is the lowest number after A is removed.

P(11th number < B) = (B - 2) / 90

P(11th number > B) = (92 - B) / 90

The expected value of the lowest number is

1 / C(100, 10) x SUM[B=2..92] {SUM[A=1..B-1] {C(100-B, 8) x (((B - 2) / 90)((B - 1) B - 2A) / (2 (B - 2)) + B (92 - B) / 90)}}

= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {((B - 1) B - 2A) / 180 + 2B (92 - B) / 180}}

= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {(183 B - B^2 - 2A) / 180}}

= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x (SUM[A=1..B-1] {183 B - B^2} - SUM[A=1..B-1] {2A})}

= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x ((B - 1)(183 B - B^2) - 2 (B - 1) B / 2)}

= SUM[B=2..92] {(183 B^2 - B^3 - 182 B) C(100-B, 8)} / (180 C(100, 10))

Okay, I needed a computer to calculate the sum, but it turns out to be 707 / 44.

March 6th, 2021 at 7:54:07 AM
permalink

What I love most about this is that you reduced the fraction ... the rest of us just got the decimal expansion. :) Nice!Quote:ThatDonGuyHere is a math solution (well, sort of) to the "slightly harder" problem with the 100 balls:

First, some explanation of my notation:

C(A,B) is the number of combinations of A things taken B at a time

SUM[B=2..92] {...} is the sum of the value within { } for all B from 2 to 92 inclusive; imagine a capital sigma with "B=2" at the bottom and "92" at the top.

Let A and B be the smallest and second-smallest numbers drawn; note that 1 <= A < B <= 92

There are C(100-B, 8) combinations of the C(100, 10) where this is true

If the 11th number < B, it is the lowest number after A is removed; there are B-2 numbers < B excluding A,

so the expected value of the lowest number in this case is (1 + 2 + ... + (B-1) - A) / (B-2) = ((B-1) B - 2A) / (2 (B-2)).

If the 11th number < B, then B is the lowest number after A is removed.

P(11th number < B) = (B - 2) / 90

P(11th number > B) = (92 - B) / 90

The expected value of the lowest number is

1 / C(100, 10) x SUM[B=2..92] {SUM[A=1..B-1] {C(100-B, 8) x (((B - 2) / 90)((B - 1) B - 2A) / (2 (B - 2)) + B (92 - B) / 90)}}

= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {((B - 1) B - 2A) / 180 + 2B (92 - B) / 180}}

= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {(183 B - B^2 - 2A) / 180}}

= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x (SUM[A=1..B-1] {183 B - B^2} - SUM[A=1..B-1] {2A})}

= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x ((B - 1)(183 B - B^2) - 2 (B - 1) B / 2)}

= SUM[B=2..92] {(183 B^2 - B^3 - 182 B) C(100-B, 8)} / (180 C(100, 10))

Okay, I needed a computer to calculate the sum, but it turns out to be 707 / 44.

Poetry website: www.totallydisconnected.com

March 6th, 2021 at 8:09:40 PM
permalink

Quote:teliot

Optimal strategy -- thanks to charliepatrick for the code.

Minimum pair (i,j) with i < j to draw a second ball to replace i.

1, 2

2, 3

3, 4

4, 5

5, 6

6, 7

7, 8

8, 9

9, 10

10, 11

11, 12

12, 13

13, 15

14, 16

15, 17

16, 18

17, 19

18, 21

19, 22

20, 23

21, 25

22, 26

23, 27

24, 29

25, 30

26, 32

27, 33

28, 35

29, 36

30, 38

31, 40

32, 42

33, 43

34, 45

35, 47

36, 49

37, 52

38, 54

39, 56

40, 59

41, 62

42, 65

43, 69

44, 73

45, 79

Return = 16.222548

I get 45,293,117,053,521 / 2,791,985,396,200, which is 16.222547981507

The strategy is to draw when A < (183 B - B^2) / 182, where A and B are the smallest and second-smallest numbers.

This is equivalent to B > 183/2 - sqrt(183^2 / 4 - 182 A) for B < 183/2.

It appears to match the above list of pairs.