34
$\begingroup$

You and an opponent are playing the following game:

  1. Your opponent picks two different real numbers, however he wants to, and writes them on two cards, which he presents to you face down
  2. You choose one of the cards, and look at its value
  3. You say "the card I picked is higher" or "the card I picked is lower"
  4. Your opponent reveals his card, and if you were correct, you score a point. Otherwise, your opponent scores a point.

Your aim is to pick a strategy for this game such that your probability of winning each point is greater than 50%. To make it more difficult, there is an extra rule:

  1. You must tell your opponent your strategy before he picks his numbers, and stick to that strategy. He keeps his owns strategy secret.

Note

Your opponent is completely unlimited as to which numbers he picks, he can pick any real numbers, with any strategy he wants. Obviously this is a bit unrealistic, because some strategies would in reality be impossible to actually compute (e.g. if your opponent wanted to randomly pick two numbers from a flat probability distribution over all real numbers).

So to be clear, both you and your opponent have the magic ability to do arbitrarily precise mathematics in a short length of time, and are able to mentally generate random numbers from a probability distribution in a way that's not constrained by whether a real computer could do the same thing.

Rule clarifications

The main rule is: No cheating or loopholes. This is a mathematical logic puzzle, not an attempt to find a way around the rules. I'll try to close some of the more obvious ones here, but if any more come up that I haven't thought of, I'll add them here too.

  • Any number can fit on a card, even if in reality it would take an infinite amount of space.
  • Likewise, any number can be written onto or read from a card in a reasonable length of time, unrelated to how large that number is or how many digits it has.
  • The "magical" power for mental maths you and your opponent have is just about being able to do calculations or generate numbers from probability distributions that wouldn't normally be possible either because of arbitrarily precise numbers or arbitrarily large numbers. You're not psychic, or anything similar. So, for example, your opponent can't have the strategy "I'm going to write 5 on this card if my opponent is thinking about a cat, otherwise I'm going to write 6.2"
$\endgroup$
  • $\begingroup$ That's very odd! I wonder if such a solution to this question exist $\endgroup$ – Rafe Oct 5 '14 at 20:26
  • $\begingroup$ @Rafe It sounds impossible, but it can be done. $\endgroup$ – Ben Aaronson Oct 5 '14 at 20:50
  • $\begingroup$ Perhaps it would be better to say that the opponent draws a line of a given length instead of writing a number. It seems to avoid various loopholes more easily (it is clear that we may assume wlog that all numbers are from (0,1).). $\endgroup$ – Jakub Konieczny Oct 11 '14 at 0:51
  • $\begingroup$ @Feanor Hm, interesting idea. It at least seems to avoid the difficulty of writing numbers with ridiculously long representations. It still seems like it'd have a lot of loopholes to plug though- need to say there's no smallest unit of length, we have a microscope with infinite zoom, and we still need a magic RNG too $\endgroup$ – Ben Aaronson Oct 11 '14 at 0:56
  • $\begingroup$ You say "the card I picked is higher or the card I picked is lower". $\endgroup$ – Kevin Nov 3 '14 at 3:27
27
$\begingroup$

Step 1.

Decide on a function $M(x)$ that will map real number $x$ to the range $(0,1)$ such that if $y > x \implies M(y) > M(x)$. One possibility is $M(x) = 0.5+{1 \over \pi}\ tan^{-1}(x)$. But there are many other options. This effectively maps your opponents two real numbers onto a point in the $[0..1,0..1]$ square.

Step 2.

Randomly choose a card, read the number and apply your $M(x)$ function to generate a number $p$.

Step 3.

Generate a uniform random number $u$ in the range $[0,1]$ and if $p > u$ state "the card I picked is higher" (if $p < u$ make the opposite statement).

This works as follows:

Your opponent has chosen (by whatever means) two distinct numbers $x$ and $y$. The numbers are unknown but it is fine to arbitrarily label the smaller of their chosen numbers as $x$ and the larger as $y$ i.e. $x < y$. If you applied your mapping function to them then you generate numbers $p$ and $q$ such that $p < q$. You choose the card at random so you have a $0.5$ probability of picking each of $x$ and $y$.

If you chose the card with $x$ written on it (the lower of the two numbers) then you correctly claim the other card as the higher (and win) with probability $(1-p)$, and incorrectly claim $x$ as larger (and lose with probability $p$). So expected yield is $(1-p) - p = 1-2p$. Alternately if you chose the card with y written on it you guess incorrectly with probability $(1-q)$ and correctly q, with expected yield $2q-1$. Combining these (and dividing by two, as initial choice of each card occurs 50% of the time), your expected score per round is $0.5 \times (1-2p +2q-1) = q-p$. But $q > p$ because $M(y) > M(x)$ because $y > x$, thus your expected score is strictly greater than zero (i.e. positive).

This will work for any function M that monotonically maps reals into the interval $[0..1]$. Depending on your M function your opponent can choose their number pair in such a way as to make your expected profit arbitrarily small, but it will always be strictly positive.

$\endgroup$
  • $\begingroup$ Yep, exactly right $\endgroup$ – Ben Aaronson Oct 5 '14 at 22:15
  • 1
    $\begingroup$ your step 3 would be clearer by just saying "keep you choice with probability $M(x)$". $\endgroup$ – Denis Oct 6 '14 at 15:38
  • $\begingroup$ Awesome! What's the most amazing to this puzzle is that your opponent can do nothing about it :) $\endgroup$ – Bogdan Alexandru Jan 8 '15 at 8:52
  • $\begingroup$ "Generate a uniform random number in the range [0,1]" -- I don't think that's possible, so your method breaks down fairly early. $\endgroup$ – Chris Jefferson Apr 6 '16 at 16:52
  • 1
    $\begingroup$ @ChrisJefferson, you don't need the exact value of the random number to compare the sizes; just keep rolling a d10 for the decimal places until you get a result for the comparison. (further digits won't change it.) $\endgroup$ – Bass Jan 2 '18 at 10:05
13
$\begingroup$

Penguino's answer is correct, but I'll add this just to give a bit of a conceptual explanation for people to understand why the problem is less impossible than it seems.

The key point here is that your opponent only gets to choose the two cards, not which of the two you pick. If he could choose which card you got, then you'd truly be sunk.

The next thing to realise is that to win more than 50% of the time, all you need to do is ensure the following statement is true:

If you pick the higher card, your probability of saying "higher" will be greater than it would be if you pick the lower card.

In other words,

if when you say "higher", you're right slightly more often than you're wrong (and, by implication, the same thing is true when you say "lower"), then you'll do better than 50%.

To see this is true with some light maths,

say that your probability of saying "higher" for the low card is $p$, and for the high card is $p+k$ (where $k$ is positive).

Then,

your probability of correctly saying "higher" is $(1/2)(p+k)$, where the $1/2$ is the chance of getting the higher card, and $p+k$ is the chance of then saying "higher".

Now doing the same for saying "lower", assigning the probability of saying "lower" for the high card to $q$, you get the chance of correctly saying "lower" as being $(1/2)(q+k)$

So your total chance of success is

$(1/2)(p+q+2k)$.

Noting that, from the definition of $p$ and $q$, $p+q+k = 1$, then the chance of success is $(1/2)(1 + k)$, which is greater than 50% as we want.

So now all we need to do is make sure that the above italicised statement is true, and it's relatively straightforward to see why Penguino's answer achieves that.

$\endgroup$
  • $\begingroup$ How would you map any real number? For any real number, there is always a higher one, and though your opponent's strategy can't change, his strategy could be to provide arbitrarily large positive or negative numbers so that it would be impossible to guess statistically where the next number would lie. I'm probably missing something. $\endgroup$ – Neil Oct 6 '14 at 7:55
  • $\begingroup$ @Neil See Penguino's answer, his function M(x) achieves this. Another function that I think would work is $sign(x-0.5)/(0.5 - Abs(x-0.5))$, where $sign(x)$ is 1 for any positive number, -1 for any negative number, and 0 for 0. $\endgroup$ – Ben Aaronson Oct 6 '14 at 8:37
  • 1
    $\begingroup$ @Neil But as a side note, as the size of the numbers your opponent picks gets larger, and the distance between them smaller, your chances very rapidly get extremely close to 50%. But they never quite get there $\endgroup$ – Ben Aaronson Oct 6 '14 at 9:17
  • $\begingroup$ Absolutely any mapping M(x) from the reals [-inf...+inf] to the line segment [0..1] will do, so long as M(x) < M(y) iff x < y. $\endgroup$ – Penguino Oct 6 '14 at 21:31
  • $\begingroup$ And for anyone who thinks "If you pick the higher card, your probability of saying "higher" will be greater than it would be if you pick the lower card" is begging the question a bit: it helps to realize the mapping M strictly excludes the values 0 and 1: "... M(x) that will map real number x to the range (0..1)", whereas the random number you're comparing it to is uniformly chosen from the range including both 0 and 1: "Generate a uniform random number u in the range [0..1]". The heart of this solution is in the shape of the brackets :) $\endgroup$ – Dan Bron Feb 17 '15 at 20:26
1
$\begingroup$

I'm not sure if this should count as a quick counterstrategy for the opponent but.. if there exists a true random number generator that can produce numbers in $[0,1]$ to use for the strategy Penguino posted, can't the opponent just use that same random number generator to produce two real numbers for this game to make it a 50% chance of winning?

I want to think that using the defined function that maps all real numbers to a range where you can use a random number generator as defined in Penguino's answer is good, but knowing that the player must stick to their mapping function, the opponent can create two sets, one that maps to a win and one to a loss and flip a coin.

With the given $M(x)$, the opponent can flip a coin and pick $0$ and $1$ if heads and $0$ and $-1$ if tails.

(I couldn't post this as a response to the previous answers because I'm still very new to puzzling.stackexchange, I don't have enough points...)

$\endgroup$
  • $\begingroup$ No, there's no such thing as a set of two numbers that maps to a win under Penguino's strategy. Every set of two numbers results in it being more likely than not to win, but not a certain win. $\endgroup$ – f'' Mar 10 '16 at 2:37
  • $\begingroup$ Oh, I think I get it, my 0, -1 and 0, 1 example doesn't work because it'd pick the higher number more often in the strategy. But what about just rolling two random numbers for the set? $\endgroup$ – Acuity Mar 10 '16 at 2:56
  • $\begingroup$ As explained in the other answer, the key part of the strategy is that "If you pick the higher card, your probability of saying "higher" will be greater than it would be if you pick the lower card." This is true regardless of how the numbers are chosen. $\endgroup$ – f'' Mar 10 '16 at 3:13
  • $\begingroup$ Remember that the opponent has no control over which of the two numbers you pick $\endgroup$ – Ben Aaronson Mar 10 '16 at 11:25
  • $\begingroup$ Ah, thanks! After thinking about it for a bit, the answer makes sense now - the probability of saying higher will be greater than the probability of saying higher for the lower card in all cases. For the 0 and 1 or -1 and 0 examples are actually pretty big differences - 0 is picked as higher 50% of the time, 1 is picked as higher 75% of the time, and -1 is picked as higher 25% of the time. Given that each are picked with equal chance, this makes it a 62.5% chance of success in the 0 and 1 case, and similarly a 62.5% chance of success in the -1 and 0 case. $\endgroup$ – Acuity Mar 10 '16 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.