Binary magic

A clas­sical trick on guessing an intended number, made up in the begin­ning of the XIX century, will let your surprise a child, assuming a role of a math­e­mat­ical magi­cian and inspire him to learn a dyadic nota­tion.

• A spec­tator thinks of a natural number from $1$ to $100$.
• A spec­tator indi­cates cards, which contain the intended number (for conve­nience numbers on every card are written in increasing order).
• A magi­cian mentally adds first numbers of indi­cated cards and  triumphantly nomi­nates the intended number.

Having conducted several exper­i­ments, one can prove that the mentioned rule works. What is the secret of cards? Can one manage with a less number of cards to ensure guessing one number of $100$? To answer these ques­tions, let’s remember the base of infor­ma­tion theory and dyadic nota­tion.

According to Claude Shannon, a bit is a quan­tity of infor­ma­tion, which elim­i­nates “igno­rance” exactly two times. A magi­cian receives exactly this quan­tity of infor­ma­tion, when a spec­tator says if the indi­cated number is present on a card or not.

Initially igno­rance of a magi­cian is equal to $100$ — he is to choose one number from a hundred of possi­bil­i­ties. In the most successful case-in case of prop­erly made cards (ques­tions) — igno­rance of a magi­cian will be two times less for one response of a spec­tator. It means that after the first answer igno­rance will be not less than $50$, after the second — $25$, etc. After six answers igno­rance can still be more than $1$ — it means that one can’t choose one variant for sure. Conse­quently six cards are not enough to define numbers from one to $100$. After the seventh response the igno­rance lowers — in case of prop­erly prepared cards there is a unique choice (in fact, there is a unique choice even if one tackles numbers from $1$ to $128$). One needs only to realize this theory on prac­tice.

Responses of a spec­tator “no” and “yes” can be coded by numbers $0$ and $1$. Let’s agree to show cards in the same order in all exper­i­ments (for instance, from the first to the seventh). In this case a full answer of a spec­tator is an ordered length sequence, made of zeros and ones. To make it more illus­tra­tive, let’s suggest $0110011$. To realize a trick, one has to learn compare natural numbers to different sequences like that. Though why should one invent some­thing, when there is a dyadic nota­tion!

The mentioned sequence, tackled like a binary record, corre­sponds to a number

$0\cdot 2^6\ +$ $1\cdot 2^5\ +$ $1\cdot 2^4\ +$ $0\cdot 2^3\ +$ $0\cdot 2^2\ +$ $1\cdot 2^1\ +$ $1\cdot 2^0 =$ $32 + 16 + 2 + 1 = 99.$

Now it is easy to guess, how the cards are made: a card with a number contains all numbers, which have $1$ in a binary record in n digit (let’s consider the lowest order digit the first and the highest order digit the seventh). As it was intended, every response of a spec­tator reduces a set of numbers, which contains the intended number, exactly by half, — as there are only two numbers in a dyadic nota­tion: in every digit there is $0$ or $1$. In case of showing cards one by one all responses are inde­pen­dent: every time there is a ques­tion about the next digit, and any two responses of spec­ta­tors will give different infor­ma­tion.

Writing numbers on every card in the order of increasing is conve­nient for a spec­tator, as well as gives a magi­cian an effi­cient way of processing the received infor­ma­tion. The number from the example is a sum of “basic”: $0110011 =\$$0100000\ +$ $0010000\ +$ $0000010\ +$ $0000001$. Namely, these numbers are the first on the cards, which receive a posi­tive answer of a spec­tator, while being shown.