# Maximizing the product of two numbers in a set given their differences

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.

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.

• 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 at 3:11
• Also, shouldn't there be 3 (4-1) zeros left in Case I, and 4 zeros left in Case II? – KD89042 Feb 24 at 3: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 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 at 10:23
• I assumed (incorrectly!) that aces were face cards – KD89042 Feb 28 at 1:02