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.
- Each person can uniformly choose a number from a finite set of numbers
- All players trust each other. That is, if they agreed on a particular procedure on dividing cards, they will actually follow the procedure.
- 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.
- 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.