Problem
get the max amount of gold
There are 10 rooms with random amount of gold. The player can only enter one room once, and can only take the gold in one of the rooms. A player designed the following strategy: for the first 4 rooms, he only enters but won't take the gold. He remember the max amount of gold he has saw among these 4 rooms. After that, if he saw any room's gold is more than that amount, he took the gold, otherwise, he took the the gold in the last room. Write a program to calculate the possibility of this player got the largest amount of gold.
For example,
1 3 4 8 1 2 10 5 7 0
the player saw the max amount in the first 4 rooms is 8, then he took the gold in room 7, because 10 is larger than 8, he can get the max amount of gold.
In another example
1 3 4 8 1 2 10 5 7 100
he won't get the max amount of gold, because he will take 10 instead of 100 according to his strategy.
Solution
The brutal force way is to simulate the game, if we have a good random and play long enough, we should get the possibility.
import java.util.*;
public class MaxGold {
private static final int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
private static final int K = 4;
private static final int MAX = 10;
private static final int TOTAL = 1000;
public boolean getMax(int[] a) {
shuffle(a);
int max = Integer.MIN_VALUE;
for(int i = 0; i < K; i++) {
if(max < a[i])
max = a[i];
}
for(int i = K; i < a.length; i++) {
if(a[i] >= max) {
if(a[i] == MAX)
return true;
break;
}
}
return false;
}
private void shuffle(int[] a) { //random
Random r = new Random();
for(int i = 0; i < a.length; i++) {
exch(a, r.nextInt(a.length), r.nextInt(a.length));
}
}
private void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String...args) {
MaxGold mg = new MaxGold();
int success = 0;
for(int i = 0; i < TOTAL; i++) {
if(mg.getMax(a)) success++;
}
System.out.println((double)success/(double)TOTAL); //0.398
}
}
public class MaxGold {
private static final int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
private static final int K = 4;
private static final int MAX = 10;
private static final int TOTAL = 1000;
public boolean getMax(int[] a) {
shuffle(a);
int max = Integer.MIN_VALUE;
for(int i = 0; i < K; i++) {
if(max < a[i])
max = a[i];
}
for(int i = K; i < a.length; i++) {
if(a[i] >= max) {
if(a[i] == MAX)
return true;
break;
}
}
return false;
}
private void shuffle(int[] a) { //random
Random r = new Random();
for(int i = 0; i < a.length; i++) {
exch(a, r.nextInt(a.length), r.nextInt(a.length));
}
}
private void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String...args) {
MaxGold mg = new MaxGold();
int success = 0;
for(int i = 0; i < TOTAL; i++) {
if(mg.getMax(a)) success++;
}
System.out.println((double)success/(double)TOTAL); //0.398
}
}
For each game, we need to go through each room, the cost is N, we play TOTAL games, the cost is O(TOTAL*N), space cost is O(1).
By changing K value, we found K = 3, we have the best chance. This makes sense, we need to sample some rooms in order to get a general idea of the rooms before we take action. If we sample too many, we are too hesitate to act; if we sample too little, we are too hasty to jump the gun. The sweet point is sample 3 of the rooms.
By changing K value, we found K = 3, we have the best chance. This makes sense, we need to sample some rooms in order to get a general idea of the rooms before we take action. If we sample too many, we are too hesitate to act; if we sample too little, we are too hasty to jump the gun. The sweet point is sample 3 of the rooms.
With mathematics, we can get the formula, then calculate it with a paper.
Math
the amount in the 10 rooms are:
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
Each room has 0.1 chance of getting the max amount. Once that room has the max, how much chance the player can get it with the strategy? We add the chance for all the rooms, that is the possibility.
Sum(P(i))
The P(1), P(2), P(3) and P(4) are all 0, because, if the max are there, the player loose the game.
Now P(5) = 0.1, because the room has 0.1 chance of getting the max, if the max is in the 5th room, the player is win for sure.
P(6) = 0.1 x (4/5)
The room has 0.1 chance of getting max, once room 6 get max, if room 5 has a bigger value than the first 4 rooms, the player will pick room 5 and fail. So in order for the player to win, the bigger value can only be in the first 4 rooms, the chance for that is 4/5.
P(7) = 0.1 x (4/6)
The room has 0.1 chance of getting max, once room 7 get max, if room 5 and 6 has a bigger value than the first 4 rooms, the player will pick room 5 or 6 and fail. So in order for the player to win, the bigger value can only be in the first 4 rooms, the chance for that is 4/6.
P(8) = 0.1 x (4/7)
P(9) = 0.1 x (4/8)
P(10) = 0.1 x (4/9)
P = 0.1 x (4/4 + 4/5 + 4/6 + 4/7 + 4/8 + 4/9)
= (k/n) x (1/k + 1/(k+1) + 1/(k+2) + ... + 1/(n-1))
To find the value, the time cost is O(N). To scan the optimum k, the time cost is O(N^2). The space cost is O(1)
public class MaxGoldPlan {
//10
public static void roomToCheck(int N) {
double maxChance = 0;
int roomToCheck = 1;
for(int i = 1; i <= N; i++) {
double chance = getChance(i, N);
if(chance >= maxChance) {
maxChance = chance;
roomToCheck = i;
}
}
System.out.println("for " + N + " rooms, check " + roomToCheck + " will yield best chance of " + maxChance);
}
private static int roomToCheck2(int N) {
double edge = 0;
int i = 0;
while(edge <= 1) {
edge = edge + (double)1/(double)(N - 1 - i);
i++;
}
return N - i;
}
private static double getChance(int k, int N) {//1 10
double chance = 0;
for(int i = k; i <= N-1; i++) {
chance = chance + (double)k/(double)i;
}
return chance/(double)N;
}
public static void main(String...args) {
int N = 10;
for(int i = N; i < N*1000; i *= 10)
roomToCheck(i);
System.out.println("==========detect P[k+1] - P[k] == 0 to find max point==================");
for(int i = N; i < N*10000; i *= 10) {
int room = roomToCheck2(i);
double chance = getChance(room, i);
System.out.println("for " + i + " rooms, check " + room + " will yield best chance of " + chance);
}
}
}
//10
public static void roomToCheck(int N) {
double maxChance = 0;
int roomToCheck = 1;
for(int i = 1; i <= N; i++) {
double chance = getChance(i, N);
if(chance >= maxChance) {
maxChance = chance;
roomToCheck = i;
}
}
System.out.println("for " + N + " rooms, check " + roomToCheck + " will yield best chance of " + maxChance);
}
private static int roomToCheck2(int N) {
double edge = 0;
int i = 0;
while(edge <= 1) {
edge = edge + (double)1/(double)(N - 1 - i);
i++;
}
return N - i;
}
private static double getChance(int k, int N) {//1 10
double chance = 0;
for(int i = k; i <= N-1; i++) {
chance = chance + (double)k/(double)i;
}
return chance/(double)N;
}
public static void main(String...args) {
int N = 10;
for(int i = N; i < N*1000; i *= 10)
roomToCheck(i);
System.out.println("==========detect P[k+1] - P[k] == 0 to find max point==================");
for(int i = N; i < N*10000; i *= 10) {
int room = roomToCheck2(i);
double chance = getChance(room, i);
System.out.println("for " + i + " rooms, check " + room + " will yield best chance of " + chance);
}
}
}
Time cost O(N^2), space cost O(1).
As a double check, we can calculate the same with a different approach. Since there exists a sweet point of number of rooms to check, before the optimum value, when we check one more room, the chance increase, after the optimum point, when we check one more room, the chance decrease.
P[k+1] - P[k] chance from negative to positive corresponds to the maximum point. We can deduce from formula P[k] = (k/n) x (1/k + 1/(k+1) + 1/(k+2) + ... + 1/(n-1)) that:
when 1/(k'+1) + 1/(k'+2) + ... + 1/(N-1) change from below 1 to above 1, the optimum value is found.
This approach has time cost O(N) and space cost O(1).
As we can see, check 36.8% of the rooms are the best strategy.
for 10 rooms, check 3 will yield best chance of 0.3986904761904762
for 100 rooms, check 37 will yield best chance of 0.37104277871264313
for 1000 rooms, check 368 will yield best chance of 0.3681956172017042
for 10000 rooms, check 3679 will yield best chance of 0.36791104755551685
==========detect P(k+1) - P(k) == 0 to find max point==================
for 10 rooms, check 3 will yield best chance of 0.3986904761904762
for 100 rooms, check 37 will yield best chance of 0.37104277871264313
for 1000 rooms, check 368 will yield best chance of 0.3681956172017042
for 10000 rooms, check 3679 will yield best chance of 0.36791104755551685
for 100000 rooms, check 36788 will yield best chance of 0.3678826017906067
for 1000000 rooms, check 367879 will yield best chance of 0.3678797572318686
