Playing with cards and caps - a prologue to mistake revising codes.


56 views
Uploaded on:
Category: People / Lifestyle
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
Slide 1

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/

Slide 2

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.

Slide 3

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

Slide 4

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.

Slide 5

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

Slide 6

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

Slide 7

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.

Slide 8

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

Slide 9

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

Slide 10

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.

Slide 11

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 .

Slide 12

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.

Slide 13

Count from 1 to 6

Slide 14

The Hat Problem

Slide 15

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.

Slide 16

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?

Slide 17

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?

Slide 18

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.

Slide 19

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.

Slide 20

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!

Slide 21

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!

Slide 22

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

Slide 23

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

Slide 24

Winning group: two whites or two blacks

Slide 25

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

Slide 26

Playing cards: simple diversion

Slide 27

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.

Slide 28

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.

Slide 29

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

Slide 30

4 cards

Slide 31

First question: is it one of these two?

Slide 32

Second question: is it one of these two ?

Slide 33

4 cards: 2 questions suffice Y N Y N

Slide 34

8 Cards

Slide 35

First question: is it one of these?

Slide 36

Second question: is it one of these?

Slide 37

Third question: is it one of these?

Slide 38

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

Slide 39

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

Slide 40

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

Slide 41

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

Slide 42

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.

Slide 43

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

Slide 44

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 .

Slide 45

16 Cards 4 questions

Slide 46

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

Slide 47

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:

Slide 48

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:

Slide 49

First question:

Slide 50

Second question:

Slide 51

Third question:

Slide 52

Fourth question:

Slide 53

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

Slide 54

More troublesome: One answer might not be right!

Slide 55

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?

Slide 56

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.

Slide 57

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

Recommended
View more...