98 Posts
BoardGameGeek» Forums » Everything Else » Chit Chat
Subject: The latest Friday math problem
Your Tags:  Add tags 
Popular Tags:  View All]  [
 ¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı(MABBY)Canada
Chestermere
AlbertaThere are 10 types of people those who understand binary, and those who don't. 
Full article is here: http://fivethirtyeight.com/features/howbadlycanacarsale...
Summary is here:
You go to buy a specific car, whose fair price we’ll call N.
You have absolutely no idea what N is and the dealer sadistic capitalist that he is won’t tell you.
The dealer enjoys a good chase, though, so without directly revealing the value of N, he takes five index cards and writes down a number on each of them: N, N+100, N+200, N+300 and N+400.
Important: the guy is sadistic, but not a math major. The numbers on the cards are numbers, not algebra equations.
He presents the cards to you, one at a time, in random order.
(For example, if the price on the second card is $100 more than the first, you can’t be sure if those are the two smallest prices, the two largest, or somewhere in between.)
Each time he shows you a card, you must either pay the price on that card, or ask to see the next card. You cannot go back to previous cards. If you make it to the fifth and final card, then that is what you must pay.
If you play the dealer’s game optimally, how much should you expect to pay on average above the fair price N?
 [+] Dice rolls

Wow that's an interesting one. So first you have to figure out the optimal strategy, then work out your average price.
My ruminations on it...Spoiler (click to reveal)
Pass on the first card. Compare, c2  c1:
* $400  Happens 1/20 of the time. First card was N. Draw until you see N+$100.
* $300  Happens 2/20 of the time. First card was N or N+$100. Draw until you see C1$100, which is N; or C1+$100, which could be N+$100 or N+$200, take it, so you will get N 25% of the time, N+$100 50% of the time, and N+$200 25% of the time.
* $200  Happens 3/20 of the time. TBD.
* $100  Happens 4/20 of the time. TBD.
* $100  Happens 4/20 of the time. TBD.
* $200  Happens 3/20 of the time. TBD.
* $300  Happens 2/20 of the time. Take C2. 50% of the time this is N, 50% of the time this is N+$100.
* $400  Happens 1/20 of the time. Take C2. This is N.
 [+] Dice rolls

wmshub wrote:
My ruminations on it...Spoiler (click to reveal)your already in process, I think the question is asking for an answer before that
 [+] Dice rolls

Just on a gut feeling, I think the optimal strategy is probably...Spoiler (click to reveal)Keep going until you see a price drop. The odds that the cards are in perfect ascending order is really low.
Assuming that they aren't, you're guaranteed not to get the worst price. And I suspect you're likely to get a low price often.Dearlove wrote:I'm going to reveal a spoiler someone posted, but only to say it's wrong.Good point. So my revised answer would be...Spoiler (click to reveal)Keep going until you see a price drop. Take it unless there is lower unseen price between it and the lowest number you've seen.

 Last edited Fri Jan 8, 2016 5:57 pm (Total Number of Edits: 7)
 Posted Fri Jan 8, 2016 4:50 pm
 [+] Dice rolls

First, let's get rid of the hundreds and call the prices n to n+4.
(I've switched to lowercase as it's easier on this phone and shows I've modified the problem.)
Let's creep up on this, assuming there are m cards.
m=1, you pay the price, additional cost zero.
m=2, it makes no difference whether you buy first or second, mean additionL cost 1/2.
m=3, you see a card, which I'll call k. It's random, and so is the second card, so you lose nothing by moving on. You might even gain.
Now the second card might be k2,k1,k+1 or k+2. Not all equally likely, the outside ones are half as likely as the inside ones. Let's consider those first.
k+2, clearly k=n, draw third card, additional cost 1. (I'm taking mean as read.)
k2, clearly k=n2, stop, additional cost 0.
k+1. k might be n or n+1, equally likely. If you stop, additional cost 3/2. If you continue you'll draw n or n+2, equally likely, additional cost 1. So you draw.
k1. Either you have n or n+1, additionL cost 1/2. If you draw additional cost 1 as above. So stick.
Now we have overall cost (doubling the latter two cases, dividing by 6) (1+0+2+1)/6 or 2/3.
OK, I'm not going to do 4 on this phone, and it's going to be very messy to do 5 this way. But maybe when I do 4 I'll begin to see a pattern 3 is still too simple.
(If this turns out to have a nice clean solution, especially one that generalises above 5, good problem. If it remains messy, less good problem.)
And before someone asks, yes, knocking up a program to do this by force wouldn't be hard. Just not what I feel like doing.

 Last edited Fri Jan 8, 2016 4:53 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 4:52 pm
 [+] Dice rolls
 I'm going to reveal a spoiler someone posted, but only to say it's wrong. Here I'll use the original formulation. If you draw 1000 then 1400 then 1300 the continue until you see a drop would buy now. But you know to wait until you see the 1100, as N must be 1000.
 [+] Dice rolls

My thoughts are basically similar to the WM Shub. Note that the +400/400 (etc) are symmetrical. For the 200/300 difference, take the missing (lower) middle number unless you see a number underneath both first. (If you get a number two under both, then you know N and can get N+100) This guarantees you no worse than N+300, and may get you better depending on the random ordering and which pair you got.
For the $100 difference, I suspect my thought is to take the next +100, unless a lower number is first (again with the caveat that if you identify a gap you can hit it). You may wind up paying the max in the specific case of (N+2, N+3, N+4) or (N+3, N+2, N+4) orderings, but that's not bad.
My second thought is that I'd love to deal with this car salesman, who apparently is only willing to screw me for $400, at worst.
There are 6 cases for each pair of first numbers
All 01  take 2
All 10  take 2
by symmetry, we can combine these, so for now i'll start again and ignore transpositions.
All 01  take 2
All 02  take 1
all 03  take 1
all 04  take 1
For the above, we'd have taken a number lower than zero ("N"), but it never shows up.
In the next cases, we take the first number that shows up lower than the first two, or the minimum number.
all 12  average of 1.5 (half take 0, half take 3, whichever comes first)
all 13  average of 1 (half take 0, half take 2, whichever comes first)
all 14  average of 1 (0/2)
all 23  Interesting, by rule we take the next number if it's lower, so we average 0,1 and 4, and get 5/3rds.
all 24  As above, we take the next number of it's 0, 1, or 3, so 4/3rds
all 34  take the next number, so 0/1/2 split, average 1.
So, 2+1+1+1.5+1+1+5/3+4/3+1 =
2+1+1+1.5+1+1+3+1=
11.5, but we have 10 cases, so average is N+1.15, or a mere $115 above book value. Much better than random.

 Last edited Fri Jan 8, 2016 5:05 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 5:04 pm
 [+] Dice rolls
 ¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı(MABBY)Canada
Chestermere
AlbertaThere are 10 types of people those who understand binary, and those who don't. 
My first thought is to get rid of N altogether and just create 5 cards that simulate the algebra.
If fair price (N) is $10,000, then you have 5 cards:
A) 10,000
B) 10,100
C) 10,200
D) 10,300
E) 10,400
For five cards, the unique combinations possible (nothing is repeated or returned to the original sample after drawing/ revealing) should be 5! which is 120.
So out of 120 possible outcomes, how much is the average price going to be if you pick the first card that you see?
I still don't know the answer I'm just hoping that this will cause someone else here to have a breakthrough that I'm missing.
 [+] Dice rolls

Update  doh! There is an asymmetry. Stupid. On the 40, you can take the zero! (etc) Hm. Redoing.
04  1
40  0
03  1
30  If you take the zero, great. But this could be the 41. In that case, you could take the one (by rule), or hope that the zero is out there. But you'd take the 0 or 2 first, which averages to one, so the best is to take the lower number you see first, which wins in the 30 case and breaks even in the 41 case.
02  1
20, 31, 42 If you just take the lower, you get 0,1,2 average. If you wait, you get 1, 1 (average of 0/2)), 4/3rds, which is (slighlty) worse.
10, 21, 32, 43  If you just take the 2nd you average 1.5
If you wait by my rule, you get, 2, 1.5, 5/3, 1.
OK, so yes, taking the first number less than a predecessor you see, unless you see a pattern like 032 you can wait for the 1, which is basically Thunkd's revised solution.

 Last edited Fri Jan 8, 2016 5:20 pm (Total Number of Edits: 2)
 Posted Fri Jan 8, 2016 5:16 pm
 [+] Dice rolls

MABBY wrote:If you just pick the first one, the combinations don't matter, the answer will be 1+2+3+4/10=$250 above N.
So out of 120 possible outcomes, how much is the average price going to be if you pick the first card that you see?
Worse than even my (inferior) first cut.
 [+] Dice rolls

Around here they 'advertise' that: "up to $150'documentation fee' MAY be added onto etc...", and weall just KNOW that these 'sleazy bastards' SHALL! So, 'moi' will unkindly inform them that I am going: "to cockpunch`em "OFF" = $1 for each & every $ of this 'fee'!" Let's then just "C" if anyone ELSE would have these becoming 'compliant' as well.
 [+] Dice rolls

(incomplete) Brute force approach:Spoiler (click to reveal)
If you draw until you have N and N+400, you know the range and can wait until you draw the lowest remaining card. That's what I'm going to call an end condition. I'm not sure how to decide if it's optimal to continue so I'm just going to play it out and see what happens.
Taken from the point of view of the buyer, here's what the set of cards will can look like after each draw. Red means we've reached the "end condition" and we know what price we'll pay and don't need to continue:
First Card:
1 {}: [X]
Second Card:
2 {X}: [X, X4] [X, X3], [X, X2], [X, X1], [X, X+1], [X, X+2], [X, X+3], [X, X+4]
Reassign X to lowest known value:
3 {X, X+3}: [X, X+3, X1], [X, X+3, X+1], [X, X+3, X+2], [X, X+3, X+4]
3 {X, X+2}: [X, X+2, X2], [X, X+2, X1], [X, X+2, X+1], [X, X+2, X+3], [X, X+2, X+4]
3 {X, X+1}: [X, X+1, X3], [X, X+1, X2], [X, X+1, X1], [X, X+1, X+2], [X, X+1, X+3], [X, X+1, X+4]
Going to four cards, readjusting and reordering:
4 {X, X+1, X+2}: [X, X+1, X+2, X2], [X, X+1, X+2, X1], [X, X+1, X+2, X+3], [X, X+1, X+2, X+4]
4 {X, X+1, X+3}: [X, X+1, X+3, X1], [X, X+1, X+3, X+2], [X, X+1, X+3, X+4]
4 {X, X+2, X+3}: [X, X+2, X+3, X1], [X, X+2, X+3, X+1], [X, X+2, X+3, X+4]
Five cards:
5 {X, X+1, X+2, X+3}: [X, X+1, X+2, X+3, X1], [X, X+1, X+2, X+3, X+4]
Ends up kinda tree like, huh? I've got to do some real work, so I'll save double checking my work and playing it out until later. But all the "red cases" have a value you'll pay. Each black case can be followed to a set of red cases so you can decide whether it is optimal to draw another card and if not, become red cases themselves. Each node (aka, red case) on the tree will have a "payout". Each node will be equally likely so average them all up for the answer.

 Last edited Fri Jan 8, 2016 6:21 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 5:55 pm
 [+] Dice rolls
 ¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı(MABBY)Canada
Chestermere
AlbertaThere are 10 types of people those who understand binary, and those who don't. 
I'm not positive that you know for certain that N+400 is the top price.
If the first price you see is N+400 and the next one is N+300, do you know that you're waiting around for N? I don't think so.
You're seeing random numbers with no idea of the gap between them beforehand.
 [+] Dice rolls

MABBY wrote:I'm not positive that you know for certain that N+400 is the top price.
If the first price you see is N+400 and the next one is N+300, do you know that you're waiting around for N? I don't think so.
You're seeing random numbers with no idea of the gap between them beforehand.
Your comments may apply to reality, but not to the problem as posed.
Edit: I take back my comment, I misread. If you see X+400 and X then you know X is N and X+400 is the top price, and you can wait for N+100 But if you see two values differing by 100 you don't know if they are N+400 and N+300 or N+100 and N, or something in between.

 Last edited Fri Jan 8, 2016 8:41 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 6:09 pm
 [+] Dice rolls

I've worked through the 4 card version in full and the mean overpayment is 7/8. (I'll post details if I get requests.) Note that this doesn't give you a strategy that is necessarily easily expressible.
My notation is something like that 1*01 means that you saw a k and a k+3 and now are holding a k+1.
With that notation we stop when in states *001 *01 *101 *011 *11 and may stop or continue in states *1 or 1*1
So now with 1 to 4 cards excess is 0, 1/2, 2/3 and 7/8. Or before reducing 0/1, 1/2, 4/6 and 21/24. I don't see a pattern yet except a wild guess that the excess never exceeds 1.
Edit: I omitted to mention the other continue states such as 10*1. (Can't be bothered to work out if any more, I just note obvious answer when clear such as that state, obvious value 1 with 4 cards.)

 Last edited Fri Jan 8, 2016 6:56 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 6:18 pm
 [+] Dice rolls

My strategy:Spoiler (click to reveal)Skip the first card. Then keep drawing until you hit one of these cases:
* you get to the last card, which you must take.
* You get a card lower than the first, which you should take.
* You get a card that is $400 more than the first. Once you have that, you know exactly what N was, and what cards are left, so then you can wait until the best remaining card appears.
The payoff:Spoiler (click to reveal)On average I overpay by exactly $110 with this algorithm.
Can it be done better?
Edit: Yes it can:Spoiler (click to reveal)If the draw is X, X+300, X+200, X+100, then you should stop; the next and last card may be $200 lower, or $300 higher, so on average stopping now is better even though it doesn't match my strategy above. Damn.

 Last edited Fri Jan 8, 2016 6:39 pm (Total Number of Edits: 4)
 Posted Fri Jan 8, 2016 6:35 pm
 [+] Dice rolls
 ¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı(MABBY)Canada
Chestermere
AlbertaThere are 10 types of people those who understand binary, and those who don't. 
Dearlove wrote:MABBY wrote:I'm not positive that you know for certain that N+400 is the top price.
If the first price you see is N+400 and the next one is N+300, do you know that you're waiting around for N? I don't think so.
You're seeing random numbers with no idea of the gap between them beforehand.
Your comments may apply to reality, but not to the problem as posed.the question wrote:...so without directly revealing the value of N, he takes five index cards and writes down a number on each of them...You have no idea if the next card will have a number higher or lower, or what the highest and lowest number are, by my reckoning.
The strategy to turn down the first card/ offer and then take the first card with a number that is lower than that was seems like a sound one, though.
 [+] Dice rolls

Haven't looked closely, but this looks very like the traditional submarine commander vs convoy problem a bit reworded.
You have been told to sink the largest ship in the convoy but have only one torpedo left and can only see the ships one at a time in sequence  how do you decide which one to fire at?
The answer is of the form: let the first so many (think it is sqrt(n)) ships pass and then sink the next one larger than those you have seen.
This is, of course, assuming that (as stated in the problem formulation) things are ordered randomly.
(edit) The fact that only specific integer sizes can occur does change the problem a little  if the difference between the first and second values is 400 or 300 you can make a much better choice and if it is 200 you can make a slightly better choice.

 Last edited Fri Jan 8, 2016 7:01 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 6:51 pm
 [+] Dice rolls

MABBY wrote:Dearlove wrote:MABBY wrote:I'm not positive that you know for certain that N+400 is the top price.
If the first price you see is N+400 and the next one is N+300, do you know that you're waiting around for N? I don't think so.
You're seeing random numbers with no idea of the gap between them beforehand.
Your comments may apply to reality, but not to the problem as posed.the question wrote:...so without directly revealing the value of N, he takes five index cards and writes down a number on each of them...You have no idea if the next card will have a number higher or lower, or what the highest and lowest number are, by my reckoning.
The strategy to turn down the first card/ offer and then take the first card with a number that is lower than that was seems like a sound one, though.
No, you're still missing that the set of cards is defined even if you don't know N, and your solution is suboptimum. But I'm not going to engage further if you just repeat your error.
Edit: Thumbing me was incredibly generous when my snark was in part a misreading, though the comment about no idea of the gap between them was wrong.
Fortunately I had already thrown a bit of GG at you for pointing this out, so I don't feel so bad. But my apologies.

 Last edited Fri Jan 8, 2016 8:43 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 6:59 pm
 [+] Dice rolls

andyholt wrote:Haven't looked closely, but this looks very like the traditional submarine commander vs convoy problem a bit reworded.
You have been told to sink the largest ship in the convoy but have only one torpedo left and can only see the ships one at a time in sequence  how do you decide which one to fire at?
The answer is of the form: let the first so many (think it is sqrt(n)) ships pass and then sink the next one larger than those you have seen.
This is, of course, assuming that (as stated in the problem formulation) things are ordered randomly.
It's more specialised than that because of the known equal spacing. I think the problem you note doesn't have that constraint. So you can improve on it.
 [+] Dice rolls

Dearlove wrote:
It's more specialised than that because of the known equal spacing. I think the problem you note doesn't have that constraint. So you can improve on it.
Yes, I've noted that in an edit.
Because of the small number of cases, an enumerated solution seems appropriate (which I gather is what you have done and I'm too lazy to)
 [+] Dice rolls
 ¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı(MABBY)Canada
Chestermere
AlbertaThere are 10 types of people those who understand binary, and those who don't. 
Dearlove wrote:No, you're still missing that the set of cards is defined even if you don't know N, and your solution is suboptimum. But I'm not going to engage further if you just repeat your error.I haven't offered a solution, I just asked what the average value of taking the first card would be. So +$250 is suboptimal, I agree.
However I still can't recognize N when it is looking me square in the face, is all I'm saying.
I can only get lucky by having it appear on the second card, otherwise I always overpay if it appears on the first card or would have appeared after some other card combination where there was a price drop and I took that instead.
 [+] Dice rolls
 HuzonfirstUnited States
Manassas
VirginiaBest hobby, with the best people in the world. Gaming is the best! 
Here's my strategy:Spoiler (click to reveal)Choose cards until you find one that's at least 200 less than a previously exposed card. The one exception to this rule is if you can deduce that a lower card is still in the stack. (For example, if the cards are, in order, 1000, 1400, 1200, wait for the 1100 card which you know must be there.) By following this rule, going through all the possibilities gives me an expected penalty of 92.5, which I think is lower than any answer we've seen. A math error is completely possible; plus, this isn't the elegant solutions we've seen in previous questions.
 [+] Dice rolls
 My not yet confirmed brute force answer is 108/120 or 9/10, or 90 dollars in the original problem. I'll post my solution for you to pick apart and find the errors in shortly.

 Last edited Fri Jan 8, 2016 7:41 pm (Total Number of Edits: 1)
 Posted Fri Jan 8, 2016 7:38 pm
 [+] Dice rolls
 I agree with Dearlove. I just finished it. The right strategy pays on average $90 over N. I used a computer to brute force the strategy; there doesn't seem to be a pattern, but there aren't very many distinct situations so you could probably work through them with paper and pencil if you have a little time.
 [+] Dice rolls