Журнал удивительных идей


Совместный проект учителей и учеников 192 школы




Великая теорема

Знакома ли вам великая теорема:

m(a2+b2)=mc2

Пифагора-Энштейна?

 

Скромность

Расказывают, что знаменитый французкий математик Жан Даламбер каждый раз, когда излагал студентам собственную теорему, неизменно говорил: "А сейчас, господа, мы переходим к теореме, имя которой я имею честь носить!"

Битовые фокусы

И все-таки двоичная система нужна не только для того, чтобы сдать ЕГЭ по информатике. Иногда она помогает решать задачи самым неожиданным способом.

Начнем с задачи из прошлого номера:

Имеется 1000 бочек с вином и 10 мышей. Известно, что одна из этих бочек отравлена ядом. Яд начинает действовать через час, и мышь умирает.
Как за час определить какая бочка отравлена?

Найти решение за 10 часов, видимо, смогут все. Действительно, напоим первую мышь из первых пятисот бочек. Если она умрет через час – яд в первых пятистах. Если нет во вторых пятистах бочках. То есть через час откидываем пятьсот. Далее вторую мышь поим из 250 бочек, и тд… Но как это сделать за час?

Занумеруем бочки по порядку и каждый номер запишем в двоичной системе счисления. Коды будут не длиннее 10 знаков. Дополним все коды нулями слева до десяти знаков.

Например, шестая бочка получит код 0000000110. Теперь напоим первую мышь из всех бочек, у которых в первом разряде стоит единица, то есть из бочек с номерами от 512 (код 1000000000) до 1000. Вторую с единицей во втором разряде. Третью – с единицей в третьем. Десятую – в десятом. То есть, из всех нечетных бочек. Через час какие-то мыши умирают. По их номерам можно восстановить номер бочки. Например, умерли третья, шестая и десятая мыши. По двоичному коду 0010010001 восстанавливаем номер: 128+16+1=145 бочка отравлена.

Совершенно удивительным является решение задачи про стратегию в игре Ним. Напомним правила этой игры. Играют двое. Есть несколько кучек, в каждой несколько камней. За один ход можно взять произвольное количество камней, но только из одной кучки. Кто выиграет при правильной игре обоих игроков, и какова стратегия победителя?

Для двух кучек все ясно.  Если в них одинаковое количество количество камней – выигрывает второй. Для выигрыша ему достаточно повторять ходы первого, но на другой кучке. Действительно. В этом случае после хода второго в кучках остается равное, но все меньшее и меньшее количество камней. Таким образом мы обязательно дойдем до ситуации, когда первый возьмет из какой-нибудь кучки последний камень. На следующем ходу второй заберет все камни из второй кучки. Если же в кучках изначально неравное количество камней, то выиграет первый. Первым ходом он сравняет количество камней в кучках и ситуация станет точно такой, как мы только что разобрали.
А что делать, если кучек хотя бы три?

Я не предлагаю вам остановиться и попробовать придумать решение самостоятельно. Потому что я уверен, что гении читают журналы посерьезней.

Запишем числа камней в кучках в… ну конечно, в двоичной системе.
Например, у нас три кучки. В первой 21, во второй 13, в третьей 24 камня:

10101
01101
11000

Мы видим, что в каждом столбце четное количество единичек. Так как по правилам можно брать камни только из первой кучки, то своим ходом первый игрок нарушит четность хотя бы в одном из столбцов.
Второй игрок сможет четность восстановить.
Например, первый берет из второй кучки все камни:

10101
00000
11000

Второму нужно из третьей кучки взять 3 камня:

10101
00000
10101

И так можно сделать всегда. Действительно, найдем первый столбец слева, в котором нарушена четность, и выбираем строку (кучку) в которой в этом столбце единица. Уменьшив количество камней, мы можем поменять эту единицу на ноль. При этом мы можем «выставить» в столбцах правее любой набор нулей и единиц так, чтобы восстановить четность во всех столбцах.

То есть, при начальной позиции 21, 13, 24 первый игрок проиграет при безошибочной игре обоих партнеров.

Снова двоичная система помогла решить задачу, которая на первый взгляд не имеет к системам счисления никакого отношения!

Еще более удивительным кажется применение двоичной системы для решение головоломки «Ханойские башни».

Наверное, всем известен рекурсивный алгоритм решения, но он плохо применим для сборки «вручную». Известно, что количество перемещений для решения башни из N колец равно 2N-1. Запишем  номера ходов  и на каждом шаге будем перекладывать кольцо с номером разряда самой правой единицы в строке.
Например, если колец три:

001 – 1
010 – 2
011 – 1
100 – 3
101 – 1
110 – 2
111 – 1

Получаем последовательность перекладываемых колец: 1, 2, 1, 3, 1, 2, 1. Для всех колец, кроме самого маленького, направление определяется однозначно. Маленькое кольцо следует перекладывать так: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->... (где f – стартовый стержень, t – финальный стержень, r – оставшийся стержень), а если N чётно, то f->r->t->f->r->t->...

Примеры можно приводить и дальше. Системы счисления действительно иногда помогают решать задачи, не связанные со способом представления чисел в компьютере!
О других задачах можно прочитать, например,  в  книге С.Б. Гашкова "Системы счисления и их применение".

Ильин В.В.

М
а
т
е
м
а
т
и
к
а
Ф
и
з
и
к
а
Х
и
м
и
я
Б
и
о
л
о
г
и
я
И
н
ф
о
р
м
а
т
и
к
а