persons A, B, and C in separate rooms with point-to-point communication.
- person C describes to person A how they intend to shuffle cards, e.g., 3 riffle shuffles.
- person A defines two decks, specifying the order of cards in each deck, and tells the information to person B.
- person B secretly randomly chooses one of person A's card orderings, constructs a deck with the chosen ordering, then gives the deck to person C. we go through this person B intermediary so that person A cannot secretly mark decks to tell them apart afterward.
- person C shuffles the received deck as declared in step 1, and gives the shuffled deck to person A.
- person A tries to determine which of the two decks person B gave to person C.
I strongly suspect there are ways that person A can construct decks so that it is very difficult to shuffle them enough destroy the one bit of information that is encoded in them. you will need the full 7 riffle shuffles as proved by Diaconis. (practically perhaps more, if your riffle shuffles are not very good.)
optionally omit step 1 to give person A less of an advantage.
a "shuffling" step that person C can do to possibly make things difficult is the following: flip a coin. if and only if tails, reverse the order of the deck. (I am not aware of any way to do this quickly. perhaps cardistry magicians know of a way.) then, do other shuffles.
variation: split the deck into 2. flip a coin. reverse one half or the other corresponding to the coin flip. then riffle shuffle.
also consider person C hand scrambling a speedcube instead of shuffling a deck of cards. person B needs to be able to construct arbitrary (legal) Rubik's cube states given by person A.
No comments :
Post a Comment