Description

Given 16 playing cards, in the event that you select one of them, then with 4 inquiries I can reason from your answers of yes/no sort which card you pick. ...

Transcripts

Upgraded December 17, 2008 Playing with cards and caps - a prologue to mistake revising codes Michel Waldschmidt Université P. et M. Curie - Paris VI Center International de Mathématiques Pures et Appliquées - CIMPA http://www.math.jussieu.fr/~miw/

Given 16 playing cards, on the off chance that you choose one of them, then with 4 questions I can find from your answers of yes/no sort which card you pick. With one more question I might recognize on the off chance that one of your answer is not good with the others, but rather I should not have the capacity to right it. The soonest blunder revising code, because of Richard Hamming (1950), demonstrates that 7 questions suffice (and this is ideal). Seven individuals are in a room, each has a cap on his head, the shade of which is dark or white. Cap hues are picked arbitrarily. Everyone sees the shade of the cap on everybody\'s head, except not all alone. Individuals don\'t speak with each other. Everybody gets the opportunity to figure (by composing on a bit of paper) the shade of their cap. They may compose: Black/White/Abstain. The general population in the room win together or lose together. The group wins if no less than one of the three individuals did not go without, and everybody who did not go without speculated the shade of their cap effectively. By what method will this group choose a decent methodology with a high likelihood of winning? Again the answer is given by Hammings code, and the likelihood of winning for the group is 7/8. Before flipping a coin 7 sequential time, you need to make a set number of wagers and make certain that one of them will have at most one wrong reply. What number of wagers are required? Again the answer is given by Hamming and it is 16. After a talk of these three illustrations we should give a brief overview of coding hypothesis, up to the later codes including logarithmic geometry.

The best card trap Michael Kleber, Mathematical Intelligencer 24 ( 2002 )

Rules of the card trap Among 52 cards, select 5 of them, don\'t indicate them to me, however offer them to my collaborator. In the wake of taking a gander at these 5 cards, my partner gives me four of them, each one in turn, and conceals the fifth one which is known not and to my associate. I am ready to let you know which one it is.

Which data do I get? I got 4 cards, each one in turn. With my collaborator we concurred heretofore with a requesting. I get these 4 cards in one of 24 conceivable plans. There are 4 decisions for the main card, once the primary card is chosen there are 3 decisions for the second card, and after that 2 decisions for the third one. Lastly no decision for the last one. 24 = 4 3 2 1

24 conceivable plans for 4 cards I get these 4 cards in one of the 24 taking after courses of action 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321. So the data I get can be changed over into a number somewhere around 1 and 24

But there are 52 cards! I got 4 cards, there are 48 obscure cards. Subsequently this thought is not adequate: with a number somewhere around 1 and 24 , I am just most of the way to a right figure.

There are 4 suits as it were! Spade, Hart, Diamond, Club My right hand got 5 cards.

Pigeonhole Principle If there are a larger number of pigeons than openings, one at any rate of the gaps has no less than two pigeons. On the off chance that there are more gaps than pigeons, one in any event of the gaps is void. Dirichlet\'s container standard ( Schubfachprinzip ) 1834

My right hand got 5 cards, there are 4 suits So one at any rate of the suits happens twice. We concur that the main card I get will let me know the suit of the concealed card.

Information I get from the following 3 cards I have to discover which one it is among the 12 different cards of the same suit. Next, I get 3 cards in one of the 6 conceivable requests. I change over this data into a number from 1 to 6 .

Last stride I get a number from 1 to 6 , there are 12 conceivable cards, so again we are most of the way (yet we gained ground by lessening the aggregate number of potential outcomes by a coefficient 4, to be specific from 48 to 12 ). My right hand had the decision between two cards for the principal I got.

Count from 1 to 6

The Hat Problem

The Hat Problem Three individuals are in a room, each has a cap on his head, the shade of which is dark or white. Cap hues are picked arbitrarily. Everyone sees the shade of the cap on everybody\'s head, except not all alone. Individuals don\'t speak with each other. Everybody tries to figure (by composing on a bit of paper) the shade of their cap. They may compose: Black/White/Abstention.

Rules of the diversion The general population in the room win together or lose together as a group. The group wins if no less than one of the three persons don\'t decline, and everybody who did not go without speculated the shade of their cap accurately. What could be the methodology of the group to get the most noteworthy likelihood of winning?

Strategy A frail system: anybody surmises haphazardly. Likelihood of winning: 1/2 3 =1/8 . Somewhat better procedure: they concur that two of them go without and alternate estimates haphazardly. Likelihood of winning: 1/2 . Is it conceivable to improve?

Information is the key Hint: Improve the chances by utilizing the accessible data : everyone sees the shade of the cap on everybody\'s head with the exception of all alone head.

Solution of the Hat Problem Better system : if a part sees two diverse hues, he avoids. On the off chance that he sees the same shading twice, he surmises that his cap has the other shading.

The two individuals with white caps see one white cap and one dark cap, so they go without. The one with a dark cap sees two white caps, so he composes dark. The group wins!

The two individuals with dark caps see one white cap and one dark cap, so they decline. The one with a white cap sees two dark caps, so he composes white . The group wins!

Everybody sees two white caps, and consequently composes dark on the paper. The group looses!

Everybody sees two dark caps, and along these lines composes white on the paper. The group looses!

Winning group: two whites or two blacks

Loosing group: three whites or three blacks Probability of winning: 3/4.

Playing cards: simple diversion

I know which card you chose Among a gathering of playing cards, you select one without letting me know which one it is. I pose a few inquiries and you answer yes or no . At that point I am ready to let you know which card you chose.

2 cards You select one of these two cards I make one inquiry and you answer yes or no . I am ready to let you know which card you chose.

2 cards: one inquiry suffices Question: is it this one?

4 cards

First question: is it one of these two?

Second question: is it one of these two ?

4 cards: 2 questions suffice Y N Y N

8 Cards

First question: is it one of these?

Second question: is it one of these?

Third question: is it one of these?

8 Cards: 3 questions YYY YYN YNY YNN NYY NYN NNY NNN

Yes/No 0/1 Yin —/Yang - True/False White/Black +/ - Heads/Tails ( hurling or flipping a coin)

8 Cards: 3 questions YYY YYN YNY YNN NYY NYN NNY NNN Replace Y by 0 and N by 1

0 1 0 1 0 2 0 1 3 1 0 4 1 0 1 5 1 0 6 1 7 3 questions, 8 arrangements

8 = 2 2 2 = 2 3 One could likewise show the eight cards on the sides of a 3D shape instead of in two lines of four passages.

Exponential law n questions for 2 n cards Add one inquiry = duplicate the quantity of cards by 2 Economy : Growth rate of 4% for a long time = increase by 2.7

Complexity A number somewhere around 0 and 2 n - 1 is given by its paired extension including n digits. Paired documentation m=a n-1 a n-2 … a 1 a 0 implies m=2 n-1 a n-1 + 2 n-2 a n-2 + … + 2a 1 + a 0 . The many-sided quality of m is its number of digits : n = 1+ [log 2 m ] if a n-1 ≠ 0 .

16 Cards 4 questions

12 0 4 8 13 1 5 9 10 14 6 2 11 15 7 3 Label the 16 cards

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Binary representation:

Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Y N Ask the inquiries so that the answers are:

First question:

Second question:

Third question:

Fourth question:

The same works with 32 , 64 , 128 ,… cards

More troublesome: One answer might not be right!

One answer might not be right Consider the same issue, however you are permitted to give (at most) one wrong reply. What number of inquiries are required with the goal that I am ready to know whether your answers would all say all are correct or not? Furthermore, in the event that they would all say all are right, to know the card you chose?

Detecting one slip-up If I make more inquiry , I will have the capacity to identify in the event that one of your answers which is not good with alternate answers. Furthermore, on the off chance that you committed no error, I will let you know which is the card you chose.

Detecting one oversight with 2 cards With two cards I simply rehash double the same inquiry. On the off chance that both your answers are the same, you didn\'t lie and I know which card you chose If your answers are not the same, I realize that one answe