Recommend
2 
 Thumb up
 Hide
98 Posts
1 , 2 , 3 , 4  Next »   | 

BoardGameGeek» Forums » Everything Else » Chit Chat

Subject: The latest Friday math problem rss

Your Tags: Add tags
Popular Tags: [View All]
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
Full article is here: http://fivethirtyeight.com/features/how-badly-can-a-car-sale...

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?
1 
 Thumb up
5.00
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
maf man
United States
endeavor
Wisconsin
flag msg tools
mbmbmbmbmb
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
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bryan Thunkd
United States
Northampton
MA
flag msg tools
badge
Avatar
mbmbmbmbmb
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.

3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
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 k-2,k-1,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.)

k-2, clearly k=n-2, 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.

k-1. 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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
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.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brian Bankler
United States
San Antonio
Texas
flag msg tools
badge
"Keep Summer Safe!"
Avatar
mbmbmbmbmb
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.

1 
 Thumb up
0.02
 tip
 Hide
  • [+] Dice rolls
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brian Bankler
United States
San Antonio
Texas
flag msg tools
badge
"Keep Summer Safe!"
Avatar
mbmbmbmbmb
Update -- doh! There is an asymmetry. Stupid. On the 4-0, 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 0-3-2 you can wait for the 1, which is basically Thunkd's revised solution.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brian Bankler
United States
San Antonio
Texas
flag msg tools
badge
"Keep Summer Safe!"
Avatar
mbmbmbmbmb
MABBY wrote:

So out of 120 possible outcomes, how much is the average price going to be if you pick the first card that you see?
If you just pick the first one, the combinations don't matter, the answer will be 1+2+3+4/10=$250 above N.
Worse than even my (inferior) first cut.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Robert Wesley
Nepal
Aberdeen
Washington
flag msg tools
designer
badge
Avatar
mb
angry Around here they 'advertise' that: "up to $150-'documentation fee' MAY be added onto etc...", and we-all just KNOW that these 'sleazy bastards' SHALL! So, 'moi' will unkindly inform them that I am going: "to cock-punch`em "OFF" = $1 for each & every $ of this 'fee'!" Let's then just "C" if anyone ELSE would have these becoming 'compliant' as well.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sean Ahern
United States
Spokane
Washington
flag msg tools
badge
Avatar
mbmbmbmbmb
(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, X-4] [X, X-3], [X, X-2], [X, X-1], [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, X-1], [X, X+3, X+1], [X, X+3, X+2], [X, X+3, X+4]
3 {X, X+2}: [X, X+2, X-2], [X, X+2, X-1], [X, X+2, X+1], [X, X+2, X+3], [X, X+2, X+4]
3 {X, X+1}: [X, X+1, X-3], [X, X+1, X-2], [X, X+1, X-1], [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, X-2], [X, X+1, X+2, X-1], [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, X-1], [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, X-1], [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, X-1], [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.

2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
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.)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Andy Holt
England
Rayleigh
Essex
flag msg tools
This is not the cat you're looking for - some other cat maybe?
badge
tout passe, tout lasse, tout casse
Avatar
mbmbmbmbmb
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.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
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.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Andy Holt
England
Rayleigh
Essex
flag msg tools
This is not the cat you're looking for - some other cat maybe?
badge
tout passe, tout lasse, tout casse
Avatar
mbmbmbmbmb
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)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Huzonfirst
United States
Manassas
Virginia
flag msg tools
designer
badge
Best hobby, with the best people in the world. Gaming is the best!
Avatar
mbmbmbmbmb
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Christopher Dearlove
United Kingdom
Chelmsford
Essex
flag msg tools
SoRCon 11 23-25 Feb 2018 Basildon UK http://www.sorcon.co.uk
badge
Avatar
mbmbmbmbmb
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.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Billy McBoatface
United States
Lexington
Massachusetts
flag msg tools
KGS is the #1 web site for playing go over the internet. Visit now!
badge
Yes, I really am that awesome.
Avatar
mbmbmbmbmb
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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2 , 3 , 4  Next »   |