|
||||||||||||||||||
|
СодержаниеММ237Конкурсная задача ММ237 (7 баллов) Студент математического факультета Вася Пупкин написал на доске некоторую перестановку A из S10 в виде произведения независимых циклов (запись каждого цикла начинается с наименьшего элемента; опускались ли в записи циклы длины 1 - неизвестно). Васины однокурсники прокомментировали эту запись.
Аня: A6 – тождественная перестановка.
Вася (умница и отличник) заметил, что количество верных утверждений его однокурсников равно наибольшей длине цикла в A. Решение Привожу решения Виктора Филимоненкова и Анатолия Казмерчука. Обсуждение
Естественно конкурсанты начали решение с проверки утверждений Мани и Сани, истинность которых не зависит от записанной на доске перестановки. Увлекшись обобщениями вопроса о количестве решений уравнения X2=B в S10, я доказал, что для любого простого p и любого n уравнение Xp=B имеет либо единственное решение, либо количество его решений кратно p (для составных показателей это уже не так). Не остановившись на достигнутом, я вывел общую формулу для количества решений уравнения Xk=B в Sn (понятно, что ответ зависит от цикловой структуры B). Конечно, я понимал, что вряд ли являюсь первопроходцем: уж больно классический объект и слишком естественна постановка задачи. Но всерьез гуглить начал лишь только получив результат. Разумеется, у меня нашлись предшественники. Причем, насколько мне удалось установить, первая работа с ответом на этот вопрос была на русском языке (хотя я старательно формулировал запрос на английском): http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=2731&option_lang=eng Приведу все возможные количества решений Xk=B в Sn для небольших k и n.
k = 2
k = 3
k = 4
k = 5
k = 6 Поясню, как я реагировал на ошибки при подсчете возможных количеств решений уравнения X2=B в S10. Фатальная ошибка (вместо самих решений считалось лишь возможное количество их цикловых видов), приведшая к «опровержению» утверждения Маши, разумеется, нарушила весь дальнейший ход решения и была отражена в оценке. Автору неверных комбинаторных формул при подсчете количеств решений повезло больше. Одно решение при этом не исчезло, а три не появилось. Поэтому дальнейшая цепочка рассуждений привела к верному ответу. Но оставить ошибки на промежуточных шагах без внимания я, конечно, не мог. Наконец, локальные арифметические ошибки, не повлиявшие на решения я вовсе не учитывал. Пример такой ошибки есть в приведенном решения Анатолия Казмерчука (там, где у Анатолия получилось 18 решений должно быть 24). В самом деле, 18 получается как сумма двух слагаемых, одно из которых подсчитано верно и равно 12. Понятно, что сумма при этом будет больше 3, что собственно и требовалось. Поэтому данная вычислительная ошибка в принципе не могла повлиять на ход решения. Неполный балл у Константина Шамсудтинова связан не с ошибками, а с недостаточно подробным изложением решения. Обосновав верную оценку утверждений Сани и Мани, Константин написал, что дальнейшее очевидно и привел правильный ответ. Закончу разбор выражением удовлетворения содержательным обсуждением предыдущей задачи и сожаления, что эта увлеченность помешала участникам диалога обратить внимание на нынешнюю. Награды
За решение задачи ММ237 участники Марафона получают следующие призовые баллы: Эстетическая оценка задачи - 4.8 балла
|
|||||||||||||||||
|
||||||||||||||||||
|