A classical trick on guessing an intended number, made up in the beginning of the XIX century, will let your surprise a child, assuming a role of a mathematical magician and inspire him to learn a dyadic notation.
- A spectator thinks of a natural number from $1$ to $100$.
- A spectator indicates cards, which contain the intended number (for convenience numbers on every card are written in increasing order).
- A magician mentally adds first numbers of indicated cards and triumphantly nominates the intended number.
Having conducted several experiments, 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 questions, let’s remember the base of information theory and dyadic notation.
According to Claude Shannon, a bit is a quantity of information, which eliminates “ignorance” exactly two times. A magician receives exactly this quantity of information, when a spectator says if the indicated number is present on a card or not.
Initially ignorance of a magician is equal to $100$ — he is to choose one number from a hundred of possibilities. In the most successful case-in case of properly made cards (questions) — ignorance of a magician will be two times less for one response of a spectator. It means that after the first answer ignorance will be not less than $50$, after the second — $25$, etc. After six answers ignorance can still be more than $1$ — it means that one can’t choose one variant for sure. Consequently six cards are not enough to define numbers from one to $100$. After the seventh response the ignorance lowers — in case of properly 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 practice.
Responses of a spectator “no” and “yes” can be coded by numbers $0$ and $1$. Let’s agree to show cards in the same order in all experiments (for instance, from the first to the seventh). In this case a full answer of a spectator is an ordered length sequence, made of zeros and ones. To make it more illustrative, 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 something, when there is a dyadic notation!
The mentioned sequence, tackled like a binary record, corresponds 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 spectator reduces a set of numbers, which contains the intended number, exactly by half, — as there are only two numbers in a dyadic notation: in every digit there is $0$ or $1$. In case of showing cards one by one all responses are independent: every time there is a question about the next digit, and any two responses of spectators will give different information.
Writing numbers on every card in the order of increasing is convenient for a spectator, as well as gives a magician an efficient way of processing the received information. 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 positive answer of a spectator, while being shown.
