Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Сколько всего прямоугольников?





Начальные шаги задачи вполне доступны младшеклассникам и послужат хорошей тренировкой для упорядоченного перебора. В общем виде ответы выражаются многочленами невысоких степеней от размеров фигур. Интересно, что прямоугольников в квадрате со стороной n оказывается столько же, сколько кубиков в кубе со стороной n. Возникает задача доказать это равенство непосредственно – не подсчитывая количество таких квадратиков и кубиков по отдельности, а установив взаимно однозначное соответствие между ними. Это пример обратной задачи комбинаторики (термин А.К. Звонкина).

 

Замок

Ссылка.http://www2.edc.org/makingmath/mathprojects/simplex/simplex.asp. Подробное обсуждение на английском языке с педагогическими и методическими комментариями.

Число турниров

Простым перебором с десятью командами не справиться, поэтому надо обобщить задачу: сколько разных расписаний для n команд? Для двух, трёх, четырёх нетрудно найти ответ перебором, после чего нетрудно угадать закономерность. Знающим она напомнит формулу количества разбиений на пары, к которому действительно можно свести эту задачу.

 

Число циклов

Экспериментальное исследование можно проводить, не зная ничего, кроме техники «упорядоченного перебора». Тогда по ходу задачи можно открыть, например, количество перестановок данных n чисел, понять разницу между размещениями с повторами и без, и т.д. Однако полное доказательство под силу скорее ученику, уже владеющему формулами перестановок, сочетаний и размещений

Вот вопросы, которые помогут решить задачу:

1) Сколько существует полных циклов (т.е. циклов длины k) из k элементов?

2) Сколько существует способов выбрать k элементов из n (порядок неважен)?

Перестановки диагоналей

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

Ссылка.П.С. Александров. Введение в теорию групп. Бюро Квантум, М., 2008. С. 71-74.

Ломаные

Нетрудно доказать, что такой ломаной с нечётным числом звеньев быть не может. Оказывается, ломаные с чётным числом звеньев n существуют для всех . Их можно строить по-разному. Так, для n = 10 можно взять правильную 5-угольную звезду и «сломать» каждое звено в середине. Дальнейшая классификация упирается в важный для всей математики вопрос: какие объекты считать разными, а какие – одинаковыми?

Наиболее разработанный подход к этому вопросу – комбинаторный: звенья ломаной нумеруются и фиксируется, какое с каким пересекается, то есть каждой ломаной ставится в соответствие нумерация. Далее можно исследовать, для каких нумераций существует соответствующая им ломаная. Часть ограничений формулируется довольно быстро (например: пересекаются звенья, номера которых имеют разную четность), другие возникают при попытках построить ломаную по данной нумерации.



Задача перекликается с теорией узлов, см., например, А.Б. Сосинский. Узлы и косы. М., МЦНМО, 2001.

Ссылка.[K2, c. 123]. Сделаны начальные шаги.

АЛГОРИТМЫ

Монетки

Используется важная идея – сведение задачи к более простой решённой. Умея решать задачу про три монетки, легко свести к ней задачу про девять монеток, и так далее. Сначала добейтесь, чтобы ученик мог объяснить порядок своих действий для конкретных случаев, а уж потом, если удастся, формулировал его в общем виде.

Раздели на части

Эта задача – простой пример задачи на нахождение стратегии в игре. Ответ здесь зависит лишь от чётности суммарного числа камней во всех кучах. Вообще, задачи на игры весьма перспективны в качестве тем, так как есть «интерактив» и ошибочность стратегии можно продемонстрировать в игре. Подробнее см. [статьи 4].

Игра в полоску

Ссылка. [статьи 4].Содержит полное решение задачи с подробным рассказом о том, как можно до него дойти.

Не больше половины

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

Ладья-ферзь

Ссылка. А. Шень «Игры и стратегии в математике». М., МЦНМО, 2007. П. 3. Содержит полное решение для ладьи.

Угадайка

«Детское» решение (делить пополам) можно переформулировать так: запишем числа в двоичной системе счисления и каждым вопросом будем узнавать цифру в очередном разряде. Действуя аналогично в угадайке с платой, попробуем подобрать такую систему счисления, чтобы с ответом «да» мы узнавали одну цифру, а с ответом «нет» - две цифры. Такой системой счисления является фибоначчиева (в ней не могут идти подряд две единицы). Интересно проверить, можно ли обобщить это решение на другие "цены" за ответы.

Угадайка с враньём во «взрослой» формулировке звучит так: «При передаче слова возможны ошибки. Двухкратные и более считаем маловероятными. Как исправить однократную ошибку, добавляя как можно меньше информации?» Это делают самоконтролирующиеся коды, например, код Хемминга.

Эволюция клеток

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

1) в кольце бывает либо цикл, либо все кольцо становится белым (что тоже можно рассматривать как цикл);

2) если в конечной полосе длиной 3, 7, 15, … в начале всего одна черная клетка, то рано или поздно вся полоска станет белой;

3) эволюция суммы является суммой эволюций, т.е. если ввести операцию бинарного суммирования чёрное + чёрное = белое и т.д., разбить полоску на две (сумма которых даёт исходную), проэволюционировать их по отдельности и просуммировать, то получится эволюция исходной полоски.

После четкой формулировки гипотезы следует попытаться доказать ее или опровергнуть.

Возможные дальнейшие вопросы.

1. Если зашифровать узор в виде двоичного числа, как оно будет эволюционировать?

2. Найдите узоры, которые периодически повторяются со временем. Какими свойствами они обладают? Что можно сказать о полосе произвольной ширины? О всей клетчатой плоскости?

Обобщения. Игру можно рассматривать также на конечной полосе, на кольце, в прямоугольнике и т.д.

Ссылка.Квант. 1970. № 4. Задачник Кванта. Задача М19 (Васильев Н.Б.).

Мудрецы у людоедов

Игру можно красиво представить, разыграв ситуацию с детьми.

Нетрудно придумать какой-нибудь способ для спасения половины или двух третей мудрецов. Ясно, что последнего гарантированно спасти нельзя, поскольку никто не видит его колпака. Будем стремиться к наилучшему результату: попробуем гарантированно спасти всех, кроме последнего! (Трудность состоит в том, что при рассмотрении двух и трёх мудрецов в голову приходят способы, которые не поддаются обобщению.) Заметим, что каждый мудрец видит колпаки всех, кто перед ним. Поэтому, зная то, что видит последний мудрец, предпоследний мог бы однозначно восстановить цвет своего колпака. Но как последний мудрец может зашифровать видимую им картинку всего одним из двух слов «чёрный» или «белый», т.е. одним битом? Это кажется невозможным, но ведь при удалении одного мудреца количество колпаков данного цвета либо не меняется, либо уменьшается на 1. Поэтому подходящей характеристикой является чётность колпаков данного цвета.

Обобщение. Пусть колпаки будут не 2 цветов, а k цветов.

 

Сумма кубов цифр

Если исходное число меньше 10000, то и все последующие – тоже. Последовательность однозначно определяется исходным числом и обязана быть периодической. Удобно говорить об орбите числа. Встаёт вопрос о длине периода орбиты. Нетрудно найти числа, переходящие сами в себя (период = 1). Можно написать программу, которая строит орбиты чисел, скажем, от 1 до 100. Многие числа попадают в орбиты других чисел. Интересно найти условия, при которых орбиты, содержащие два данные числа, заведомо не пересекаются.[9] Одним из инвариантов орбит является остаток от деления числа на 3.

Обобщение.Аналогичные вопросы можно ставить, задавая другие итераторы – правила вычисления последовательности (сумма квадратов цифр, количество букв в числе, записанном по-русски и т.д.).

 

Задача о самураях

Комментарий.Хорошая задача на идею рекурсии. На представлении тем эту задачу можно подать очень увлекательно, поставив несколько школьников в круг и разыграв считалочку с выходом. В более миролюбивой формулировке говорится о считалочке или о вычёркивании точек, стоящих по кругу. Однако возникла эта задача во вполне военной обстановке: в древнерусском переводе «Иудейской войны» Иосифа Флавия есть история о том, что «он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.» (Р. Грэхем и др. «Конкретная математика». М., Мир, 2006. С. 25).

Стоит составить таблицу номеров уцелевших в зависимости от начального числа самураев. Далее можно увидеть закономерность, которую, впрочем, не так легко доказать напрямик. Можно перенумеровывать самураев после прохождения каждого круга, найти рекуррентный закон изменения номера уцелевшего и, используя его как шаг индукции, доказать найденную закономерность. Другой подход – заметить, что если вначале было 2n самураев, то выживает первый. Значит, если их 2n + l, то останется в живых тот, кто является первым после l исключений. (Этот подход быстрее приводит к цели, но вряд ли поддаётся обобщению.)

Обобщение. 1.Пусть харакири делает каждый k-й, начиная с k-го. (Уже в случае k = 3 всё заметно сложнее – поэтому-то мы пренебрегли исторической правдой и сформулировали задачу для каждого второго.)

2.Нужно узнать также номер предпоследнего живого («спаси себя и друга»).

Ссылка. Р. Грэхем и др. «Конкретная математика» М., Мир, 2006. С. 25 и дальше. Содержит решение задачи для каждого k-го и различные обобщения задачи.

 

Обезьяна и кокосы

Заметим, что после того, как первый кокос разбит, задача сводится к задаче об одном кокосе. Полезно перевернуть задачу: какова этажность дома, который можно «протестировать» данным количеством бросков (имея два кокоса)? Этаж для броска данного кокоса надо выбирать так, чтобы количество проверок нижних этажей, если он разбился, равнялось количеству проверок более высоких, если он цел. Идея «равномерной траты попыток в пересчёте на приобретаемую информацию» - общая в подобных задачах, ср. «Угадайку», да и «Монетки».

Обобщение. Пусть будет 2 кокоса и F этажей; пусть будет K кокосов и F этажей.

Игра Ним

Возможный подход к решению такой: рассмотрим сначала одну кучку (очевидно), две кучки (симметричная стратегия). Для трёх кучек поставим такой вопрос: пусть в двух из них количества камней фиксированы – a и b; сколько камней с должно быть в третьей кучке, чтобы позиция была проигрышная? (Заметим, что с определяется по a и b однозначно, т.к. если бы для данных a и b было два разных значения c, то игрок мог бы из большего привести позицию к меньшему, т.е. привёл бы противника к проигрышной позиции.) Рисуем квадрант с натуральными a и b, находим по ним c, заполняем таблицу, смотрим на получающиеся узоры и ищем закономерности. «Правильная» закономерность обобщается уже на любое количество кучек.[10]

Ссылки.

1. А. Шень «Игры и стратегии в математике». М., МЦНМО, 2007. П. 4. Содержит полное решение.

2. В.В. Шилов. «Ещё раз об игре Ним». «Потенциал», 2009, N 6. Содержит увлекательные истории про эту игру.

Обобщение. Пусть имеются две кучи предметов (например, спичек), и два игрока поочередно берут либо произвольное число предметов из одной кучи, либо поровну

из каждой кучи. Получится более сложная игра, называемая Цзяньшицзы. Если в анализе игры Ним помогала двоичная система счисления, то в Цзяньшицзы помогает фибоначчиева система. См., например, А.М.Яглом, И.М. Яглом. «Неэлементарные задачи в элементарном изложении». М., ГИТТЛ, 1954. Задача 129.

 

РАБОТЫ









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.