Card Matching Game

[Scuttlemutt]

A man challenges a woman to a card matching game. Using a standard 52 card deck (two colors, four suits, 13 of each suit), all of the cards are placed on a table and the woman must turn them over two at a time, and if they match she may remove them and if they don't match they are flipped back over. However, because a single deck will not have any naturally matching cards, a 'match' in this case will be considered to be a card with the same number and color (But not suit). In order to win, she must remove all of the cards from the game.

The woman brags that this will be easy for her, because she tells the man (truthfully) that she has a perfect memory, and even tells the man what order she will turn the cards over in. Upset, the man decides to purposefully arrange the cards so that it will take the woman the longest possible time to finish the game. Assuming the woman does not deviate from the strategy she explained to the man, how many turns would this game take to finish? (One 'turn' is two cards being flipped, and either removed or put back)

Recap:
-The woman has a perfect memory, so once she flips over a card she will never need to again until its match is found.
-The man knows the exact order she will flip cards over in.


I don't have a confirmed correct answer, but this is the best I could come up with.

Spoiler:

51 turns.

[sfwc]

I get a slightly different answer:

Spoiler:

Suppose that the woman knows that 2 cards match. She's no better off if she immediately removes that matching pair than if she waits a bit and looks at some other pairs first. In fact, she may as well leave all the turns on which she knows she will removing a matching pair until the very end. Then before she starts making those moves, she has to identify which cards match which. Of course, if the man knows the order in which she'll look at the cards, then he can arrange them so that she has to look at all but 1 of the cards before she knows which pairs match. That takes at least 26 turns. Then she has to remove all the matching pairs, which takes another 26 turns, giving a total of 52. And of course, she can always succeed in 52 turns, by first looking at all the cards (2 at a time) then removing all the matching pairs.

Here's a related problem. Suppose that when the woman picks 2 cards she does it 1 at a time. So she can look at the first card she picks before picking the second. Again, she reveals her (deterministic) plans, and again the man arranges the cards fiendishly. How many turns does she need?

Edit: On second thoughts, I guess that my `related problem' must be the problem you originally meant. So here's the solution:

Spoiler:

As you claimed, the answer is 51. The man can ensure that the woman needs at least 51 turns as follows: he ensures that, where possible, when the woman looks at a fresh card, it matches a card she has previously looked at exactly when it is the second of the pair to be looked at. He can always do this except on the first turn or if she has seen cards of all kinds, so for at least 25 rounds. As long as he keeps it up, she may as well not reveal any matching pairs (as in the argument above). So she takes at least 25 + 26 = 51 turns. On the other hand, she can always succeed in 51 turns, by using the first 25 turns to determine the identities of 50 of the cards, then the next 2 turns (1 turn if they match) to remove the 2 remaining cards, each with the card it matches, and the final 24 (25 if they matched) turns to remove all the remaining pairs.

[thc]

I don't understand the problem. If she sets the order she will turn the cards over, beforehand, without being able to deviate with new knowledge, can't the man just arrange the cards so that she won't match any cards for a very long time? This obviously doesn't make sense, since it doesn't make use of her perfect memory, so I think I'm missing something.

[t1mm01994]

I don't understand the problem. If she sets the order she will turn the cards over, beforehand, without being able to deviate with new knowledge, can't the man just arrange the cards so that she won't match any cards for a very long time? This obviously doesn't make sense, since it doesn't make use of her perfect memory, so I think I'm missing something.

Example of a strategy: I will flip 1 random card, and I name it A. Then, at some other point I will start flipping cards in pairs to reveal the card until I found the matching card with A. I will remove the pair, and start from the beginning.
Completely deterministic, but completely uncounterable.

[thc]

I don't understand the problem. If she sets the order she will turn the cards over, beforehand, without being able to deviate with new knowledge, can't the man just arrange the cards so that she won't match any cards for a very long time? This obviously doesn't make sense, since it doesn't make use of her perfect memory, so I think I'm missing something.

Example of a strategy: I will flip 1 random card, and I name it A. Then, at some other point I will start flipping cards in pairs to reveal the card until I found the matching card with A. I will remove the pair, and start from the beginning.
Completely deterministic, but completely uncounterable.

So she tells the order which she'll flip over the first card, but then gets to choose during the moment which second card she'll flip over?

edit: i guess I didn't think about this problem well enough

[EtherealScorpions]

27 turns at most.
If she remembers BOTH cards, and then flips other pairs, the first time she sees one of the original cards, she immediately picks up its counterpart. It'd take her 26 turns to reveal all the cards, and one more to get the pair.

[rigwarl]

@thc

I suppose she's allowed to have a predetermined strategy with different choices based on whether she has seen the card before. E.g., Flip over next card, if it's something I've seen before, match. Otherwise, flip over the next unknown card (number the cards from 1-52 to pick next).

@Ethereal
It uses up a turn to perform a match.

[mathmaniac31]

Spoiler:

Assuming she uses the optimal strategy of whenever she sees a pair she matches, the most amount of moves she can take is 39.
lets just say there are 52 cards numbered 1-26. If it is set up so she doesnt see a pair, she uses 13 moves to know the know where the 26 first cards are. Then, any card she reveals she will know the match to. Therefore, it will take her 26 more moves to match them. 26+13 is 39 moves. If he takes a different strategy and reveals pairs before she reveals every card, she just matches it, and it still would take exactly 13 moves of revealing 2 cards, and 26 moves of revealing 1 unknown card and selecting 1 known card to match. Therefore, unless the man uses a self defeating strategy in which he allows her to match 2 unknown cards by luck in one move, her minimum AND maximum number of moves is 39.

[Scuttlemutt]

Actually, the strategy I came up with for the man is this:

Spoiler:

The first card the woman flips over must always be a new card, because she hasn't seen any before. The second card can either be another new card, or the match to the first card. Obviously the latter is not ideal for making it take the longest possible amount of turns, so it's then another new card.

From every turn after this point, if the first card flipped over is one that was previously seen, then she will match it, so the man has to avoid this if possible. The second card will end the turn whether it is a new card or one that was previously seen, so ideally he will make it an previously seen card because not only will she still have to spend another turn matching that card regardless of when it turns up (as long as it's not the match of the card that was also turned over this turn), but also the pool of cards she will be unable to match if they turn up will stay as high as possible.

So the end result is something like this:
Turn 1: 2 new cards (2 unmatched, 50 unknown)
Turn 2: 1 new card, one old card (1 potential pair, 2 unmatched, 48 unknown) -One of the flipped cards, becomes an unmatched, and the second card turns itself and one of the unmatched into a potential pair
Turn 3: Match old cards (1 pair, 2 unmatched, 48 unknown)
Turn 4: 1 new card, one old card (1 pair, 1 potential pair, 2 unmatched, 46 unknown)
Turn 5: Match old cards (2 pairs, 2 unmatched, 46 unknown)

-Repeating this pattern, on average one new card is revealed each turn, and one match is made every other turn. This suggests it takes as many turns as there are cards to finish, but because the first turn is an exception to the pattern and revealed two new cards, the highest possible amount of moves is one less than that. So it will continue on until:

Turn 46: 1 new card, one old card (22 pairs, 1 potential pair, 2 unmatched, 4 unknown)
Turn 47: Match old cards (23 pairs, 2 unmatched, 4 unknown)
Turn 48: 1 new card, one old card (23 pairs, 1 potential pair, 2 unmatched, 2 unknown)
Turn 49: Match old cards (24 pairs, 2 unmatched, 2 unknown)
Turn 50: There's only two cards left, so this must turn over an old card. Match it (25 pairs, 1 unmatched, 1 unknown)
Turn 51: Last card must be an old card. Match it (26 pairs)

Sorry, I edited this post a few times after posting it. I'm anal about grammar/spelling like that. And also I started counting from the wrong number on one occasion.

And yes, I meant that she defined a general strategy to follow which tells exactly how she will determine which card she picks when looking for a new (unrevealed) card to turn over. For example "I'll always pick the card closest to me. If two are equally close, I'll pick the one among them that is furthest to my left."

[Turtlewing]

Spoiler:

Since the woman is stated as telling the exact order she will turn over cards and is unable to deviate, she will have to have a strategy that would by brute force iterate over all possible configurations of cards (no other strategy can be guaranteed to solve all cases). The man then simply selects the last patern over which she itereated and arranges the cards to match it.

I think this works out to be something like 52! * 26 moves assuming a "move" is fliping two cards. That's the number of permiatations of the cards times the number of moves to fully solve one permeation.

The real solution is probably lower however as subsets of the final permeation will be removed by earlier iterations that share that subset of the positions in common, but I have no idea how to calculate that

Edit: After reading further in the tread it looks like the question wasn't meant to be interpreted the way I did so the above will be incorrect for the spirit of the puzzle.