четверг, 3 ноября 2016 г.

Алгоритмические аспекты школьной геометрии



Алгоритмические аспекты школьной геометрии
(тезисы доклада в Кирове на конференции по математическому образованию одаренных школьников, 03.10.2016)

Практически во всех учебных планах по геометрии значительное количество часов отводится на решение задач. При этом остается «за кадром», какие именно задачи должны решаться. С одной стороны, это оставляет свободу выбора не только авторам учебников и задачников, но и разумным учителям. С другой — каждая свобода предполагает и определённую ответственность. Я бы хотел обратить ваше внимание на актуальность и важность алгоритмического подхода при решении абсолютно всех геометрических задач, но в особенности — при решении задач на построение.

Начну с классики.

Задача 1. Дана прямая и точка на ней. Провести через эту точку перпендикуляр к прямой.

Эта задача встречается еще у Евклида («Начала», Книга 1, Предложение 11). И, начиная с Евклида, мы учим школьников, что решать ее надо примерно так:


Сначала отметить на прямой точки B и C на равных расстояниях от данной точки A, затем построить третью вершину D правильного треугольника BCD. Прямая AD – искомый перпендикуляр. Евклид доказывает это с помощью признака равенства треугольников ABD и ACD, и все учебники геометрии вслед за ним повторяют и это построение, и это доказательство.

Безусловно, в этом нет ничего плохого, и я не предлагаю ничего менять в этом месте. Однако потом, после изучения темы «окружность», имело бы смысл снова вернуться к этой задаче и предложить ученикам найти альтернативное построение, требующее меньшего количества шагов. Под шагами я здесь и далее буду понимать проведенные линии. Такое построение существует и является в чем-то даже более красивым, чем решение Евклида. Вот оно:

Удивителен здесь самый первый шаг — проведение окружности с центром в произвольной точке B вне данной прямой. А доказательство правильности построения — после изучения свойств вписанных углов — ничуть не сложнее евклидового.

Стоит отметить, что если такое «экономичное» решение задачи 1 не является новым, то неоптимальность решения следующей задачи, по-видимому, осталась незамеченной всеми авторами учебников, методистами и пр.

Задача 2. Дана окружность и точка на ней. Провести через эту точку касательную к окружности.

Классический способ решения — сначала провести диаметр, а потом перпендикуляр к нему. Даже если воспользоваться «экономным» алгоритмом проведения перпендикуляра, это потребует 1+3=4 операции. Однако задача решается за 3 операции, то есть не требует проведения диаметра. Более того, она вообще обходится без использования центра окружности. На нашем рисунке его вовсе нет.

Как и в задаче о перпендикуляре, здесь неожиданен уже первый шаг — проведение через А второй окружности с центром в произвольной точке C  данной окружности. Кстати, как доказать, что прямая AG – действительно касательная? Для этого достаточно знать теорему про угол между касательной и хордой (AC).

В чем преимущество «экономных» построений перед стандартными? Разве так уж важно, решена ли задача за четыре шага или за три? Для конкретной задачи — безусловно, не важно, потому что в геометрии не бывает «хороших» и «плохих» решений, а бывают только правильные и неправильные. Но вот в окружающем мире, в том числе и в школе, детям очень часто приходится решать задачи именно с ограниченными ресурсами — пробежать стометровку, уложившись в норматив, или успеть решить контрольную работу до того, как прозвенит звонок. Почему мы в геометрии игнорируем возможность ставить задачи с явным ограничением ресурсов?

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

Закончу небольшим историческим экскурсом и сводкой задач.

Идея геометрографии - подсчета числа шагов в построениях, - безусловно, не нова. Одним из первых ее выдвигал французский геометр Эмиль Лемуан еще в самом начале XX века. Однако тогда эта идея явно опередила своё время.

Задачи.
1.     Дан луч с началом в точке A, на котором отмечены точки B и C. Построить на луче точку D такую, для которой AD = AB2 /AC (3 шага)
2.     Дана окружность и точка A вне неё. Провести касательную. (5 шагов)
3.     Дан треугольник, построить вписанную в него окружность (8 шагов)
4.     Разделить данный отрезок на три равных части (6 шагов)
5.     Решить предыдущую задачу одной линейкой (8 шагов)
6.     Дана окружность с неизвестным центром. Построить его одним циркулем (6 шагов)

Литература
1.     Emile Lemoine. Géométrographie ou Art des constructions géométriques - 1902.
2.     К.А.Кноп. Одной линейкой - http://elementy.ru/problems/1243
3.     Коллекция интерактивных задач по геометрии — www.euclidea.xyz


четверг, 19 мая 2016 г.

Unicode, Word и диакритические знаки

Просто оставлю здесь замечательный рецепт от Алексея П.

Поле́зный сове́т. Что́бы в Word бы́стро поста́вить знак ударе́ния или умля̈ут, следует воспо́льзоваться объединёнными диакрити́ческими зна́ками и альтернати́вным спо́собом вво́да юнико́дных си́мволов. Юнико́дный код ударе́ния 0301; код умля̈ута — 0308. Вво́дятся они так: сра́зу же по́сле бу́квы, кото́рая должна́ быть уда́рной, набира́ется пря́мо в те́ксте 0301 и нажима́ется комбина́ция кла́виш Alt+x. Для вво́да умля̈ута сра́зу за ну́жной бу́квой набира́ется 0308 и нажима́ется Alt+x.

пятница, 25 марта 2016 г.

"Пиратская" статья в "Кванте"

В первом номере "Кванта" за 2016 год выйдет наша с Сергеем Грибком совместная статья с задачами об оптимальном принятии решений в антагонистических играх с полной информацией для многих игроков. Называется она "Пятнадцать человек на сундук мертвеца". Попросту говоря - это задачи о дележе клада командой пиратов.

С разрешения редакции публикую здесь собственно задачи и упражнения из статьи, без решений.

Пятнадцать человек на сундук мертвеца

Сергей Грибок, Константин Кноп


Все задачи, о которых мы собираемся вам рассказать, связаны общим сюжетом: команда пиратов хочет поделить золотые монеты. Но прежде чем приступить к рассказу, мы должны поближе познакомиться с пиратской логикой и ее законами.
       Ни при каких обстоятельствах ни один из пиратов не желает очутиться за бортом корабля.
       Пираты очень любят золото. Каждый из них хочет получить как можно больше монет в результате дележа.
       Ни один из пиратов никогда не вступит в сговор с другим пиратом, чтобы сообща обыграть остальных. «Каждый сам за себя» – правило, которому следует каждый пират.
       Каждый пират в совершенстве владеет логикой, и все его действия логически обоснованы.
       Все предпочтения, законы и правила пиратов (включая и это правило) известны и самим пиратам.

Итак…

Задача 1

Пятнадцать пиратов с брига «Арабелла» – капитан, 13 матросов и юнга – нашли клад, – сундук, в котором лежало 100 одинаковых золотых монет. Чтобы поделить деньги, пираты использовали такую процедуру:
1.      Капитан как самый старший предлагает свой план дележа клада.
2.      Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».
3.      Если все пираты проголосовали «за», то план принимается и деньги делятся по плану. Если же хотя бы один из пиратов проголосовал против, то старшего пирата бросают за борт. После этого следующий по старшинству пират вносит свой план, пираты снова голосуют и так далее, пока наконец план одного из пиратов не будет принят.

Еще одна особенность пиратов «Арабеллы» – их природная доброта. Если решение пирата голосовать «за» или «против» никак не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то каждый пират по доброте душевной всегда проголосует «за».

Как будут поделены деньги, если пираты будут использовать данный метод дележа? Чей план будет принят?

Упражнение 1.

Капитан делил добычу между пиратами. Сначала он взял себе 1/16 всех монет и еще одну монету. Второму пирату он дал 1/16 оставшихся монет и еще две и т.д. Пятнадцатому (юнге) он дал 1/16 оставшихся монет и еще 15 монет. Оказалось, что все получили поровну и все монеты розданы. Сколько всего было монет?

Упражнение 2.

За столом сидят три пирата, перед каждым – кружка, в некоторые налит ром (возможно, не поровну). Первый разлил весь свой ром поровну в кружки остальным. Затем второй разлил свой ром поровну остальным двоим (включая первого), а потом и третий сделал то же самое. В итоге в каждой кружке оказалось столько же рома, сколько было вначале. Сколько рома в каждой кружке, если всего его две пинты?

Теперь расскажем о том, как делила клад другая команда пиратов со шлюпа «Бестия».

Задача 2

Пираты на «Бестии» использовали другой метод дележа:
1.      Самый старший пират рассказывает план остальным.
2.      Все пираты голосуют, следует ли принять план старшего. Каждый из пиратов голосует либо «за», либо «против».
3.      Если не менее половины пиратов проголосовали «за», то план принимается, и деньги делятся по плану. Если же большинство пиратов проголосовало против, то старшего пирата бросают за борт. После этого следующий по старшинству пират излагает свой план, пираты снова голосуют и так далее, пока наконец план одного из пиратов не будет принят.

Пираты «Бестии» – такие же добродушные ребята, как и их коллеги с «Арабеллы». Если решение пирата голосовать «за» или «против» не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то каждый пират всегда голосует «за». Как 15 пиратов со шлюпа «Бестия» поделят 100 монет?

Упражнение 3.


Задача 3.

Пираты с фрегата «Валькирия» отличаются от пиратов «Бестии» отсутствием доброты: если решение пирата голосовать «за» или «против» никак не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то в пирате просыпается его жестокая бабушка с отцовской стороны, и он голосует «против».
А в качестве алгоритма дележа на  «Валькирии» используются правила, описанные в упражнении 3.

1.      Самый старший пират рассказывает остальным свой план.
2.      Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».
3.      Если все пираты, кроме, быть может, одного, проголосовали «за», то план принимается, и деньги делятся по плану. Если же хотя бы двое из пиратов проголосовали против, то старшего пирата бросают за борт. После этого план предлагает следующий по старшинству, пираты снова голосуют и так далее, пока план одного из пиратов не будет принят.

Как 15 пиратов с «Валькирии» поделят 100 монет?

Упражнение 4.

б) Как N пиратов с «Валькирии» разделят K монет?

Примечательно, что лишь незначительное различие в характере пиратов (добродушные  пираты «Бестии» в нейтральной ситуации голосуют «за», а упрямые пираты «Валькирии» – против), приводит к кардинально отличающимся результатам дележа. Способность команды “Валькирии” обеспечить себе существенно более выгодные условия дележа иллюстрирует важный общий принцип, доказательство которого выходит далеко за рамки данной работы: социальная активность ведет к росту благосостояния общества.

Задача 4

Один из пиратов, бывший в те славные времена юнгой на «Валькирии», спустя много лет после описываемых событий хвастался, что сумел забрать себе весь клад.
– Тысяча чертей! Этот скряга капитан предложил мне всего 13 монет. Тут я вижу, что шкипер голосует против, и тоже проголосовал против! И пока все на меня выпучились, шкипер уже успел выкинуть капитана за борт. А после этого, как ни в чем не бывало, шкипер предложил мне всего 12! Ну, я еще раз проголосовал против – и наш бывший шкипер тут же улетел за борт к бывшему капитану. И вот тут до следующего стало что-то доходить... Тысяча чертей! Он раз пять подряд начинал что-то говорить, и каждый раз, не доведя предложение до точки, смотрел на меня и сбивался... В конце концов он предложил отдать всё мне. Мне, безусому юнге! А все остальные пираты, постоянно косясь на меня, проголосовали «за». Конечно, после этого я не мог уже ни минуты находиться на нашем фрегате, поэтому отвязал капитанскую шлюпку, погрузил в нее сундук и немедленно отчалил.

Докажите, что этот рассказ юнги немножко не соответствует истине.


Наша серия пиратских баек была бы неполной, если бы мы не рассказали историю пиратов со шхуны «Горгона».

Задача 5

Все пираты на шхуне «Горгона» такие же жестокие, как и на «Валькирии», а для дележа используют тот же метод, что и команда шлюпа «Бестия»:
1.      Самый старший пират излагает свой план дележа.
2.      Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».
3.      Если не менее половины пиратов проголосовало «за», то план принимается и деньги делятся так, как было предложено. Если же большинство пиратов проголосовало против, то старшего пирата бросают за борт. После этого следующий по старшинству пират вносит новый план, оставшиеся пираты снова голосуют и так далее, пока, наконец план одного из пиратов не будет принят.

а) Как 15 пиратов «Горгоны» поделят 100 монет?
б) Чей план будет принят, если 100 пиратам со шхуны «Горгона» нужно разделить 15 монет?

Методы дележа, которые мы рассмотрели в предыдущих задачах, имеют один существенный недостаток: большинство пиратов может очутиться за бортом, а это плохо сказывается на боеготовности экипажа. К счастью, среди пиратских команд встречаются и менее кровожадные.

Задача 6

Пираты с корвета «Даная» были такими же жестокими, как на «Горгоне» и «Валькирии», но придумали новый способ дележа монет, который позволяет пиратам оставаться на борту и претендовать на часть добычи даже после того, как их план не был принят.

1.      Самый старший пират излагает свой план дележа.
2.      Все пираты голосуют «за» либо «против».
3.      Если все пираты, кроме, быть может, одного, проголосовали «за», то план принимается и деньги делятся так, как было предложено. Если же хотя бы двое из пиратов проголосовали «против», то план не принимается и голосование продолжается. Следующий по старшинству пират предлагает свой план, пираты снова голосуют и так далее, пока план одного из пиратов не будет принят. Если ни один из планов не пройдёт, то все деньги получает юнга.

Как 15 пиратов «Данаи» поделят 100 монет?

Заметим, что доверие пиратов к демократическим механизмам принятия решений тоже не такое абсолютное, как вам могло показаться...

Задача 7

На бригантине «Ехидна» только капитан и шкипер имеют право предлагать планы дележа монет. Все остальные пираты могут лишь голосовать. Таким образом, алгоритм дележа выглядит так:
1.      Шкипер рассказывает всем остальным свой план дележа монет.
2.      Затем капитан рассказывает всем свой план дележа монет.
3.      Все пираты (включая капитана и шкипера) голосуют либо за первый, либо за второй план.
4.      Монеты делятся в соответствии с планом, набравшим больше голосов.

Известно, что если оба плана сулят пирату равное число монет, он проголосует за первый план.

Как 15 пиратов (капитан, шкипер и 13 матросов) с «Ехидны» поделят 63 монеты?

Задача 8

На барке «Жанетта», как и на «Ехидне», матросы не имеют права выдвигать планы. Это могут делать лишь старшие пираты. Алгоритм дележа такой:

1.      Первый пират рассказывает свой план дележа.
2.      Второй пират рассказывает свой план – «альтернативу».
3.      План и альтернатива сравниваются. Если план даёт хотя бы двум пиратам не меньше монет, чем альтернатива, то альтернатива отвергается. Если же альтернатива даёт больше денег всем пиратам, кроме быть может одного, то план отвергается, а альтернатива становится планом. Затем следующий пират озвучивает новую альтернативу, и так далее.
4.      После того как все старшие пираты высказались, монеты делятся по плану.

5 старших пиратов и 10 матросов с «Жанетты» делят 105 монет. Как первый пират сможет получить 14 монет?

Задачи для самостоятельного решения

В среднем эти задачи более сложны, чем разобранные выше.

С1.
Как изменится дележ на «Данае», если пираты поменяют правило 3): план будет считаться принятым, если более половины пиратов проголосовали “за”? Для решения задачи требуется уточнить, как пират решает, какой выдвинуть план, если есть несколько разных планов, каждый из которых принесет этому пирату одно и то же число монет. В этом случае будем считать, что выбор плана происходит случайным образом (например, пират бросает монетку, чтобы сделать выбор между двумя равноценными планами).

С2.
Как изменится решение предыдущей задачи, если в случае выбора между равноценными планами пират «Данаи» всегда предпочтет тот план, который оставляет больше монет более старшим пиратам?

С3.
Как именно будут разделены монеты в задаче 5б (“Горгона” с большой командой и малым запасом золота), если выбор между равноценными планами делается так же, как в предыдущей задаче С2?

Как будут разделены на бригантине «Ехидна» K монет между N пиратами?

С5.**
На яхте «Золушка» команда состоит всего из троих – капитана, шкипера и юнги. В найденном ими кладе оказалось всего 15 монет. Поэтому они договорились, что сначала выслушают все три плана, а уже потом будут выбирать.

Итак, все по очереди, начиная с капитана и заканчивая юнгой, предлагают свои варианты дележа. Потом каждый голосует – выбирает тот из планов, в котором ему достается больше монет. Если таких планов несколько, он проголосует за первый из них. План, получивший больше одного голоса, принимается, и клад делится в соответствии с ним. Однако если такого плана не оказалось, то никто ничего не получает (весь клад выбрасывается за борт).

Как окажутся разделены монеты?
  

воскресенье, 1 ноября 2015 г.

Отрицание "Этюда"

В очень далеком 1997 году я опубликовал в «Компьютерре» статью под названием «Этюд о двух отрицаниях, или Точка опоры». Статья была посвящена задаче о реализации логических операторов AND, OR, NOT с ограничением на число используемых NOT. А именно, я считал тогда (и утверждал это в статье), что любое количество входов можно инвертировать («перевернуть») с помощью всего двух элементов NOT, если количество AND и OR не ограничено. А теперь я так не считаю, потому что в той моей статье была допущена (глупая, хотя и очень поучительная) ошибка.


Статья начиналась с конструктивного доказательства следующей «леммы о трех входах»
Значения трех бинарных величин можно заменить на противоположные, использовав только две операции NOT. (При этом разрешается использовать любое число операций AND и OR, а также любое число вспомогательных величин).

А после доказательства леммы был примерно такой вывод.
«А теперь рассмотрим такую процедуру: пользуясь доказанной выше леммой, заменим первые три инвертора на два. Добавим к ним следующий инвертор. Снова воспользуемся леммой и уменьшим число инверторов до двух. Потом возьмем следующий инвертор и т.д. - до тех пор, пока у нас не останется всего два инвертора.»

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

Пусть даны бинарные величины X, Y, Z. Выходные величины будем обозначать буквами X', Y', Z', а вспомогательные - другими буквами. Вместо OR я буду писать «+», а AND буду рассматривать как умножение (собственно, на этом базируется вся булева алгебра). И только NOT я буду писать буквами, чтоб он был заметен.

Алгоритм INVERT3.
1. S1 := X+Y+Z
2. S2 := XY+YZ+ZX
3. S3 := XYZ
4. A := NOT (S2)
5. C := NOT (AS1 + S3)
6. X' := AY + AZ + AC + CYZ
7. Y' := AX + AZ + AC + CXZ
8. Z' := AX + AY + AC + CXY
Докажем, что мы получили именно то, что хотели получить. Первые три действия вычисляли симметрические многочлены от X,Y,Z. Нетрудно убедиться, что их результаты имеют следующий очень простой смысл: Si (i=1,2,3) равно 1 тогда и только тогда, когда [дальше я буду писать в таких случаях iff] не менее чем i входов равны 1. Так как NOT(S2) S1=1 iff  S1=1 и S2=0, то это бывает iff ровно один вход равен 1. Следовательно, AS1+S3=1 iff «один или три входа равны 1», а C=1 iff «0 или 2 входа равны 1».
Операции 6-8 аналогичны друг другу, поэтому достаточно разобраться с первой из них. AY=1 iff Y=1 и «не более одного входа равно 1». То есть когда три входа равны (0,1,0). Аналогично AZ=1 только на наборе (0,0,1). AC=1 iff одновременно A и C равны 1, а это бывает только когда нет входов, равных 1, то есть на наборе (0,0,0). И, наконец СYZ = 1 iff 2 входа равны 1, причем Y=Z=1, то есть только на наборе (0,1,1). Таким образом, сумма четырех выписанных слагаемых принимает значение 1 на наборах (0,0,0), (0,0,1), (0,1,0) и (0,1,1), то есть равна 1 iff   X=0. Иначе говоря, эта сумма равна NOT(X). Аналогично, результаты операций 7 и 8 равны NOT(Y) и NOT(Z) соответственно.
Итак, лемма доказана. В ней ошибок нет. Где же тогда была ошибка?

Если индукционное доказательство приводит к неверному утверждению, а в базе индукции ошибок нет, значит, ошибки есть в индукционном переходе. И действительно, если мы применим базу к первым трем входам, то для инвертирования их нам нужно будет вычислить отрицания от S2 и AS1+S3. Но одно из этих выражений содержит внутри себя уже построенное отрицание другого, так что мы не можем считать их независимыми входами. В частности, мы не можем с самого начала вычислять симметрические выражения от двух этих выражений и третьего входа.

Но, может быть, существует другой алгоритм, в котором два инвертируемых промежуточных выражения будут независимыми? Увы, тоже нет (доказать это не очень трудно, но я знаю только переборное доказательство).
А сколько всего операций NOT потребуется для инвертирования, например, четырех входов? Три штуки. А для инвертирования пяти, шести, семи входов? Тоже три! Точно три? Да, точно.  Следите за руками. Я запишу алгоритм, а справа от номера шага буду в квадратных скобках фиксировать, при каком количестве единиц среди входов вычисляемая величина будет равна 1. Входы я буду обозначать буквами X1, …, X7.

Алгоритм INVERT7.
1. S1 := X1 + … + X7  [1,2,3,4,5,6,7]
2. S2 := X1X2 + … + X6X7  [2,3,4,5,6,7]
3. S3 := X1X2X3 + … + X5X6X7  [3,4,5,6,7]
4. S4 := X1X2X3X4 + … + X4X5X6X7  [4,5,6,7]
5. S5 := X1X2X3X4X5+ … + X3X4X5X6X7  [5,6,7]
6. S6 := X1X2X3X4X5X6 + … + X2X3X4X5X6X7  [6,7]
7. S7 := X1X2X3X4X5X6X7  [7]
8. A1 := S4  [4,5,6,7]
9. B1 := NOT (A1)  [0,1,2,3]
10. A2 := B1S2 + S6  [2,3,6,7]
11. B2 := NOT (A2)  [0,1,4,5]
12. A3 := B1B2S1 + B1S3 + B2S5 + S7  [1,3,5,7]
13. B3 := NOT(A3)  [0,2,4,6]
Кроме того, введем обозначения для симметрических выражений, содержащих все переменные кроме X1, а именно, P0=1, P1 := X2 + … + X7, P2 := X2X3 + … + X6X7, …, P6 := X2X3X4X5X6X7.
Тогда
X1' = B1B2B3P0 + B1B2A3P1 + B1A2B3P2 + B1A2A3P3 + A1B2B3P4 + A1B2A3P5 + A1A2B3P6
В этом выражении множители вида {A,B}1{A,B}2{A,B}3 выделяют строго «своё» количество входов, равных 1 (в соответствии с двоичной записью числа i), а умножение на Pi гарантирует, что среди этих входов не окажется вход X1. [Часть этих выражений можно было бы сократить, например, A1A2 это просто S6, но я не стал этого делать ради единообразия записи слагаемых.]
Выражения для X2', …, X7' строятся аналогично.

Контрольный вопрос: для какого наибольшего количества входов будет достаточно четырех инвертирований?

пятница, 18 сентября 2015 г.

Три коробка спичек

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

У вас есть три коробка по 20 спичек в каждом. Однако известно, что какой-то один из них полностью состоит из хороших спичек, а в двух других половина (10 штук) спичек бракованные и непригодны для использования. Однако на ощупь брак никак не опознается, поэтому различать коробки вы не умеете.
Вы можете попытаться поджечь любую из спичек. С бракованной спичкой, естественно, ничего не случится, а хорошая загорится. Беда в том, что после этого ее уже нельзя будет взять в поход. Такую операцию назовём тестированием спички. Вы можете тестировать столько спичек, сколько захотите. 

1. Какое (в худшем случае) количество хороших спичек вам удастся взять в поход? (Брать в поход бракованные спички ни в коем случае нельзя.)

2. Попробуйте придумать алгоритм, который позволяет отобрать это количество, затратив при этом наименьшее (в среднем) число тестирований. 

четверг, 17 сентября 2015 г.

Про весы-обманщики. История одной задачи

Я люблю рассказывать истории про задачи. Особенно когда задачи того стоят. Один из таких замечательных сюжетов – «весы-обманщики». Задачку на эти весы я придумал очень давно, но как-то всё не представлялось возможности ее пристроить. Однако в прошлом году я решил, наконец, кинуть ее в «Математику в школе». Вот условие, с которым она была опубликована:

5418. Среди 9 монет 8 одинаковых настоящих и одна фальшивая, чуть более лёгкая. Костя хочет определить эту монету с помощью чашечных весов без гирь. Сможет ли он справиться с этим за 4 взвешивания, если в одном из них весы могут «соврать» (то есть результат какого-то одного взвешивания может оказаться неправильным)?

Приводить решение я пока не буду, потому что в журнале указан срок присылки решений до 30-го сентября. Желающие могут порешать. (Хотя, если вы прочитаете всё, что я написал ниже, то решение этой задачки покажется совсем детским) Вместо этого расскажу то, что осталось «за кадром», благо, этого добра тут много.

Во-первых, почему целых 4 взвешивания? Неужели не хватит меньшего количества? Ведь если весы всё показывают правильно, то хватает и двух взвешиваний... Оказывается, здесь всё тютелька в тютельку, - не просто без запаса в одно взвешивание, но и даже без запаса в одну монету! Покажем, что для 10 монет эта задача за 4 взвешивания неразрешима.

Пусть мы думаем, что научились решать задачу для 10 монет, то есть при каждой фальшивой монете и каждом способе вранья весов правильно определим ФМ. Если в каких-то случаях нам удастся это сделать быстрее четырех взвешиваний – ну что ж, прекрасно, значит, оставшиеся взвешивания делаем как угодно и не обращаем внимания на их результаты. 

Представим, что против нас действуют не бездушные весы, а некий соперник, который сознательно выбирает, какая монета будет фальшивой, на каком взвешивании он нас обманет (и будет ли обманывать вообще) и как именно (т.е. какой из двух неверных исходов он нам сообщит). Если мы всё равно умеем найти ФМ, то мы умеем отгадывать и поведение соперника. Но сочетание «выбор ФМ + поведение соперника» даёт ему 10*(1+2*4)=90 вариантов, а 4 взвешивания – это всего 3^4 = 81 вариант. Таким образом, какие-то варианты будут для нас неразличимыми, а это означает, что гарантированно находить ФМ мы не сможем.

Это рассуждение показывает, что число монет не может быть больше, чем 81/(1+2*4), то есть 9.

Ok, а теперь подумаем, как бы обобщить задачку? Прежде всего, в обобщении нужно постараться тоже предложить точный результат, то есть такой, при котором число вариантов за соперника будет в точности равно числу вариантов, обеспечиваемых взвешиваниями. А поскольку для N взвешиваний у соперника (не считая выбора монеты) имеются 1+2N вариантов выбора поведения, значит, это количество должно быть степенью тройки. Следующее такое N равно 13. Иначе говоря, мы хотим разрешить делать 13 взвешиваний. Оценка вариантов говорит нам, что максимально возможное число монет при этом равно 3^13 / (1+2*13) = 3^10.

Найдя это значение, я подумал, что никогда в жизни не рискну выдать в олимпиаду задачу про 13 взвешиваний и 59049 монет! Однако, к счастью, в жизни бывают не только школьные олимпиады. Просматривая недавно свою старую переписку, я наткнулся в ней на задачу от моего знакомого, присланную мне еще в 2006 году:

59049 монет и одно неверное взвешивание
Есть 59049 монет (310). Среди монет имеется одна фальшивая. Известно, что фальшивая монета немного тяжелее настоящей. Сколько нужно взвешиваний на чашечных весах без гирь, чтобы определить фальшивую монету, если известно, что во время одного из взвешиваний весы могут показать неверный результат?

И – каюсь – даже не задумавшись толком над нею – написал автору:
То, что должно хватать 13 взвешиваний, я понимаю. То, что скорее всего существует троичный код Хэмминга из 3^10 кодовых слов (длины 10 каждое) с расстоянием 3 между кодовыми словами, я тоже понимаю. Хотя ни разу его и не видал. Но ведь для существования плана взвешиваний мало существования такого кода, нужно еще и сбалансированность по каждому разряду обеспечивать... Короче, как Вы предполагали это решать?

В ответ получил ссылку на форум c головоломками на SciTecLibrary.ru, http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1145890398, где с чувством восхищения простотой прочёл следующее изящное решение (от Pupugai, увы, не знаю, кто это такой).

Первые 10 взвешиваний как обычно: 
Нумеруем монеты и за k-ое взвешивание сравниваем монеты с k-ой цифрой в троичной системе 1 и монеты с k-ой цифрой в троичной системе 2.
В итоге получаем одного Главного Кандидата - монету, которая будет фальшивой при условии, что все взвешивания были правильны.
И еще 20 дополнительных кандидатов, которые могут быть фальшивыми при одном неправильном взвешивании (по 2 кандидата на одно неправильное взвешивание). 
11-е взвешивание: 8 и 8 из числа дополнительных кандидатов.
Если одна из чаш перевесит, то мы знаем, что хотя бы одно неправильное взвешивание уже было, и фальшивая монета либо Главный Кандидат, либо одна из 8 перевесивших. Из этих 9 монет находим фальшивую стандартным способом за 2 взвешивания.
Иначе фальшивой может быть только Главный кандидат или одна из четырех оставшихся монет. 
Делаем 12-е взвешивание: 2 и 2 из этих четырех.
Если равновесие, то фальшивая - Главный кандидат. Иначе опять уже было неправильное взвешивание и фальшивая одна из трех, которую находим за одно 13-е взвешивание.

Но не успел я мысленно обругать себя за то, что не сумел решить задачку, как получил по башке еще более красивым рассуждением от WhiteKnight.


  1. Нумеруем монеты i10...ik...i1, ik=0,1,2; k=1..10
  2. В k-ом взвешивании на одну чашку кладем монеты с 0 в k-ом разряде, на другую с 1. Результат k-ого взвешивания Wk записываем как: 
       0 - перевесила чашка с "0"
       1 - перевесила чашка с "1"   2 - равновесие (фальшивка в группе с 2 в k-ом разряде)
  3. Результат взвешивания W10...Wk...W1 указывает на номер "главного" кандидата (не было ошибок в первых 10 взвешиваниях). Если ошибка произошла в k-ом взвешивании, то добавляются два дополнительных кандидата W10W9...Dk...W2W1, где Dk >< Wk не совпадающие с Wk две другие цифры. Итого имеем 20 дополнительных кандидатов. 
  4. 21 монету-кандидат дополняем 6 настоящими (любыми из оставшихся) до 27 и организуем 3 дополнительных взвешивания по прежнему принципу. Занумеруем их j3j2j1. 
  5. Если в основных взвешиваниях ошибки не было - главный кандидат фальшивый - то ошибка может произойти в одном из доп. взвешиваний. Главного кандидата занумеруем 000 - результат дополнительных взвешиваний V3V2V1 без ошибки должен быть 000. Ошибка в любом из взвешиваний/разряде даст один из результатов 100, 200, 010, 020, 001, 002. Именно на эти 6 мест мы помещаем настоящие монеты. На остальные 20 мест - дополнительных кандидатов.
  6. Если ошибка случилась в основных взвешиваниях, то результат дополнительных взвешиваний V3V2V1 безошибочно укажет номер одного из 20 доп.кандидатов.
И уже после этого автор задачи – мой знакомый, Lactarius – убил меня наповал, опубликовав (там же, по ссылке Ответ #14) «бонусную» задачу.
Пусть имеется 36 монет. При этом известно, что не более двух взвешиваний могут оказаться ошибочными. Сколько взвешиваний потребуется для определения фальшивой монеты?

Давайте сначала сосчитаем. Вместе. Пусть мы проделали N взвешиваний (и имеем 3^N исходов). За эти взвешивания наш Соперник мог ни разу не обмануть, или обмануть 1 раз (2N вариантов) или обмануть дважды (4*N(N-1)/2 вариантов, так как для каждого выбора пары неверных взвешиваний есть 4 варианта ответа). Не очень трудно сосчитать, что наименьшим N, при котором выполнено неравенство 3^N 3^6 (1+2N+2N(N-1)), является N=11. При этом выражение в скобках (1+2N^2) оказывается равным 1+22+220=243 = 3^5, то есть равенство здесь снова точное!

Кивок в сторону. Может быть, Вы когда-нибудь пробовали решать уравнение 1+2n^2=3^m. Пара (11,5) – это наибольшее из его целочисленных решений... Но я уже примерно понимал, как действовать. Давайте еще раз вместе. 

Первый этап - 6 взвешиваний по "покоординатному" плану. После них у нас имеется следующая картинка
1 "главная" ФМ при условии, что весы ни разу еще не врали
12 "дополнительных" ФМ при условии, что весы врали 1 раз (2 варианта ошибочного ответа на каждом из 6 взвешиваний)
60 "вторичных" ФМ при условии, что весы врали уже два раза (4 варианта на каждой из 15 пар взвешиваний)

И что дальше? У нас осталось 5 взвешиваний - 243 варианта. При этом для главной монеты всё еще есть 51 вариант (1 без обмана, 10 с одним обманом, 40 с двумя), для 12 дополнительных есть 12+120 вариантов не более чем с одним обманом, а для оставшихся 60 – всего по одному варианту. Формально 51+132+60=243, то есть всё сходится, - но как дальше взвешивать?? Нам нужно сделать так, чтобы любой из результатов первого взвешивания оставлял 81 вариант. Значит, придется как-то взвешивать не только вторичные ФМ – их нам просто не хватит.
Допустим, мы положили на весы по X дополнительных ФМ и по Y вторичных. Тогда при равенстве у нас останется 1+8+24=33 варианта с главной монетой, (60-2Y) вариантов со вторичными и... сколько ещё? Во-первых, действительно может оказаться, что это взвешивание не содержит ошибки, и тогда остаются 12-2X дополнительных. Во-вторых, это взвешивание может быть ошибочным, а тогда 2X дополнительных превращаются во вторичные! Иначе говоря, у нас остается 33 + (12-2X)*9+(60-2Y+2X) вариантов. Это даёт уравнение 8X+Y=60. Ура! Что-то прояснилось. Теперь просчитаем еще уравнение для результата «одна из чаш перевесила», и получим систему, из которой найдём X и Y
Но не тут-то было: второе полученное уравнение в точности совпадает с первым. (Вообще говоря, это и не удивительно, просто в горячке не пришло в голову.)
Ну, значит, однозначного решения системы не получается, а следовательно, можно брать, например, X=6 и Y=12. А вот дальше что? У-у-у... Я покопался в вариантах еще какое-то время и понял, что лучшим выходом будет решение с планом а-ля WhiteKnight. Поиск этого решения занял у меня часа два, но я справился. Вот оно:

Теперь составим план на оставшиеся 5 взвешиваний. Отметим, что каждая монета в таком плане однозначно характеризуется набором координат - пятимерным вектором, состоящим из чисел 0,1,2. i-я координата такого вектора говорит нам, на какую из чаш весов эта монета кладется в i-м взвешивании (i от 1 до 5). Для успешности плана (не в конкретной задаче, а вообще) достаточно, чтобы у разных монет не было одинаковых векторов координат. Еще нужно, чтобы в каждом взвешивании на чашах было поровну монет, но это кажется намного более простым требованием. "Главной" ФМ мы сопоставим вектор 00000.
Для "дополнительных" назначим следующие 12 координат:
01122
02211
20112
10221
22011
11022
12201
21102
11220
22110
11111
22222
Заметим, что хеммингово расстояние между всеми этими точками не меньше 3. Это очевидно для любой пары вида "одна из 10 первых точек + одна из двух последних" и для всех пар точек, в которых 0 стоит на одной и той же позиции. Если же у двух точек индекс (позиция) нуля отличается, то отличаются также позиции у хотя бы одной единицы и хотя бы одной двойки, потому что все эти точки получены циклическими сдвигами – две одинаковые цифры СТОЯТ РЯДОМ ЗА нулём или ПЕРЕД ним.
Так как расстояния не менее 3, то все точки, находящиеся на единичных расстояниях от этих 12 точек (а таковых ровно по 10 штук), различны. На расстояниях 1 и 2 от точки 00000 находятся 10 точек с четырьмя нулями в координатах и 40 точек с тремя нулями - все они отличны от всех вышеперечисленных.
Итого сколько у нас осталось неперечисленных точек, то есть таких, которые находятся на расстоянии более 1 от "дополнительных" и более 2 от "главной"?
243 - 12 - 120 - 1 - 10 - 40 = 60.

Именно в них мы и поместим все "вторичные" ФМ. План готов. Проделав взвешивания по плану, мы попадём либо в одну из точек-монет (и тогда она и есть фальшивая), либо в точку, соседнюю с "дополнительной" монетой (и тогда фальшивой будет эта дополнительная), либо в точку на расстоянии не более 2 от "главной" (и тогда фальшивой будет "главная" монета.