аступного: 1 + 2 + 4 + 8 + ... + 2 n - 2 + 2 n - 1=2 - 1 +2 + 4 + 8 + ... + 2 n - 2 + 2 n - 1=4 - 1 + 4 + 8 + ... + 2 n - 2 + 2 n - 1=8 - 1 + 8 + 16 + ... + 2 n - 2 + 2 n- 1=...=2 n - 2 - 1 + 2 n - 2 + 2 n - 1=2 n - 1 - 1 + 2 n - 1=2 n - 1.
. А тепер, використовуючи даний трюк, обчислимо твір (2 + 1) * (22 + 1) * ... * (22 n + 1).
Доведемо тепер існування і єдиність представлення числа N у вигляді суми менших ступенів двійки. Доказ будемо проводити індукцією по N.
Для N=1 твердження очевидне.
Нехай воно вірно для всіх N? N0. Нехай 2n - максимальна ступінь двійки, що не перевершує N, тобто 2n? N0 lt; 2n + 1. Тоді за припущенням індукції число представимо у вигляді суми ступенів двійки, менших N0 - 2n? 2n. Отже, число N0 теж представимо у вигляді суми менших ступенів двійки (досить до подання числа N0 - 2n додати 2n). Крім того, так як 1 + 2 + ... + 2 n - 1=2n - 1 lt; 2n, то чи не існують уявлення числа N0, що не використовує 2n. Таким чином, доведена єдиність такого подання.
Зауважимо, що для швидкого застосування цього алгоритму зручно заздалегідь обчислити всі ступеня двійки, не перевищують даного числа.
Зауважимо ще, що на відміну від першого варіанта рішення, повна сума у ??всіх конвертах менш ніж у два рази перевершує верхню межу підлягає виплаті суми.
Для короткої записи результату роботи алгоритму над даним числом а можна замість розкладання, яке і записати щось у загальному вигляді без використання триповерхових позначень скрутно, використовувати послідовність показників ступенів (n1, ..., nk), або, що ще зручніше (але не завжди коротше), написати послідовність (am, ..., a1) чисел 0 і 1, в якій ai=1, якщо число 2i - 1 входить в вказане вище розкладання, і ai=0 в іншому випадку. Тоді це розкладання можна буде переписати у вигляді: a=a1 + 2a2 + 4a3 + ... + 2m - 1 am.
Ясно, що наведений вище алгоритм дозволяє будувати таке подання, причому воно визначається однозначно, якщо припускати, що старший його розряд am ненульовий. Це уявлення і називається двійковій записом числа а.
Побачите, що поняття двійковій запису дуже схоже на поняття десяткового запису і в якомусь сенсі навіть простіше.
Залишилося питання про мінімальності знайденої системі конвертів. У загальному вигляді зазначений вище прийом пропонує для сплати будь-якої суми від 1 до n використовувати m конвертів з сумами 1, 2, 4, 8, ..., 2m - 1, де 2m - 1? n lt; 2m. Меншої кількості конвертів може не вистачити, тому що за допомогою k lt; m конвертів можна сплатити не більше ніж 2k - 1 lt; 2m - 1? N різних сум, тому що кожна сума однозначно визначається ненульовим набором (a1, ... .., ak), в якому кожне число ai дорівнює 1, якщо i-й конверт входить в цю суму, і дорівнює 0 в іншому випадку , а всього наборів довжини k з нулів і одиниць можна скласти рівно 2k.
2.2 Застосування систем числення
.2.1 «Книга змін»
Двійкова система, принаймні, у своїй комбінаторної іпостасі, по суті була відома в Древньому Китаї. У класичній книзі «І цзин» («Книга змін») наведені так звані «гексаграми Фу-сі», перша з яких має вигляд, а остання (64-я) - вид, причому вони розташовані по колу і занумерованів точній відповідності з двійковій системою (нулями і одиницями відповідають суцільні і переривчасті лінії). Китайці не полінувалися придумати для цих діаграм спеціальні ієрогліфи і назви (наприклад, перша з них називалася «кунь», а остання - «цянь», суцільної лінії зіставляється чоловіче начало янь, а переривчастої лінії - жіноче начало інь).
Кожна гексаграмма складається з двох триграм (верхній і нижній), їм теж відповідають певні ієрогліфи і назви. Наприклад, триграм з трьох суцільних ліній зіставлений образ-атрибут «небо, творчість», а триграм з трьох переривчастих ліній зіставлений образ-атрибут «земля, податливість, сприйнятливість». Їх також прийнято розташовувати циклічно, але цей цикл не є кодом Грея.
«Книга змін» дуже давня, можливо, одна з найдавніших у світі, і хто її написав - невідомо. Вона використовувалася раніше, і використовується в даний час, в тому числі і на Заході, для ворожіння. У Європі з аналогічною метою використовуються карти Таро. У чомусь обидві ці системи схожі, але Таро ніяк не пов'язані з двійковій системою, тому про них ми говорити не будемо.
Спосіб ворожіння по «Книзі змін» в короткому викладі такий. Впадає шість разів монета (або краще гудзик, гроші у ворожінні застосовувати не рекомендується), і за отриманими результатами (орел чи решка) розшукується підходяща гексаграмма (для цього треба заздалегідь зіставити орлу і решці янь або інь). За гексаграмме розшукуєте відповідний розділ «Книги змін» і читаєте, що там написано.
2.2.2 Азбука Морзе
Семюель Морзе відомий, однак, не тільки вин...
