ThatDonGuy Joined: Jun 22, 2011
• Posts: 5368
March 10th, 2020 at 7:33:52 PM permalink
A casino opens a game that works as follows:
There are 2020 balls, numbered 1, 2, 3, ..., 2019, 2020
1000 of them are drawn, and you win whatever the lowest number drawn is.
What is the expected result of the game?
ChesterDog Joined: Jul 26, 2010
• Posts: 1026
March 10th, 2020 at 8:46:39 PM permalink
Quote: ThatDonGuy

A casino opens a game that works as follows:
There are 2020 balls, numbered 1, 2, 3, ..., 2019, 2020
1000 of them are drawn, and you win whatever the lowest number drawn is.
What is the expected result of the game?

A brute force method with Excel gave me an EV of 2.01898101897439.
But I bet there's an elegant way to do the math.
Ace2 Joined: Oct 2, 2017
• Posts: 1593
Thanks for this post from: March 10th, 2020 at 8:58:16 PM permalink
2021/1001 =~ 2.019

(N + 1) / (selections + 1)
It�s all about making that GTA
ThatDonGuy Joined: Jun 22, 2011
• Posts: 5368
March 11th, 2020 at 4:33:24 PM permalink
Quote: Ace2

2021/1001 =~ 2.019

(N + 1) / (selections + 1)

Correct, but how about some details?

Ace2 Joined: Oct 2, 2017
• Posts: 1593
March 11th, 2020 at 5:00:06 PM permalink
Quote: ThatDonGuy

Correct, but how about some details?

I calculated the values for n=5 and n=6. The pattern was clear so I didn�t have to derive the formula.
It�s all about making that GTA
ThatDonGuy Joined: Jun 22, 2011
• Posts: 5368
Thanks for this post from:  March 11th, 2020 at 5:52:01 PM permalink
Quote: Ace2

I calculated the values for n=5 and n=6. The pattern was clear so I didn�t have to derive the formula.

"The pattern was clear"?
So, in that case:
22 - 1 = 3
23 - 1 = 7
25 - 1 = 31
27 - 1 = 127
"The pattern is clear" that 2 raised to the power of a prime number, minus 1, is also prime
211 - 1 = 2047 = 23 x 89...

However, I'm going to be nice and provide the solution:

Before I begin, note that I use (n)C(k) to denote the number of combinations of n things taken k at a time; this is also C(n,k) or Combin(n,k).

This puzzle involves something called the Hockey Stick Principle:
(n)C(n) + (n+1)C(n) + (n+2)C(n) + ... + (n+k)C(n) = (n+k+1)C(n+1)
The name comes from the shape of the line of numbers when this is done on Pascal's Triangle.

Anyway, I will solve the generic case of subsets of K numbers out of {1, 2, 3, ..., N}
There are a total of (N)C(K) subsets
Let S be the smallest number in the subset
There are N-S numbers greater than S, and K-1 of them make up the rest of the numbers in the subset, so there are (N-S)C(K-1) subsets with the smallest number S.
There are (N-1)C(K-1) with smallest number 1, (N-2)C(K-1) with smallest number 2, and so on through (N-(N-(K-1)))C(K-1) with the smallest number N-(K-1), which is the one subset {N-K+1, N-K+2, ..., N}.
The sum of the smallest numbers = 1 x (N-1)C(K-1) + 2 x (N-2)C(K-1) + 3 x (N-3)C(K-1) + ... + N-(K-1) x 1
= ( (N-1)C(K-1) + (N-2)C(K-1) + (N-3)C(K-1) + ... + (K-1)C(K-1) ) + ( (N-2)C(K-1) + (N-3)C(K-1) + (N-4)C(K-1) + ... + (K-1)C(K-1) ) + ... + ( (K)C(K-1) + (K-1)C(K-1) ) + (K-1)C(K-1)
Apply the Hockey Stick Principle to each element in the sum
The sum = (N)C(K) + (N-1)C(K) + (N-2)C(K) + ... + (K+1)C(K) + (K)C(K)
Apply it again to the sum to get (N + 1)C(K + 1)
The expected return = (N + 1)C(K + 1) / (N)C(K)
= ( (N + 1)! / ( (K + 1)! (N - K)! ) ) / ( N! / K! (N - K)! )
= (N + 1)! / ( (K + 1)! (N - K)! ) ) x K! (N - K)! / N!
= (N + 1) N! K! (N - K)! / ( (K + 1) K! (N - K)! ) N!)
= (N + 1) / (K + 1)

gordonm888 Joined: Feb 18, 2015
• Posts: 3625
Thanks for this post from: March 12th, 2020 at 12:47:58 AM permalink
We are going to need the Wizard to continue posting math problems. Because apparently we will all be quarantined or sheltered in our homes for the next month without any sports events to watch.

So, its going to be math and books and movies. And turtles all the way down.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
rakesh Joined: Jun 29, 2021
• Posts: 6
July 3rd, 2021 at 7:32:33 PM permalink
Total possible combinations of 1000 balls = 2020 combination 1000

In possible combinations of 1000 balls
Sets having ball of min value 1 = 2020-1 Combination 1000-1
Sets having ball of min value 2 = 2020-2 Combination 1000-1
Sets having ball of min value 3 = 2020-3 Combination 1000-1
- - - -
- - - -
Sets having ball of min value 1020 = 2020-(2020-1000) Combination 1000-1
Sets having ball of min value 1021 = 2020-1021 Combination 1000-1

Using above pattern we can sum of series or avg or prob. whatever we need.
gordonm888 Joined: Feb 18, 2015
• Posts: 3625
July 3rd, 2021 at 9:02:14 PM permalink
Quote: gordonm888

We are going to need the Wizard to continue posting math problems. Because apparently we will all be quarantined or sheltered in our homes for the next month without any sports events to watch.

So, its going to be math and books and movies. And turtles all the way down.

Why did this old post of mine from 16 months ago randomly get re-posted in the thread in July 2021?

Is there a gremlin in the gears?
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
rakesh Joined: Jun 29, 2021