Считалочки, шифры и культура понимания задач
"Отгадай цвет шапочки". Классика жанра.
Обещала ответы еще в прошлый понедельник выложить, но загулялась задержалась
Считалочка
"Стакан-лимон, выйди вон", "Вышел месяц из тумана.." - водящий начинает с кого придется;
еще в дошкольном детстве задумывалась: действительно ли "посчитаться" - это как лотерея
или можно заранее подгадать кто останется?
Неполиткорректная задача из архаичного учебника по-сути считалочка и есть:
1----2- ---3---4----5----6----7!
Ста-кан ли-мон вый-ди вон
Иногда играют по словам, иногда по слогам - и так и так встречала, слогов как раз семь.
Считаются так же как, если бы стояли по кругу:
На кого выпало "вон" - свободен, остальные продолжают.
Так с кого начать, чтобы в конце концов освободились все, кроме перевернутой спички?
[Задача Иосифа Флавия]
Найти ответ для конкретного числа участников, вычеркивая каждого седьмого седьмого на чертеже - минутное дело.
Сущестует ли общее правило, как занять выигрышную позицию в считалочке?
Задание со спичками является вариантом не менее кровопролитной Задачи Иосифа Флавия,
основанной на легенде о защитниках Йодфата:
отряд попал в окружение, сорок воинов, включая самого Иосифа, на время укрывшись в пещере, предпочли быструю развязку мучительной смерти в плену. Чтобы не накладывать на себя руки, порешили, что каждого третьего убьют двое его товарищей; сомкнув круг, проделают то же самое еще раз... И так пока не останутся двое, которые должны будут убить друг друга.
По легенде Иосиф Флавий нашел решение на ходу, он и его друг остались живы
(сдались, и - дальше целая история, тоже интересная, но не про математику).
Как нашел - о том история умалчивает. В теории чисел известно общее решение только для "считалочки из двух слов" - т.е. когда выбывает каждый второй (и тоже, не сказать, чтоб такое уж наглядное: "В случае чётного n(числа участников) получаем, что будут вычеркнуты все чётные числа, а потом останется задача для n/2, тогда ответ для n будет получаться из ответа для n/2 умножением на два и вычитанием единицы (за счёт сдвига позиций). Аналогично, в случае нечётного n будут вычеркнуты все чётные числа, затем первое число, и останется задача для (n-1)/2, и с прибавлением единицы с учётом сдвига позиций.").
Для "считалочек" из более чем двух слов все существенно сложнее:
"Несмотря на простой вид задачи и большое количество статей по этой и смежным задачам, простого аналитического представления решения задачи Иосифа до сих пор не найдено. Для небольших k выведены некоторые формулы, но все они трудноприменимы на практике (например, см. Halbeisen, Hungerbuhler "The Josephus Problem")."
Известна так называемая рекуррентная формула
k(n, m) = 1 + (k(n-1, m) + m - 1) mod n
Если принять что расчет начинается с первого в шеренге, то k - исходный номер выжившего,
m - раппорт отсчета ("число слов в считалочке") и n - число участников.
(Выражение типа А mod В, если попросту, означает остаток от деления А на В)
Всё вместе подразумевает совсем не сложное действие: чтобы найти, какой номер выживет из сорока участников,
нужно взять номер выжившего для случая тридцати девяти участников прибавить семь (у нас же каждый седьмой освобождается),
отнять один, взять остаток от деления на сорок и прибавить к нему единицу.
- А где взять значение для 39-ти?
- Нетрудно посчитать, зная значение для 38-ти.
- Ага, а его из k для 37-ми?
- Именно. Это и есть рекуррентность.
Фишка в том, что значение для одного участника - тривиально и очевидно: один и выживет.
Соответственно для 2 считаем по формуле 1+(1+7-1)mod2 остаток от деления 7 на два - один,
таким образом - выживет второй. Не трудно посчитать для 3-х, 4-х...
Рекуррентная форма хороша для программирования, а в боевой обстановке быстрее
начертить круг, расставить точки и последовательно вычеркивать...
Вот такая "простенькая задачка".
Практическое следствие: считалочки из более чем двух слов вполне надежны в качестве жребия.
Даже коротенький "стакан-лимон..." для большой компании рассчитать на ходу вряд ли получится,
эпичный "на зо-ло-том крыль-це..." и подавно.
Разве что запомнить, в случае постоянного числа участников =)
Муторно? Представьте каково будет ребенку.
В наше время исчисление остатков, "вычетов" проходили разве что мельком, факультативно.
Сейчас это мейнстрим прикладной математики, операция mod важна не менее привычных четырех действий арифметики.
(Даже популярные статьи на тему крипто/стеганографии пестрят "сравнениями по модулю" и значками логических операций;
шифрование - это не только "шпионские штучки", это технология передачи и защиты данных,
одна из важнейших дисциплин в эпоху электронных коммуникаций.)
В зависимости от программы по информатике, с "умножением по модулю" возможно придется столкнуться
уже бабушкам второклассников. Математика "вычетов" не сложнее прочих разделов, но непривычна, в нее надо
"въехать", проникнуться темой, лучше это сделать заблаговременно, на задачах-загадках, на считалочках.
Следующий номер программы - "Дисциплина понимания условий"
Никакой заморочной теории, задача построена на внимательном прочтении текста.
В стиле традиционного понимания условий: всё что "дано" - существенно,
лишних данных в условии нет. Ответ существует.
Решение:
Отгадчику известно произведение возрастов дошкольников - он видит сколько голубей у скамейки.
Пары чисел от 1 до 6 дают не так уж много сочетаний:
1х6 2х6 3х6 4х6 5х6 6х6
1х5 2х5 3х5 4х5 5х5
1х4 2х4 3х4 4х4
1х3 2х3 3х3
1х2 2х2
считаем что, раз "голубей" - то больше одного.
Присмотримся к полученным выражениям. Что мы можем сказать например о 5х5 ?
- То, что 25 никаким иным способом не получишь, кроме пятью-пять.
Это значит, что отвечающему не понадобилось бы дополнительной информации,
сразу бы ответил. 5х5 вычеркиваем.
Аналогично вычеркиваем всё, кроме 1х6=2х3 2х6=3Х4 1х4=2х2
Подсказка "Старший похож на мать" исключает вариант 2х2.
Ответ: год и четыре.
- Как это, а остальные варианты куда делись 1х6=2х3 2х6=3х4 ?
- Отгадчику число голубей известно точно, ему только и нужно было, что выбрать между 1х4 и 2х2.
А мы остановились на этом решении исходя из того, что - дальнейших вопросов не последовало.
Будь голубей шесть или двенадцать, без дальнейших расспросов не обошлось бы.
Учитываем по умолчанию подразумеваемый принцип "Ответ существует" -
т.е. в данному случае: существует однозначный выбор.
- А как это относится к математике, может собеседнику просто надоело допытываться?
- А как относится к математике, что "сделать пюре!" не годится в качестве ответа
к задаче "поделить девять яблок на пятнадцать человек"?
Существует система умолчаний, традиция понимания текстовых условий.
Иногда умышленно составляют задачи "на грани", чтобы привести в недоумение развлечь публику, иногда - за гранью:
с такими лучше всех справляются митрофанушки, получается задача на нестандартное мышление
хороший тест на отсутствие культуры понимания условий.
Современный фольклор, новые персонажи
Переходим к третьему пункту программы,
тематически перекликающемуся с первыми двумя:
"Задачу для восьмикласников" можно переформулировать как:
какие нужно назвать три числа, что бы когда их умножат на три задуманные
и сообщат сумму - было бы легко определить, на что умножили?
Восьмиклашки решают сходу: только что прошли поразрядное представление чисел, материал свеж и актуален.
Бери 10000 100 и 1, на что хочешь умножай (двузначное! не забываем) в ответе не ошибешься.
Рядовое, вполне корректное задание для кружковцев.
Наверняка найдется девочка Агаша (от Агафья), которой этот вывод покажется неоднозначным.
Заменим в слове "бабушка" буквы - числами: 2 1 2 21 26 12 1 по номерам в алфавите.
Возьмем только нам известный произвольный ряд из семи чисел 8 3 6 2 10 5 13 - это будет ключ.
Умножим последовательно "оцифрованное" слово на числа из ключа: 2х8 1х3 2х6 21х2 26х10 12х5 1х13,
получим 16 3 12 42 260 60 14. Восстановить исходное сообщение может только тот, у кого есть ключ.
Но если данные просуммировать, то ответ, вообще говоря, будет не однозначен.
(напр. 5, 7, 9 можно умножить на 14, 50, 12, а можно на 70, 10, 12,
результат получим одинаковый 5х14+7х50+9х12 = 5х70+7х10+9х12 )
Матанолюбвая интернет-общественность вспоминает о ключах шифрования,
нетривиальность задачи разложения на простые слагаемые...
загадчики надувают щеки - "Программа начальной школы! какие все тупые"
Фокус в том, что решения в общем виде, для любых х y z, не требуется,
достаточно придумать единичный удобный ответ.
Добавочка. Вытащу из комментов -
"Идут в поход трое.
У одного с собой две палки, у другого четыре.
У третьего же - шесть монет.
Развели костёр из шести палок, сготовили обед.
Как третьему отблагодарить остальных монетами?"
Поскольку в обсуждении под предыдущим постом решение уже есть, выложу под спойлером:
[Spoiler (click to open)]
Правильный ответ - "все монеты отдать второму.
По сути, третий купил у него две палки, чтобы у всех троих был равный вклад в общий костёр"
- вызывает определенные сомнения: из каких соображений палки куплены за 6 монет, а не за 5, 4, 3 ?
Задания с хохмами - фольклор нашего времени,
своеобразная литературная форма, близкая к анекдоту: с завязкой и парадоксальной развязкой.
"Культура понимания условий" соответственно изменяется - лишние данные игнорируем,
все неизвестное постулируем, в ответе приветствуется не четкая однозначность,
а чтобы он складно вписывался в сюжет, придавая миниатюре завершенность.
Честные задачи "на подумать" встречаются всё реже, и в них прежде всего ищут подначку,
пытаясь решить дело каким-нибудь остроумным экспромтом, неожиданным продолжением.
И, на закуску, еще одна хитрая увлекательная задача, из той же серии, что шапочки
Кто разобрался с предыдущими, тому по силам одолеть и эту -
[Иллюстрация в большем разрешении:]
Палец указывает на "ключ к свободе"; герою осталось лишь перевернуть монету, любую из.
Вариант 4х4 для потренироваться.
Сами выберите какую клетку загадать.
Выкладывайте решения-соображения под спойлером, скопируйте скобки: [Spoiler (click to open)]
(в комментах спойлер работает, если кто не знал)
Метод гуглится, англоязычный и хабро-перевод - метод написания алгоритма в терминах Джавы и Сиплюплюс. Так что есть возможность всласть позаморачиваться над задачей самостоятельно, избежав искуса подсмотреть готовый ответ =)