суббота, 11 марта 2017 г.

История про квадрат с пятиугольником


На минувшей неделе я снова вёл Geometry-Kanal на Телеграме. И совершенно неожиданно для себя "застрял" на внешне несложной геометрической задаче.

Здесь очевидным образом расположены квадрат и правильный пятиугольник, а спрашивается угол между "псевдодиагоналями" CE и DF. Взял я эту задачу из геометрической группы в фейсбуке Romantics of Geometry, до ответа догадался минут за пять, и решил, что к вечеру как-нибудь найду разумное решение. В итоге не нашел ничего, хотя постарался. Но об этом - ниже.



Сразу должен сказать, что на http://www.cut-the-knot.org есть целых два решения задачи. Одно - через тригонометрию (ей-богу, нетрудное, но громоздкое), другое - через комплексные числа (еще менее трудное и даже не слишком громоздкое, но все-таки комплексные...).

При этом на вышеупомянутом cut-the-knot есть замечательная подсказка:

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

Я могу найти (то есть доказать) величину угла между DF и CJ. Проблема в том, как доказать, что C,E,J лежат на одной прямой. Еще я могу доказать величину угда между CE и DK. Проблема та же самая - как доказать, что D, F и K лежат на одной прямой. И, наконец, у меня всё получится, если рассматривать точку H как вторую (кроме А) точку пересечения двух окружностей - сплошной и пунктирной, и суметь доказать, что она лежит хотя бы на одной из двух псевдодиагоналей. То есть прямо кладезь разных фактов, ни один из которых не желает доказываться геометрически, но при этом любого хватит, чтобы решить задачу.

Ну и еще на закуску один вариант пути доказательства.

Здесь М - общая точка двух окружностей (на рисунке показаны дуги, центром одной является D, а другой - F). Если доказать, что она попадает на CE, то дальше тоже всё будет хорошо (четырехугольник DMFB представляет собой два равнобедренных треугольника с общим основанием MB; поэтому DF является биссектрисой углов D и F, а это уже позволяет сосчитать все нужные углы). Но вот как-то не складывается и этот факт тоже...




суббота, 18 февраля 2017 г.

Треугольники и квадраты

33. Как тремя единичными квадратами полностью покрыть [возможно, с наложениями] правильный треугольник со стороной 2? Можно ли покрыть правильный треугольник со стороной, большей двух? Отметим переменную точку D на стороне и точку O - центр квадрата. Будем поворачивать квадрат так, чтобы вершина треугольника оставалась вершиной квадрата, а точки D и O лежали на противоположной стороне. При таком вращении размер квадрата будет уменьшаться. В момент около t=0.523 (ползунок можно приостановить, нажав на паузу) квадраты перестают покрывать весь треугольник. Именно в этот момент длина стороны квадрата - наименьшая относительно фиксированного треугольника, а если считать ее равной 1, то сторона треугольника оказывается наибольшей.

четверг, 16 февраля 2017 г.

Теорема Боттемы


Задача 32 в Геометрия-канале имеет собственное имя - она называется теоремой Боттемы
Эне Боттема (1901-1992) - голландский математик, наиболее известный своими трудами в геометрии.




Теорема Боттемы утверждает, что середина отрезка Ab Ba - точка М - не зависит от положения вершины C. На этом рисунке показаны некоторые вспомогательнгые свойства точки M.

Мы приведем три разных доказательства теоремы. Первое - совсем простое, но использующее комплексные числа.

Пусть вершины A,B и C задаются комплексными числами α, β и γ соответственно. Умножение комплексного числа на i равносильно поворота на угол p/2 против часовой стрелки, а умножение на (-i) - повороту в обратном направлении. Это значит, что Ba = α + (γ - α)·i и Ab = β + (γ - β)·(-i), откуда (Ab + Ba)/2 = (α + β)/2 + (β - α)·i/2. Очевидно, что это выражение не зависит от C = γ, что и требовалось доказать. [Отсюда же сразу получается, что AMB - равнобедренный прямоугольный треугольник, как показано на рисунке выше],

Второе доказательство - вычисление в координатах - для тех, кто не знаком с комплексными числами.






































Расположим начало координат в точке O - середине отрезка AB. Пусть A=(1,0), B=(1,0), а C=(x,y). Тогда нетрудно сосчитать координаты 
Ab=(y+1,1x) и Ba=(1y,1+x), откуда середина отрезка между ними имеет координаты
 (Ab+Ba)/2=(0,1).


Ну а третье доказательство будет в стиле "смотри". Вертикальный отрезок посередине
делит 
прямоугольник пополам, поскольку проходит (по построению) через середину
отрезка AB, а 
левая вертикальная сторона находится от А на таком же расстоянии, как
правая - от B (оба этих расстояния равны высоте CH). 
Следовательно, середина отрезка
EG непременно попадает на этот отрезок. При этом - попадает в его середину, 

так как точка E находится на расстоянии синего отрезка от нижней стороны 
прямоугольника, а точка G - на таком же расстоянии от верхней стороны.  

Все приведенные здесь доказательства взяты с сайта Александра Богомольного Interactive Mathematics Miscellany and Puzzles
http://www.cut-the-knot.org/Curriculum/Geometry/GeoGebra/VisualBottema.shtml,

.

четверг, 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' строятся аналогично.

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