Imagine you and four friends deal out a hand of a game of poker, and look at your hands. Each person is dealt 5 cards, and the remaining 27 cards are still in the deck. Unfortunately, the game is interrupted before it has a chance to start. You decide to memorize your hands, and play the hand tomorrow. The next day, you want everyone to somehow get the same 5 cards they had yesterday out of a shuffled deck, without gaining any information about what cards the other players have. All players are assumed to be honest, and will not cheat in any way.

This puzzle is my own design. I will eventually post the solution in the comments, but if you solve it before then, show off and post your own solution.

I take my cards. Everyone else shuffles the deck. I put my cards back in random places, remembering where they went, but not looking at the rest of the cards.

At this point I know where in the deck my cards are, but for each of the other positions in the deck I don’t know what card is in that position.

We’ll go through each person in turn until we can say the same of everybody.

In general, the person whose turn it is takes the deck and finds their cards. They take them out, announcing the position where they found each one. This way, the people who have already been can keep track of where their cards are. Then the people who have already been work together to secretly apply some permutation to the deck, each keeping track of where their cards are (but without looking at the faces of the cards). Then the person whose turn it is puts their cards back in the deck, announcing where they are putting them back in, but only to the people who have already been.

It’s now the case that the person whose turn it was knows where in the deck their cards are, but for each of the other positions in the deck they don’t know what card is in that position. The same has remained true of each of the people who have already had their turn.

Once we’ve gone through everyone like this, people simply take it in turns to remove their cards from the deck without looking (which they can do since they know where their cards are) and they announce which positions they’re taking from so that everyone else can keep track of their own cards.

That is exactly correct. Well done! You are the first person I have asked to give a correct answer to this puzzle.

That violates part of the problem statement. You’ve required the players to get the cards from a shuffled deck, which necessarily implies that no player has any knowledge of the order of the deck.

For any reasonable meaning of “shuffled”, there’s no way to reconstruct an ordered state (everyone can re-acquire their cards) from a shuffled state. Therefore, if you want the problem to be solvable, you must interpret the phrase “out of a shuffled deck” to mean “the cards in the deck which will not be in anyone’s hand are in a random order.” This makes the problem trivial; shuffle the deck, then put hands back on top in a specified order. Seal the deck away until you resume. Continue play.

All of the cards, including the ones in players hands are shuffled together. Then, the 5 players have to get their hands out of the completely shuffled deck. This is not impossible. The players are allowed to look at the shuffled deck. If you want, you can assume that you start with a sealed deck instead of a shuffled deck.

If players can examine the deck, then they can select a new hand distinct from the old one. Therefore in order to reconstruct the hands correctly, looking at the contents of the deck must be forbidden.

I said in the problem statement that all players are assumed to be honest.

No. I don’t think it is correct.

Suppose it is just you and me. I look at the shuffled deck and my cards are in positions 25-29. I announce that to nobody and hand the deck to you (without moving my cards because why bother).

You tell me you are putting your cards in positions 26, 30, 18, 40 and 41.

The fact that you are able to put a card in position 26 tells me that you have at least one card from the second half of the deck does it not? Therefore you are leaking information to me by your actions.

Nor can you take your cards and tell me what positions you took from (because I know what cards are in what positions).

Anyways its now on reddit http://www.reddit.com/r/math/comments/1xkkj2/logic_puzzle_poker_interrupted/

I agree that this solution is not clear as written. However, it is clear to me that he understood the correct solution.

How about this?

If there are N players, get N identical decks of cards. Tape together all of the cards of each type (all the fives of hearts are taped together for example). Then shuffle this pile of taped-together card packets.

Then write on each card from each taped-together packet, in erasable invisible ink, an index from one to 52, the same for each card in a packet. All the fives of hearts might have the number 9, but nobody knows this because they’re all looking only at the backs of the cards.

Then sort the cards back into decks. Distribute one deck to each player. Ask the players to pick out their cards, then erase the invisible ink from the cards chosen by players.

Flip all the remaining cards again, then shuffle them all back together for anonymity. Then sort out the remaining cards into piles by their invisible ink ID. Throw out piles of N-1 cards, and keep one copy of each card for which there are N. Erase all the invisible ink, and you have correct cards left, but nobody can identify which cards they are.

Thanks for you comment Jacob.

That may work, but there is a way to do it with a single deck, and no invisible ink.

As promised, here is my solution:

First, I will take my 5 cards out of the deck.

I will describe an algorithm that gets from the position where n people have taken their hands out of the deck to a position where n+1 people have taken their hands out of the deck:

The remaining deck (not counting the n people’s hands) is shuffled. The n people then one at a time put their hands on the top of their deck. I choose a random permutation, and shuffle the deck with that permutation. The n+1st person, who has not yet found their hand, looks at the permuted deck, and announces which locations his cards are in. I then apply the inverse permutation, putting the deck back in the original order. The n people each take their hands off of the top. I know which 5 positions the n+1st player’s hand is in, so I take those 5 cards out without looking and hand them to him.

Repeating this algorithm 4 times will give everyone back their original hands. There is no extra information, since the only time anyone ever looks at the deck, it is in a random order.

I haven’t looked at the comments. I can think of a rather convoluted way of doing this; I kind of suspect that there’s a more elegant solution that I’m supposed to think of.

Here’s how it works: with the cards in the deck in a fixed order, each player looks through the full deck and memorizes the position of their card. Then the cards are systematically placed in order on a sufficiently large table, and each card is covered with a larger sized card that won’t reveal whether or not it’s covering a card underneath. Then each player pulls out their cards from underneath the positions they memorized while the other players look away. Then the original deck can be carefully recovered without revealing anything by collecting the covering cards together and ensuring that no covered card is accidentally revealed before it gets lost in the deck.

This is just one way of expressing the principle behind this solution, which is that I need some way of storing the cards in their deck order without it being revealed which cards have been removed, and then similarly a way of getting those remaining cards back together without revealing information. The above was sort of the least convoluted way I could think of to accomplish this.