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

Алгоритмические аспекты школьной геометрии
(тезисы доклада в Кирове на конференции по математическому образованию одаренных школьников, 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 = AB² /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

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

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

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

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

В первом номере "Кванта" за 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.

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

А в качестве алгоритма дележа на  «Валькирии» используются правила, описанные в упражнении 3.

1.      Самый старший пират рассказывает остальным свой план.

2.      Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».

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

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

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

а) Как 15 этих пиратов поделят 20 монет?

б) Как 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?

С4

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

С5.**

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

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

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