Problem Statement
Empty The Box is a game played with two D-sided dice, one box, and a collection of T penalty tokens. The values of the penalty tokens are 1, 2, ..., T. At the beginning of the game all penalty tokens are in the box.
The game consists of one or more turns. In each turn you roll the two D-sided dice. The number you rolled (i.e., the sum of the numbers on the two dice) is called your power for the round. Now you have the option to remove some penalty tokens from the box. You may remove arbitrarily many tokens, but the total value of the tokens you remove must be exactly equal to your current power. If you cannot do that, you do not get to remove any tokens and the game ends. Your penalty at the end of the game is equal to the total value of tokens left in the box.
You are going to play this game. Your goal is to minimize the expected value of the penalty you'll receive at the end. Calculate and return that expected value, assuming you play optimally.
Definition
- Class:
- EmptyTheBox
- Method:
- minExpectedPenalty
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double minExpectedPenalty(int D, int T)
- (be sure your method is public)
Notes
- Your return value must have an absolute or relative error at most 1e-9.
- Each D-sided die generates a uniformly random number between 1 and D, inclusive.
Constraints
- D will be between 2 and 6, inclusive.
- T will be between 1 and 50, inclusive.
Examples
2
3
Returns: 1.25
You have two 2-sided dice (i.e., coins with "1" on one side and "2" on the other) and three penalty tokens with values 1, 2, 3. The only strategic decision in this game is what to take if your first roll is a 3. In this particular situation it's obvious that eliminating the token with value 3 is better than eliminating tokens worth 1+2, as it leaves you more options later, so you do that. We can now examine all possible results of the first and second roll, concluding that if your first roll is a 2 or a 4, your expected final penalty is 1.5, but if your first roll is the 3, your expected final penalty is only 1. Hence, your expected final penalty is 0.25 * 1.5 + 0.5 * 1 + 0.25 * 1.5 = 1.25.
6
2
Returns: 2.777777777777778
If you roll a 1+1 (probability 1/36), you get to remove the token with value 2. If you roll a 1+2 (probability 1/18), you get to empty the box. Otherwise, you end with penalty 3.
6
50
Returns: 1232.0814206529215
6
22
Returns: 210.08142065292145
6
10
Returns: 16.64572136166177
Two regular dice and a box with ten tokens. You can usually get the penalty much lower than the initial 55.
4
10
Returns: 33.489906787872314
In the same game played with tetrahedrons instead of traditional dice your expected final penalty is much higher.
6
37
Returns: 660.0814206529215
5
50
Returns: 1243.7099205939144
5
32
Returns: 496.7099205939144
5
14
Returns: 73.70992059391436
4
35
Returns: 608.4899067878723
3
50
Returns: 1261.6377754068656
2
49
Returns: 1217.78125
2
1
Returns: 1.0
2
2
Returns: 1.0
2
3
Returns: 1.25
2
4
Returns: 2.78125
3
1
Returns: 1.0
3
2
Returns: 2.111111111111111
3
3
Returns: 1.5061728395061729
3
4
Returns: 2.148148148148148
3
5
Returns: 3.694711172077427
3
6
Returns: 7.637775406865482
4
1
Returns: 1.0
4
3
Returns: 2.21875
4
4
Returns: 2.63525390625
4
7
Returns: 8.31364631652832
4
8
Returns: 14.489906787872314
5
1
Returns: 1.0
5
2
Returns: 2.6799999999999997
5
5
Returns: 3.39937024
5
6
Returns: 4.3549142016
5
8
Returns: 9.679621758976001
5
9
Returns: 15.32827956588708
5
10
Returns: 23.709920593914365
6
1
Returns: 1.0000000000000002
6
2
Returns: 2.777777777777778
6
3
Returns: 4.0246913580246915
6
4
Returns: 3.2946244855967084
6
5
Returns: 3.898693510897729
6
6
Returns: 4.3020358357042445
6
7
Returns: 5.534381535885452
6
8
Returns: 7.6236893875640135
6
9
Returns: 11.157508444202621
6
10
Returns: 16.64572136166177
6
11
Returns: 24.540199533804397
6
12
Returns: 35.081420652921445
6
42
Returns: 860.0814206529215
5
48
Returns: 1144.7099205939144
4
32
Returns: 506.4899067878723
6
45
Returns: 992.0814206529215
6
30
Returns: 422.08142065292145