Sadistic Car Salesman

Solution to @ollie's Car Salesman Problem

120 elementary orderings. 

Never take 1^st card.  Upon 2^nd card, if difference (2^nd minus 1^st) 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 4^th card.  It is in between the 1^st and 2^nd card (not below both) but you get a better expectation than waiting for the 5^th 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).

1^st 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 1^st 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

N+100:  42

N+200:  15

N+300:  4

N+400:  6