ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6293
Joined: Jun 22, 2011
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
ChesterDog
  • Threads: 8
  • Posts: 1517
Joined: Jul 26, 2010
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
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
Thanked by
ChesterDog
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
ThatDonGuy
  • Threads: 117
  • Posts: 6293
Joined: Jun 22, 2011
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
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
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
ThatDonGuy
  • Threads: 117
  • Posts: 6293
Joined: Jun 22, 2011
Thanked by
ChesterDogcharliepatrick
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
Administrator
gordonm888
  • Threads: 60
  • Posts: 5062
Joined: Feb 18, 2015
Thanked by
EdCollins
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
rakesh
  • Threads: 1
  • Posts: 6
Joined: Jun 29, 2021
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
Administrator
gordonm888
  • Threads: 60
  • Posts: 5062
Joined: Feb 18, 2015
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
rakesh
  • Threads: 1
  • Posts: 6
Joined: Jun 29, 2021
July 4th, 2021 at 1:03:04 AM permalink
All good Gordonm888, actually i could not see the solution given by THATDONGUY and i shared my approach also.
Both solutions are same.
  • Jump to: