1

This is an interview problem from Glassdoor that I've been unable to solve.

You have all the clubs from a deck, 13 cards, and you can choose 2 from the deck and get paid their product, where all face cards are considered to be 0. You can pay $1 to reveal the difference of any two cards you choose, how much would you pay to play this game?

The answer given is "$79, because the 9 and 10 cards can be found in 11 steps", with no further explanation. Is this answer correct, and if so, how does one arrive at it? I tried diagramming out possible combinations of questions, but that method seems intractable.

KD89042
  • 35

1 Answers1

2

Note: as suggested by the comment below from @user284873 there is an ambiguity in the problem. In my solution below I assumed that we are told the signed difference between the two cards. That is, if I point to $a$ and $b$ I am told $a-b$, as opposed to the absolute difference $|a-b|$. I have not considered the analogous problem where you are told the absolute difference...that might be an interesting variation.

It's clear that you can guarantee getting the $9,10$ if you pay $\$11$. To see that:

Pick a card and start to collect the differences.

Case I: you started with a $0$. In that case there are two $0's$ left out of $12$. You are sure to hit at least one of those in the first $11$ tries. Once you know you have a $0$ you can read off all the other cards from their differences. Seeing $11$ choices certainly determines the final, untested, choice.

Case II: you start with something other than $0$. In that case, there are three $0's$ left so in $11$ tries you are sure to get at least two. Once you see the same difference twice, that will tell you the value of the card you started with and again the $11$ known values will determine the final one.

Note: all this shows is that if you pay $\$11$ then you can guarantee the $\$90$ win. You might be able to do it more cheaply, if you are lucky. For instance, if your first two differences are $10,1$ then you know you started with the $10$ and that the second test card is the $9$. Thus you should be willing to pay more than $\$79$ though computing the exact amount seems like a tedious computation.

lulu
  • 70,402
  • Thank you, that makes total sense!

    How did you figure this out? Was it just immediately apparent to you, or were there certain methods/ways of thinking you used? I've spent 5-10 hours thinking about the problem and got nowhere, so I'm curious how I can improve on future problems.

    I'll try to compute the exact amount now as an exercise

     – KD89042 Feb 24 '19 at 03:11
  • Also, shouldn't there be 3 (4-1) zeros left in Case I, and 4 zeros left in Case II? – KD89042 Feb 24 '19 at 03:16
  • You didn't say how Aces were treated. I guessed that they were $1$. If you say they are $0$ then you can modify the argument (that will change the true expectation but I don't think it will change the worst case). – lulu Feb 24 '19 at 10:20
  • To your first question: Lots of decision problems depend on a "witness". One reliable source of information. Here, if you had one value that you knew you could easily get all the others. You don't quite have that, so I tried the next best thing. As I say, however, this method only gets you a lower bound on the price. The exact fair value seems to depend on a lot of special case work. – lulu Feb 24 '19 at 10:23
  • I assumed (incorrectly!) that aces were face cards – KD89042 Feb 28 '19 at 01:02
  • What if I started with 5, the difference between 5 and 10 is 5, the difference between 5 and 0 is 5. How can I know which one is 10? – user284873 Nov 15 '20 at 02:50
  • @user284873 Been a while since I thought about this. More broadly, my case $2$ claim that you know the value of your card once you see the same value twice is incorrect. If, say, you see the value $1$ twice then there are lots of ways to explain that. (you could have the $n$ and compared it to the $n+1$ and the $n-1$ and so on). Of course the pattern of differences defines the number uniquely but it's not obvious how many you need to draw.to get the value. I'll think about it when I wake up. – lulu Nov 15 '20 at 11:04
  • @user284873 Ah, no. My solution assumes, as the problem says, that you are told the difference, not the absolute difference between the two cards. Thus $5-10=-5$ and $5-0=5$. I will edit to clarify that I was reading the problem that way. Of course, it might be interesting to solve the problem wherein you are told the absolute difference instead. – lulu Nov 15 '20 at 11:11