МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Хороводы, перестановки и попросту циклы

1.

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

2.

Пианист играет гамму в одной октаве туда и обратно: до-ре-ми-фа-соль-ля-си-до-си-ля-соль-фа-ми-ре-до-ре... и так далее. Какая нота будет 20-й? 30-й? 1500-й?

3.

От главных ворот центрального космопарка начиная ровно с 8 утра стартуют синие и зелёные экранопланы. Синие экранопланы отправляются каждые семь минут, а зеленые — каждые пять минут. Когда в следуюший раз одновременно взлетят и синие и зелёные экранопланы?

4.

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

5.

В алфавите людоедского племени 7 букв: Л, Ю, Д, О, Е, С, К. Людоедские шпионы обмениваются зашифрованными сообщениями. Алгоритм шифрования заменяет каждую из 7 людоедских букв на какую-то другую букву, причём разные заменяются на разные, а одинаковые на одинаковые. Докажите, что после нескольких применений этого алгоритма мы вернёмся к исходному тексту.

Hint

Hint. Смотри первую задачу.

6.

Если один раз применить перекодировщик из KOI8-R в CP1251 к строчке «Абвгдежзийклмнопрстуфхцчшщъыьэюя», то получится «юАБЦДЕФГХИЙКЛМНОПЯРСТУЖВЬЫЗШЭЩЧЪ». Сколько раз надо применить этот перекодировщик к «Наша Таня громко плачет, уронила в речку мячик», чтобы в итоге получить снова «Наша Таня громко плачет, уронила в речку мячик»?

7.

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

8.

Каждый зритель, купивший билет в первый ряд кинотеатра, занял одно из мест в первом ряду. Оказалось, что все места в первом ряду заняты, но каждый зритель сидит не на своём месте. Билетёр может менять местами соседей, если оба сидят не на своих местах. Всегда ли он может рассадить всех на свои места?