Поскольку различных значений у слов конечное количество, то среди слов найдутся два с одинаковым значением. Пусть это слова из и букв

Докажем, что слово имеет то же значение, что и слово из букв Если для такой пары оказывается, что то это верно. В противном случае при

То есть одинаковые значения имеют слова из букв. Отсюда и следует верность утверждения, если продолжать до тех пор, пока

Тогда:

Что и требовалось доказать.

Заметим, для начала, что если на доске чётное количество чисел, то ходит Марина, а если нечётное — Саша.

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

Тогда, если то Саша сразу находится в выигрышном для себя положении, а если то он должен первым ходом перемножить две единицы и передать Марине ситуацию ровно с одной единицей.

Докажем теперь, что если или то выигрывает Марина. Заметим, что если в какой-то момент на доске окажутся одни нули, то Марина выигрывает. Тогда при Марина точно уже выиграет.

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

Пусть сейчас ход Саши. Если он оставляет ситуацию разнообразной - хорошо. Если же он сделал ситуацию не разнообразной, то поскольку убрать ноль он не может, как и убрать сразу две единицы, то сейчас на доске ровно две единицы, а остальные нули. Марина своим следующим ходом заменяет эти две единицы на и теперь на доске одни нули.

Пусть сейчас ход Марины. Перед ней точно есть Если есть какие-то ещё числа, то их чётное количество, то есть хотя бы два, поэтому она может сделать ход с ними, оставив ситуацию разнообразной. Если же других чисел нет, то Марина меняет на оставляя Саше тогда он делает ход и оставляет и Марина выигрывает, делая после этого

Осталось заметить, что при и ситуация на доске уже разнообразная, а при Марина может сделать её разнообразной своим первым ходом.

Легко видеть, что Ярослав будет находится вначале у замка потом —

Если то следующим действием Ярослав закроет замки с номерами и, возможно, ещё какие-то. В любом случае, замок под номером останется закрытым.

Если то дальше Ярослав закроет все замки с номерами от до и вновь встанет у замка с номером Сейчас открыты замки Дальше Ярослав закрывает замок и переходит к замку потом закрывает замки и переходит к замку который и оставляет открытым.

Первое решение.

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

Второе решение.

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