Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The idea came up from a discussion I had with my friends.

Suppose we want to play a game using a deck of cards, and we can't use any physical materials. If we are intelligent enough, we can remember the types of cards each one has. The problem is that it is even hard to divide the cards uniformly by using only our brains.

To divide them properly, each one should not know the types of cards others have. By introducing a 'dealer', it becomes easy. We can ask the dealer to tell each person what cards they will have. But the dealer then can't participate in the game. The question is that how can players divide the deck uniformly by themselves.

I think it is important to specify the exact condition for the problem. This is what I have in mind.

  1. Each person can uniformly choose a number from a finite set of numbers
  2. All players trust each other. That is, if they agreed on a particular procedure on dividing cards, they will actually follow the procedure.
  3. The procedure would consist of a sequence of data transfer from one person to other. The receiver will remember the data exactly, and it is impossible to forget it.
  4. By the end of the procedure, the conditional probability distribution of cards given all the information each person knows should be uniform.

This is far from clear mathematical formulation. So the first question is:

How can we formulate this problem exactly into mathematical language? For example, how can we define the concept of data transfer?

The question is easy when there are only two people and two cards. One can just simply grab one and pass the other. But the question seems much harder for even three people and three cards.

How can three individuals divide three cards uniformly? Or if it is impossible, are there any proof?

I think this can be a more fundamental question.

Can two people having their own number from 1, 2 or 3, interact with each other to conclude that whether they have same or different numbers, but gain no more information about their opponent's number?

Any suggestions for clarification are welcomed. Fixing grammar mistakes and awkward expressions are much welcomed too.

share|improve this question
1  
what you need is a Zero-knowledge proof en.wikipedia.org/wiki/Zero-knowledge_proof not sure if it is possible, doubt it very much. –  Willemien Dec 28 '13 at 20:20
    
cool question. i am not sure i even understand the 2 player case completely. would you mind posting that solution in more detail? –  hunter Dec 28 '13 at 22:11
    
@hunter Let the two players be A and B and two cards be 1 and 2. A simply choose her card uniformly from 1 and 2, and pass the other to B. Now the cards are distributed uniformly, and since each individual knows his card, knowing the opponent's card does not add to that information. –  Jineon Baek Dec 29 '13 at 3:35
1  
Related: en.wikipedia.org/wiki/Mental_poker –  leonbloy Dec 29 '13 at 20:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.