I can shave off 1.67 since I was wrong the first time. Let's be a little more rigorous in defining the optimal strategy. The optimal strategy is the one that will end with the least amount over the fair price on average.
There are 5!=120 different possible arrangements of the cards, each of which is assumed equally likely.
Note that if we are in the situation of having been shown the smallest and largest card before the last card is shown, we have complete information and can make an informed decision on when to stop.
Let's start with analyzing the case that we have been shown 4 cards that have consecutive values, and hence, still do not have complete information. What should we do in this case?
4.1. If we are currently on the smallest card, then we are looking at either N or N+100. This means we would pay 50 over on average if we stop. If we continue, then the next card will be either N+400 or N respectively, meaning we would pay an average of 200 over if we continue. Stopping is in our best interest.
4.2 If we are currently on the second smallest card, then we are looking at either N+100 or N+200. This means we would pay 150 over on average if we stop. Since 200 over is the average if we continue, we should stop in this situation.
4.3. If we are currently looking at the second largest card, then we are looking at either N+200 or N+300, paying an average 250 over if we stop. Continuing in this case is in our best interests.
4.4. Looking at either N+300 or N+400 means we pay an average of 350 over. Again, continuing is in our best interests.
Let's now explore some 3 card scenarios. Let's start with the situation in having seen 3 cards that have consecutive values. That is, you are either looking at N, N+100, N+200, or N+100, N+200, N+300, or N+200, N+300, N+400. If we decide to continue in this situation, let's see what would happen.
3.1 Given the N, N+100, N+200 situation, we would either see the sequence N+300, N+400 or N+400, N+300 next. In either case, we continue to the end given 4.4 above or complete information respectively.
3.2 Given the N+100, N+200, N+300 situation, we would either see the sequence N, N+400 or N+400, N next. In either case we stop at N given 4.1 and 4.4 above.
3.3 Given the N+200, N+300, N+400 case, we would either see the sequence N, N+100, or N+100, N. We would stop at the fourth card given complete information or case 4.1.
Given these 6 permutations, we are paying an average of (400+300+0+0+0+100)/6=133.33 over if we elect to continue. So, let's look at each case.
3.1.1. We are currently looking at the smallest of the three cards, which means we are either looking at N, N+100, or N+200. If we stop, we pay an average of 100 over fair price. Compared to the 133.33, this is the better deal. It is beneficial to stop.
3.2.1. The current card is middle card: either N+100, N+200, or N+300. Stopping means we pay an average of 200 over. When compared to 133.33, we elect to continue in this situation.
3.3.1. If our current card is the largest card of either N+200, N+300, or N+400, we pay an average of 300 over, and so continuing is a no-brainer.
Now let's explore 3.4, the situation in which we are looking at 3 cards in the form N, N+100, N+300, or N+100, N+200, N+400, and 3.5, the situation in which we are looking at 3 cards in the form N, N+200, N+300, or N+100, N+300, N+400.
Suppose we continue in case 3.4.
3.4.1. Given the N, N+100, N+300 case, we either see N+200, N+400 or N+400, N+200. We go to the end in either case given 4.3 or complete information.
3.4.2. Given the N+100, N+200, N+400 case, we either see N, N+300 or N+300, N. In either case, we stop at 0 over given complete information or 4.3.
This produces an average of (400+200+0+0)/4=150 over if we elect to continue in this situation. So, let's look at each case.
3.4.3. We are currently looking at the smallest of the three cards, meaning we're looking at either N or N+100. This is an average of 50 over. It is beneficial to stop when compared to 150.
3.4.4. We are on the middle card of either N+100 or N+200 paying an average of 150 if we stop. This is the only case in which we could stay or continue and have the same average. Since the variance is lower for staying, let's assume we stay in this case.
3.4.5. If the current card is the largest of either N+300 or N+400, then the average of 350 is much more than the average of 150 if we continue. Continuing here is a no-brainer.
What if we continue in case 3.5?
3.5.1. Given the N, N+200, N+300 case, we either see N+100, N+400 or N+400, N+100. In either case, we stop at N+100 given 4.2 or complete information.
3.5.2. Given the N+100, N+300, N+400 case, we either see the sequence N, N+200, or N+200, N. We'll stop at the fourth card using complete information or 4.2 respectively.
This produces an average of (100+100+0+200)/4=100 over if we elect to continue. Let's quickly examine each case.
3.5.3. If we are looking at the smallest of the three cards we have seen this averages 50 over. We stay.
3.5.4. The middle cards of N+200 or N+300 has us paying 250 over on average. Continue!
3.5.5. We're on the largest of these three?!? Continue!!
Now comes the largest part of analyzing the two card scenarios. However, with the analysis above, it isn't too daunting.
If the first two cards are N+400 and N, then we stop with the complete information and pay 0 over. There are 6 permutations of 5 cards where these are the first two cards. T=0, P=6.
If the first two are N+300 and N or N+400 and N+100, we should stop. (I've analyzed this on a previous blog, but the idea is that stopping has you pay an average of 50 over while continuing has you pay an average of 100 over). This has you paying 0 over for 6 permutations and 100 over for 6 permutations.
Our current total and number of permutations is T=600 and P=18.
If the first two are N+400, N+200, or N+300, N+100, or N+200, N, we pay an average of 100 over if we stop. If we continue?
2.1.1. Continuing with N+400, N+200, if we see N next we'll stop. We pay 0 with the two permutations associated with that. If we see N+100 next we'll stop by 3.4.3 and pay 100 over with the two permutations associated with it. If we see N+300 next, we continue by 3.2.1. We'll pay 100 if we see the N+100, N permutation and 0 if we see the N, N+100 permutation. T=900, P=24
2.1.2. Continuing with N+300, N+100, if we see N next we'll stop by 3.4.3 and pay 0 with those two permutations. Seeing N+200 next will have us continue by 3.2.1 and see either N+400, N or N, N+400, both of which end at paying 0 over by 4.4 or 4.1 respectively. Seeing N+400 next has us continue by 3.5.5 to see either N+200, N or N, N+200, both of which has us stop at the 4th card by 4.2 or complete information. T=1100, P=30
2.1.3. Continuing with N+200, N, if we see N+100 next we'll continue by 3.2.1 and see either N+300, N+400, or N+400, N+300, both of which we will see to the end by using 4.4 or complete information. If N+300 is next, we continue by 3.5.5 and see either N+100, N+400, or N+400, N+100 both of which we stop at N+100 by 4.2 or complete information. If N+400 is next, we have complete information and will stop a N+100 with those two permutations. T=2200, P=36
If we were to have stayed given those three cases then we would have paid an average of 100 over for the 18 permutations associated with it bringing our total up to 2400 instead. Continuing is better.
Analyzing the case of seeing N+200, N+400, or N+100, N+300, or N, N+200 is completely analogous, except for the fact that it is easier to see you should continue in this case. Adding another 1600 to the total and another 18 permutations gives us T=3800, P=54.
Let's now look at the cases when the first two are N+400, N+300, or N+300, N+200, or N+200, N+100, or N+100, N. We pay an average of 200 over if we stop. Continuing is best.
2.2.1. If we continue with N+400, N+300, we will stop on N+200, N+100, or N given 3.1.1, 3.5.3, or complete information. T=4400, P=60.
2.2.2. Continuing with N+300, N+200, we will stop on N+100 or N if they are next by 3.1.1 or 3.5.3. If N+400 is next we continue by 3.3.1 to see either N+100, N or N, N+100 stopping on the fourth card. T=4700, P=66.
2.2.3. Continuing with N+200, N+100, we will stop on N by 3.1.1. If we see N+400 or N+300 next, we continue and stop at N in either case. T=4700, P=72.
2.2.4. If we see N+100, N we'll explore all 6 cases. The permutations (N+100, N, N+200, N+300, N+400), (N+100, N, N+200, N+400, N+300), (N+100, N, N+300, N+200, N+400), (N+100, N, N+300, N+400, N+200), and (N+100, N, N+400, N+300, N+200) will all have us going until the last card. The permutation (N+100, N, N+400, N+200, N+300) will have us stop at the 4th card because of complete information. T=6400, P=78.
Going from 3800 to 6400 was a 2600 bump with 24 more permutations. This is important only in that analyzing the cases N+300, N+400 or N+200, N+300, or N+100, N+200, or N, N+100 is the exact same. T=9000, P=102.
We're almost there. Now, to look at the two cases N, N+300 and N+100, N+400. We should definitely continue in these cases.
2.3.1. For N, N+300, if we see N+100 next we stop because of the assumption in 3.4.4. If N+200 is next, we continue by 3.5.4 and conclude on N+100 for either permutation. If N+400 is next, we will stop at N+100 because of complete information. T=9600, P=108.
2.3.2. For N+100, N+400, if we see N next we stop with complete information. If N+200 is next, we will stop because of my assumption in 3.4.4. If N+300 is next we continue by 3.5.4 and will stop on the very next card of N+200 (by 4.2) or N by complete information. T=10200, P=114.
And finally, the last 6 permutations associated with N, N+400. These all will lead to N+100 no matter what because we have complete information. The final tally: T=10800, P=120.
This averages to 10800/1200 = 90.
Given the amount of time these riddles are taking me to solve, along with the fact that I get them wrong, I probably will stop writing them up.
Thanks for the write up! Don't stop.
ReplyDeleteGreat writeup, thanks for doing that
ReplyDelete