22
$\begingroup$

Alice and Bob play the following game with two (identical) standard decks of $52$ cards.

  • First Alice secretly arranges one deck of $52$ cards in a long row on the table. All cards are face-down, and Bob has no knowledge of the positions of any of the cards.
  • Then the game goes through several rounds. In every round, Bob first pays $1$ Euro to Alice. Then Bob arranges the second deck of cards in a long row on the table, parallel to Alice's row and with all the cards face-up. Then Alice tells Bob all the face-up cards in his row that agree with the corresponding face-down cards in her row. Then the next round starts.
  • The game ends, as soon as Bob knows the positions of all the face-down cards in Alice's row. Bob then receives $x$ Euros from Alice.

Question: What is the smallest value of $x$, for which Bob can still avoid (with absolute certainty) to lose any money?

$\endgroup$
6
  • 8
    $\begingroup$ I might be missing something, but what determines $x$? It doesn't seem connected to any other action. $\endgroup$
    – DylanSp
    Mar 3, 2016 at 14:41
  • 1
    $\begingroup$ When Alice identifies the matching cards, does she say exactly which cards or correct, or just the number of cards that are correct? (i.e. does she say 2 of diamonds is correct, or just that 1 card is correct) $\endgroup$
    – Brian J
    Mar 3, 2016 at 16:53
  • 1
    $\begingroup$ What happens if Alice tells Bob all but 2 cards are correctly positioned? At that point, Bob knows that the 2 cards not correctly positioned must be swapped, so he now knows the positions of all the face-down cards. Does the game end immediately, or does he have to play another round (and pay Alice again)? $\endgroup$
    – cjm
    Mar 3, 2016 at 19:52
  • 1
    $\begingroup$ @cjm: The game ends, as soon as Bob knows the positions of all the face-down cards in Alice's row. $\endgroup$
    – Gamow
    Mar 3, 2016 at 19:56
  • 2
    $\begingroup$ @DylanSp A similar formulation in an earlier question of Gamow's had me puzzled for a while too. x is simply defined as the smallest payoff for which Bob is guaranteed to be able to make a non-negative profit, and we have to funds its value. (In the other question, x was the payment and the prize was fixed.) $\endgroup$
    – Oliphaunt
    Mar 16, 2016 at 21:16

6 Answers 6

19
$\begingroup$

An upper bound

51 Euro.

Bob picks a random permutation of the deck and then rotates the subset of his deck that does not match Alice's. The worst case is when the whole deck is a rotation of his initial permutation, in which case he has to rotate 51 times.

$\endgroup$
7
  • $\begingroup$ Wouldn't the upper bound be 52? Worst case he rotates 51 times, but he still has to pay for that first round, too. $\endgroup$
    – ricksmt
    Mar 3, 2016 at 19:12
  • 5
    $\begingroup$ He doesn't have to make the 51st rotation though. After 50 rotations (51 attempts) he knows every position, even if he hasn't got any cards right yet; every card has only one unattempted position $\endgroup$ Mar 3, 2016 at 19:59
  • $\begingroup$ Yeah, I think my answer was a bit unclear regarding this. As @frodoskywalker pointed out, he doesn't have to attempt/pay for the last rotation but the solution is obtained after 51 rotations in the algorithm described above. $\endgroup$ Mar 3, 2016 at 20:22
  • $\begingroup$ The worst case is the most instructive to me: Bob learns nothing that makes his job easier for the first 50 rotations. $\endgroup$ Mar 3, 2016 at 23:38
  • $\begingroup$ @BenJackson Of course he does. Even if no cards are in the correct position, right off the bat he reduces the initial possibilities $\left(52!\right)$ by a factor of $e$; think of derangements. $\endgroup$ Mar 4, 2016 at 0:53
6
$\begingroup$

I think the worst case scenario is 52 tries. That scenario is where each guess (until the last) is completely wrong. Your first guess is shifted by 1, and subsequent guesses are just shifting the cards, but in the wrong direction. On the 52nd guess, all the cards will line up. Since you can disregard the last guess (you know the guess), Bob has to pay 51 Euro.

That's an unlikely scenario, since you're likely to make some right guesses during that time; you just skip over those cards when shifting.

$\endgroup$
1
  • 1
    $\begingroup$ I don't think you've shown that Bob can't avoid this worst case by doing something clever (not just rotating guesses). I don't think he can, but no answer has yet convinced me of that. $\endgroup$ Mar 4, 2016 at 15:11
5
$\begingroup$

A lower bound is

$51$.

Represent the game as a bipartite graph $G$ on the set of cards and the set of positions. The game starts with a complete bipartite graph. Every turn, Bob guesses a perfect matching (of the complete bipartite graph). For each guessed edge $ab$, if Alice says it is wrong, then $ab$ is removed; otherwise, all other edges adjacent to $a$ and $b$ are removed. If at any point an edge is impossible, i.e., not in any perfect matching, then it is removed. The game ends when only one perfect matching remains.

Alice's adversarial strategy will be to say that a card $a$ is in the correct position $b$ only if she has to, i.e., $a$ and $b$ are adjacent only to each other in $G$. Then an edge is only ever removed when either Bob guesses it or it is impossible. Call a card elusive if it has only ever had adjacent edges removed through guesses by Bob, not because they were impossible. Call a connected component of $G$ elusive if all of its cards are elusive.

Claim: $G$ always has an elusive connected component.

Proof: $G$ starts as one elusive connected component. Suppose at some point in the game, the impossible edge $xy$ is removed from the elusive connected component $C$ with set of cards $X\ni x$. Then there is $U\subseteq X\setminus\{x\}$ that violates Hall's condition in $C-x-y$ but not in $C$, so $|U|=|N(U)|$. Then $U$ must be matched with $N(U)$, so every edge between $X\setminus U$ and $N(U)$ can be removed to leave an elusive connected component induced by $U\cup N(U)$.

When Bob finally knows the correct order, only one perfect matching of $G$ remains. By the claim, there is some elusive card $a$ which has degree $1$ but has only ever had adjacent edges removed through guesses by Bob, requiring at least $51$ guesses.

$\endgroup$
4
$\begingroup$

If we can agree that not knowing a card is always less informative than knowing a card, then I guess we can show the lower bound too. I'm not exactly sure how obvious this assumption is.

Carl's suggested strategy maximizes information in the sense that in each turn there is no dead guess for any card. Even when guesses are wrong, on each turn and for each card at least one possibility is excluded. The only way to do better is by guessing some other card right (thus excluding more possibilities). Therefore, in the worst case scenario, on each turn and for each card we exclude exactly one possibility, so that after $51$ turns we are done.

Another way to think of this is as follows. Rather than consider the worst case scenario for finding out the entire sequence of cards, consider the worst case scenario for finding out a single given card, say the first. On each turn, we can exclude at least one possibility for the first card, so the worst case scenario cannot be worse than $51$ turns. On the other hand, the only way we can do better is if, before then, we guess some other card right and that guess had not yet been made for the first card.

In the worst case scenario, these correct guesses don't happen (here is where I've used the assumption). In other words, the worst case for guessing correctly the first card is $51$ turns. Surely, the worst case for guessing correctly the entire sequence can't be better, so it too must be $51$ turns.

$\endgroup$
3
  • 1
    $\begingroup$ You're assuming that it's always possible for no correct guesses to happen, but that isn't necessarily true. In a simpler case with five cards, guessing ABCDE BCADE CABDE is guaranteed to get at least one match. $\endgroup$
    – f''
    Mar 4, 2016 at 23:37
  • $\begingroup$ I can see how that is problematic, but when looking at a single card this doesn't quite adress the problem of 'and that guess had not yet been made for the first card'. Granted, the 'proof' (if you can call it that) is definitely flimsy, but I there's something to it. Specifically, the idea of looking at a single card; that should be easier. $\endgroup$ Mar 5, 2016 at 2:21
  • $\begingroup$ @f'' - I'm almost convinced that by using some method of guessing like you described, that one can force enough matches such that we can do better than 52 as an upper bound. $\endgroup$
    – TTT
    Mar 22, 2016 at 16:49
3
$\begingroup$

The optimal worst case it requires

51 tries

To show that, Try the game with 2 cards, let's call them A and B. In the worst case;

A B (all face down)

B A

would be the first try. So Alice would not tell anything since no match up is available. In the game rule it is stated that;

The game ends, as soon as Bob knows the positions of all the face-down cards in Alice's row. Bob then receives xx Euros from Alice.

So before the next game begins, Bob knows the positions and he gets the money, which should be 1€ at least! So with two cards, 1 try is enough to find at worst optimal case.

For 3 cards;

A B C

B C A

Then no response from Alice; Next try will be (unluckily)

A B C

C A B

Then Bob knows all face down cards automatically, so 2 tries would be enough. Then 2€ for 3 cards.

For 4 cards; it makes 3 tries and 3€ not to lose any money at least!

As a result;

For 52 cards it has to require 51 tries and 51 Euros at the worst optimal case! At worst case, Bob will strangely never find any card until the last try, which is kinda very low chance!

$\endgroup$
3
$\begingroup$

The smallest value of x, for which Bob can still avoid (with absolute certainty) to lose any money is:

€51

He starts off knowing Alice's order is one of 52! orders. Let us imagine Bob can keep a list of this vast amount of orders. When he pays €1 he receives some information: "these positions are correct and the rest are not". He now deletes impossible orders and will have a smaller number of possible orders left - those forming the intersection of those orders that match at positions he has matched so far and those that do not match any of his attempts so far at positions he has not yet matched.

If, in any round, Bob:

  1. places a matched card in an as yet unmatched position;
  2. places an unmatched card in a matched position; or
  3. places an unmatched card in a position he has already tried for said card

...then he will receive some information he already knew (he knew that card did not go there) and hence will, in expectation, reduce his list of possible orders by less than if he avoided doing so.

Furthermore, since he will know Alice's order if he matches all but two positions, he should

  1. avoid possible orders that include any pairwise transpositions of two positions of previously unmatched cards

...as there is a chance he will get this information for free. Note, however, that this does not affect the worst case performance, but does affect the expected performance (see this follow up question).

One way, and by far the easiest, to assure he avoids all four of these scenarios is the cycling unmatched cards method given by Carl Löndahl.

Since Bob is avoiding at least 1. 2. & 3 to maximise his information and the information gained from making a match is at least as much as the information gained from making a non-match, the worst case is necessarily not matching any cards all the way to round N-2 and then matching some number (possibly zero) of the cards in round N-1 which then reduces his possible orders to 1.

If we label Bob's order as
(0,1,2,3,...,N-2,N-1)
then for a cycling of unmatched cards there are two worst case orders for Alice to have chosen, if we cycle rightwards then
(1,2,3,...,N-2,N-1,0) has no matches in round N-1, and
(2,3,...,N-2,N-1,0,1) matches all in round N-1;
if instead we cycle leftwards they would be
(N-1,0,1,2,..,N-2) and
(N-2,N-1,0,1,2,...) respectively.


As an example of the fourth point one can compare Carl's method with choosing the first of the possible orders when they are listed in lexicographical order for all cases of a four card game. If we label Bob's starting choice as (0,1,2,3) and have him cycle leftwards, then his costs for each of the 24 orders Alice could choose are:

Comparison of cycle unmatched with next lexicographically available order

When using the first lexicographically listed order, when Bob does not match any in the first round using (0,1,2,3) then his next round choice will be (1,0,3,2), which, while being a possible order, happens to be two pairwise transpositions of his first round attempt. This helps him in one of the two worst cases he would experience from cycling unmatched cards (if he was cycling rightwards it would help him with the other instead), but hinders him in three cases. The worst case scenario is the same, but the expected cost rises from $\frac{43}{24}$ to $\frac{45}{24}$.

$\endgroup$
6
  • 1
    $\begingroup$ The idea is certainly correct, and explained in more detail than other answers, but I don't quite see how it solves the actual shortcomings of previous answers. $\endgroup$ Mar 17, 2016 at 8:30
  • $\begingroup$ @Fimpellizieri - much like your answer Bob tries to maximise the relevant information he receives whenever he pays; the only extension really is to note that if he ever makes a match he gains nothing by subsequently either moving those cards to another position or from moving any other card into those positions (Thus the attack made by f'' does not pay dividends - the rounds posted for a five card game are only worthwhile if only D and E matched on rounds 1 and 2, in which case the worst case is then matching one more on round 3 whereupon another round is required equalling the worst case). $\endgroup$ Mar 17, 2016 at 23:48
  • $\begingroup$ I missed out: or subsequently placing an unmatched card in a position it has already been. $\endgroup$ Mar 18, 2016 at 0:17
  • 1
    $\begingroup$ Yes, there is certainly 'waste' of guesses in the guesses of f'', but it is still unclear (as is in my rather hand-wavey answer) whether or not some other strategy can do better. $\endgroup$ Mar 18, 2016 at 5:28
  • $\begingroup$ Put it another way: you showed that there is an 'information-maximizing' strategy with a worst case of $51$. It remains to show that there is no (information-maximizing) strategy with a worst case of $50$ or less. $\endgroup$ Mar 18, 2016 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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