120 elementary orderings.
Never take 1st card. Upon 2nd card, if difference (2nd minus 1st) is
· -400: Take it (6 outcomes, E=N+0)
· -300: Take it (12 outcomes, E=N+50; 50% chance of N, 50% of N+100)
· 400: Wait for N+100 (because you now know N) (6 outcomes, E=N+100)
· 300: Define the first card as X. Take X+100 when it comes, or take X-100 if that comes first. (12 outcomes, E=N+100)
· -200, -100, 100, 200: Choose next card that is better than *both* of the first two, with two exceptions:
· If the sequential differences are +200, +100, -200, or if they are -200, +300, -200, then see the 4th card. It is in between the 1st and 2nd card (not below both) but you get a better expectation than waiting for the 5th card.
· If you come to know the optimal remaining choice (because you’ve seen values 400 apart), take it. This occurs when you see sequential diffs of -100/+400, or +100/+300, you know what N+200 is and that it is your optimal choice. Or if you see +200/+200 or -200/+400, you know what N+100 is and that it is your optimal choice.
· This strategy (including exceptions) gives you E=N+88.9 when the first difference is +/-200, 18 outcomes each. And gives you E=N+108.3 when the first difference is +/-100 (24 outcomes each).
1st Difference Outcomes: E(as amount over N)
-400 6 0
-300 12 50
400 6 100
300 12 100
+/-200 36 88.9
+/-100 48 108.3
Total overage = 10,800 out of 120 cases, average overage of 90 (N+90)
Trying to write it as efficiently as possible:
- Never take 1st card (C1). Upon C2, calculate difference (D1=C2-C1).
- If D1 in (-400,-300) then choose C2
- Else if D1=400 then wait for N+100 and choose it
- Else if D1=300 then choose the next card that is equal to C1+100 or C1-100.
- Else if D1 in (-200,-100,100,200) then see C3:
- If C3 < min (C1,C2) then choose it, else see C4
- If C4 < min (C1,C2) then choose it,
- Else if C3 is N+400 (i.e., C3 – min (C1,C2) = 400) then the optimal remaining card is known (could be N+200 or N+100). It could be C4 (choose it now) or C5 (wait for it).*
- Else if the sequential differences (D1/D2/D3) are +200/+100/-200, or -200/+300/-200, then choose C4.**
* [Note: this affects 8/120 elementary orderings, with differences of -200/+400, or -100/+400, or +100/+300, or +200/+200]
** [Note: This affects 4/120 elementary outcomes. The basic strategy of “wait for 1 better than both of C1/C2” results in N twice and N+400 twice. Choosing C4 results in N+100 twice and N+200 twice.]
There are 120 (5!) possible orderings. Among those, you pay
N: 53 times