Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ237

Конкурсная задача ММ237 (7 баллов)

Студент математического факультета Вася Пупкин написал на доске некоторую перестановку A из S10 в виде произведения независимых циклов (запись каждого цикла начинается с наименьшего элемента; опускались ли в записи циклы длины 1 - неизвестно). Васины однокурсники прокомментировали эту запись.

Аня: A6 – тождественная перестановка.
Ваня: Длины всех циклов A – числа Фибоначчи.
Даня: В S10 существует ровно 3 перестановки, квадрат которых равен A.
Маня: Хм, уравнение X2 =B не может иметь в S10 ровно 3 решения ни при каком B.
Саня: Более того, количество решений уравнения X2 =B в S10 не может быть нечетным ни при каком B.
Таня: Квадрат наибольшего элемента в самом длинном цикле меньше порядка A.
Зина: A5 имеет столько же циклов, сколько и A.
Лина: Внутри всех циклов элементы строго возрастают.
Нина: Произведение всех элементов одного из циклов кратно произведению всех элементов более длинного цикла и сумме всех элементов более короткого.
Фаина: Зина, Лина и Нина правы.

Вася (умница и отличник) заметил, что количество верных утверждений его однокурсников равно наибольшей длине цикла в A.
Найдите A.

Решение

Привожу решения Виктора Филимоненкова и Анатолия Казмерчука.

Обсуждение

Естественно конкурсанты начали решение с проверки утверждений Мани и Сани, истинность которых не зависит от записанной на доске перестановки.
Причем проверка утверждения Мани оказывается наиболее сложной частью задачи. Некоторые участники предпочли ограничиться доказательством отсутствия трех решений уравнения X2=B в S10, другие же рассмотрели более общий вопрос о возможных количествах решений этого уравнения. Наконец, еще один участник привел чисто алгебраическое обоснование правоты Мани. Ведущий пошел по пути «других» (комбинаторщиков), но для надежности проверил свои теоретические выкладки возведением всех элементов S10 в квадрат (разумеется, не руками). Конкурсанты оказались более уверенными в себе и к мощи компа не прибегали (некоторые - зря :-)).
Дальнейшие рассуждения практически все вели, перебирая возможные длины наибольшего цикла. И только Влад Франк отталкивался от истинности или ложности утверждения Фаины, показав, что этот путь тоже ведет к верному ответу.

Увлекшись обобщениями вопроса о количестве решений уравнения 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
1 {1}
2 {0, 2}
3 {0, 1, 4}
4 {0, 1, 2, 10}
5 {0, 1, 2, 26}
6 {0, 1, 4, 76}
7 {0, 1, 2, 4, 8, 10, 232}
8 {0, 1, 2, 4, 8, 12, 20, 26, 764}
9 {0, 1, 2, 4, 10, 12, 16, 52, 76, 2620}
10 {0, 1, 2, 4, 6, 8, 10, 24, 26, 40, 152, 232, 9496}

k = 3
1 {1}
2 {1}
3 {0, 1, 3}
4 {0, 1, 9}
5 {0, 1, 3, 21}
6 {0, 1, 9, 81}
7 {0, 1, 3, 9, 21, 351}
8 {0, 1, 3, 9, 33, 81, 1233}
9 {0, 1, 3, 9, 18, 21, 27, 33, 351, 5769}
10 {0, 1, 3, 9, 18, 21, 33, 81, 1233, 31041}

k = 4
1 {1}
2 {0, 2}
3 {0, 1, 4}
4 {0, 1, 16}
5 {0, 1, 2, 56}
6 {0, 1, 4, 256}
7 {0, 1, 2, 4, 16, 1072}
8 {0, 1, 4, 8, 48, 56, 6224}
9 {0, 1, 2, 10, 16, 256, 33616}
10 {0, 1, 2, 4, 6, 10, 56, 64, 96, 1072, 218656}

k = 5
1 {1}
2 {1}
3 {1}
4 {1}
5 {0, 1, 25}
6 {0, 1, 145}
7 {0, 1, 25, 505}
8 {0, 1, 25, 145, 1345}
9 {0, 1, 25, 145, 505, 3025}
10 {0, 1, 25, 145, 385, 505, 1345, 78625}

k = 6
1 {1}
2 {0, 2}
3 {0, 6}
4 {0, 2, 18}
5 {0, 1, 2, 66}
6 {0, 1, 4, 396}
7 {0, 1, 2, 12, 2052}
8 {0, 1, 4, 6, 12, 36, 12636}
9 {0, 2, 4, 12, 18, 132, 91548}
10 {0, 2, 6, 8, 18, 24, 66, 792, 625176}

Поясню, как я реагировал на ошибки при подсчете возможных количеств решений уравнения X2=B в S10. Фатальная ошибка (вместо самих решений считалось лишь возможное количество их цикловых видов), приведшая к «опровержению» утверждения Маши, разумеется, нарушила весь дальнейший ход решения и была отражена в оценке. Автору неверных комбинаторных формул при подсчете количеств решений повезло больше. Одно решение при этом не исчезло, а три не появилось. Поэтому дальнейшая цепочка рассуждений привела к верному ответу. Но оставить ошибки на промежуточных шагах без внимания я, конечно, не мог. Наконец, локальные арифметические ошибки, не повлиявшие на решения я вовсе не учитывал. Пример такой ошибки есть в приведенном решения Анатолия Казмерчука (там, где у Анатолия получилось 18 решений должно быть 24). В самом деле, 18 получается как сумма двух слагаемых, одно из которых подсчитано верно и равно 12. Понятно, что сумма при этом будет больше 3, что собственно и требовалось. Поэтому данная вычислительная ошибка в принципе не могла повлиять на ход решения. Неполный балл у Константина Шамсудтинова связан не с ошибками, а с недостаточно подробным изложением решения. Обосновав верную оценку утверждений Сани и Мани, Константин написал, что дальнейшее очевидно и привел правильный ответ.

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

Награды

За решение задачи ММ237 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 10;
vpb - 8;
Виктор Филимоненков - 7;
Владислав Франк - 7;
Константин Шамсутдинов - 6.
Валентина Колыбасова - 5;
Евгений Гужавин - 2;

Эстетическая оценка задачи - 4.8 балла


 

 


Страница: [[marathon:problem_237]]

marathon/problem_237.txt · Последние изменения: 2019/09/07 13:36 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006