Пусть - итоговое шестизначное число. Пусть также и . Заметим, что если Боря своим третьим ходом поставит цифру из множества , Аня выиграет, поскольку полученное число будет делиться на 2 . Значит, .

Пусть Аня первым ходом выберет цифру , а вторым ходом - цифру 9. Если Боря на первом или втором ходу выберет цифру из множества , то своим третьим ходом Аня заберет последнюю оставшуюся цифру из множества , и Боря вынужден будет взять свою цифру из , что приведет к его проигрышу. Значит, Боря вынужден взять первые две свои цифры и взяты из множества . Заметим, что Боря вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Ане достаточно подобрать цифру так, чтобы сумма цифр давала бы остаток 2 при делении на 3 . Поскольку и не влияют на остаток этой суммы, все зависит от остатка суммы . Покажем, как действовать Ане в каждом из случаев.

Если делится на 3 , то Аня выберет цифру из набора : поскольку до этого момента эти цифры мог выбирать только Боря, как минимум одна из этих трех цифр останется не выбранной.

Если дает остаток 1 при делении на 3 , Аня выберет цифру . Как мы помним, Боря не мог ее выбрать на первых двух ходах.

Наконец, если дает остаток 2 при делении на 3 , Аня выберет цифру из набора . Боря не мог выбрать обе эти цифры, поскольку тогда , а мы предположили, что дает остаток 2 при делении на 3 .

Таким образом, Аня выиграет.

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

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

Таким образом, поскольку , побеждает первый игрок: ему достаточно каждый раз забирать такое число камней, чтобы общее число забранных камней было точным квадратом, и на своём ходе он возьмёт последний камень.

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

Игра конечна, следовательно, у одного из игроков есть выигрышная стратегия. Докажем, что у второго не может быть выигрышной стратегии. Предположим, что она у него есть, и будем играть за первого. Первым ходом выбросим кучку а вторую разделим на и Второй игрок обязательно выбросит кучку и разделит как-то кучку С этого момента у второго игрока есть ответные ходы на каждый наш ход, соответствующие выигрышной стратегии. Тогда можем начать игру по-другому: первым ходом выбросим кучку и разделим кучку так же, как и второй игрок разделил бы ее в соответствии со своей выигрышной стратегией. Теперь будем отвечать на ходы второго по его же стратегии и победим. Значит, у первого тоже есть выигрышная стратегия. Противоречие.

Доказали, что первый игрок имеет выигрышную стратегию.

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

Случай 1. Пусть .

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

Случай 2. Пусть .

Если текущее число на доске не равно -256 , Саша может поставить знак минус перед числом 512 и плюсы перед остальными знаками. Результат после вычислений будет равен -1 , поэтому число на доске останется на отрезке . Если же текущее число на доске равно - 256, Саша может поставить знак минус перед числом 256 и плюсы перед остальными знаками. Результат вычислений будет равен 511, поэтому следующее число на доске будет равно 255 за пределы отрезка Саша не вышел.

Теперь докажем, что Дима может добиться результата 256. Будем называть всегда . Если Саша ставит плюс перед числом 512 , результат вычислений будет равен +1 , и число на доске увеличится. Чтобы не допустить появления числа, превосходящего 255, Саше нужно в какой-то момент поставить знак плюс перед другим числом. В такой ситуации результат вычисления отрицательный и по модулю не меньше . Поэтому следующее число на доске не больше, чем , и Дима добился желаемого результата.

Приведем одну из возможных стратегий за Вову. Покрасим клетки доски в шахматном порядке так, чтобы угловые клетки были черными. В нечетных столбцах крайние клетки будут черными, а в четных белыми. Центральная клетка находится в 51-м столбце, поэтому она сама будет белой.

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

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

Для белых клеток ситуация несколько иная: две диагонали, проходящие через центральную клетку, симметричны относительно центрального столбца, но других симметричных белых диагоналей на доске нет. Опять же, перед ходом Паши ситуация на белых клетках осе-симметрична, то есть и на диагонали, выбираемой сейчас Пашей, и на диагонали, выбранной по стратегии Вовой, есть незачеркнутые клетки. Но единственная общая клетка, которую могут иметь осе-симметричные белые диагонали, зачеркнута с самого начала, поэтому Паша не может своим ходом зачеркнуть незачеркнутую клетку с Вовиной диагонали. Таким образом, Вова своим ходом зачеркнет хотя бы одну новую клетку.

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

Введем нумерацию горизонталей: пусть строка шахматной доски, на которой находится ферзь вначале будет -ой. Над горизонталью с ферзем - горизонтали, а под ней

Если король ушел из под шаха, то он находится либо на -ой, либо на -ой горизонтали.

Пусть первым ходом ферзь сходит на одну клетку вверх. Либо король попадет под шах, либо он был на горизонтали с номером а после своего хода может находиться только на -ой, -ой, или -ой строчке.

Назовем “шагом вправо” следующие два подряд хода ферзя: По диагонали вправо-вниз на три клетки; (после такого хода либо король попадает под шах, либо после своего хода может находиться только на -ой, -ой, или -ой строчке.) На три клетки вверх; (либо король попадает под шах, либо после своего хода находится только на -ой, -ой, или -ой строчке.)

Аналогично “шаг влево”: По диагонали влево-вниз на три клетки; На три клетки вверх;

Заметим, что когда ферзь делает “шаг влево” или “шаг вправо”, он сдвигается на клетки вправо или влево. Также король всегда должен находится на полосе из и -ой горизонтали, иначе попадет под шах. И также можно заметить, что за один “шаг” король будет атакован, если он находился между вертикалями начальной и конечной позиции “шага”. То есть задача сводится к тому, что нужно доказать, что ферзь сможет догнать короля “шагами влево и вправо”, если за один “шаг” ферзь перемещается на клетки по горизонтали, а король максимум на клетки по горизонтали.

Но это утверждение уже легко доказать: отправим мысленно в обе стороны две вспомогательные фигуры, перемещающиеся со скоростью клетки за “шаг”. Пусть ферзь догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит короля, а значит, и ферзь когда-то догонит короля, то есть король когда-то будет под шахом.

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

Занумеруем двери числами например, по часовой стрелке. Пусть он будет рассматривать двери с номерами для

Первой попыткой Иван Царевич проверяет двери и Если после этого он не сумел выйти из комнаты, то двери и были заперты. Дверь останется запертой даже после того, как Баба-Яга запрёт открытую и отопрёт одну из соседних.

Второй попыткой Иван Царевич проверяет двери и Если после этого он не сумел выйти из комнаты, то двери были заперты, а с учетом того, что тоже заперта, можно утверждать, что двери и останутся запертыми и после действий Бабы-Яги.

Пусть на шаге он открывает двери с номерами И пусть ему известно, что дверей с номерами точно были закрыты перед его ходом. Тогда после проверки дверей Иваном Царевичем и действий Бабы Яги мы будем знать, что дверей с номерами точно заперты, потому что перед ходом Бабы Яги были заперты соседние к ним двери.

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

(a) Пусть Дима загадал значение — , а Петя задаст вопросы следующего вида: «Верно ли, что загаданное число равно ?», где — какое-то число, — сумма чисел из предыдущих вопросов. По условию Дима увеличивал свое значение на число из вопроса Пети, если Петя не угадал, поэтому Петин вопрос вида: «Верно ли, что загаданное число равно ?» — по смыслу эквивалентен вопросу: «»

Переберем значения в следующем порядке:

То есть первые несколько вопросов выглядят так:
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»

Тогда Петя рано или поздно выберет значение равное изначально загаданному и, спросив «Верно ли, что загаданное число равно » угадает текущее число.

(b) Пусть Петя сначала задаст вопрос, который не изменит числа: «Верно ли, что загаданное число равно ?» Либо он угадает, либо сможет узнать знак загаданного числа. Без ограничения общности далее считаем, что загаданное число положительное, иначе задаем следующие вопросы с противоположным знаком. (И также будем считать - что если Петя угадал число в какой-то момент, то он автоматически выиграл.)

Теперь пусть Петя задает вопросы вида:
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
«Верно ли, что загаданное число равно ?»
…
«Верно ли, что загаданное число равно ?»

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

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

Перед последним вопросом загаданное число будет лежать в границах то есть после изменения на оно не превосходит по модулю числа

Пусть Петя задаст вопрос: «Верно ли, что загаданное число равно ?» И тем самым поймет знак загаданного числа в данный момент.

То есть теперь нам известны знак и границы, в которых лежит текущее загаданное число.

После этого, пока не угадаем число, будем задавать вопросы:
«Верно ли, что загаданное число равно ?», где — текущее максимальное по модулю значение для загаданного числа (может быть как положительным, так и отрицательным числом)
«Верно ли, что загаданное число равно ?»

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

Отправим мысленно в обе стороны дороги двух помощников, едущих со скоростью большей, чем скорость вора, но меньшей, чем скорость полицейской машины. Пусть полицейская машина догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит угонщика, а значит, и полицейский когда-то догонит угонщика.

Сначала покажем, что при емкости вёдер Кащей сможет добиться того, что ведро будет переполнено. Если то Кощею достаточно литр поместить в одно какое-то ведро.

Иначе пусть где и пусть ведра пронумерованы по кругу: соответственно. Тогда пусть Кощей наливает в первое ведро а в третье литров воды.

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

В случае же Василиса сможет не допустить победы Кащея. Пусть она будет действовать следующим образом: сначала опустошает ведро, потом ведро, потом потом потом и так далее по кругу. Тогда каждое ведро не опустошается не более, чем хода Кащея, то есть в каждом ведре может быть налито Кащеем за хода максимум литра, после чего оно опустошается. Значит, что ни одно из ведер не переполнится. И Василиса побеждает.

Разместим все карточки в квадрате как показано на рисунке (составляем так называемый магический квадрат). Заметим, что игрок выиграл тогда и только тогда, когда он первый забирает себе целый столбец, целую строку либо целую диагональ (сумма чисел на вертикалях, горизонталях и диагоналях магического квадрата постоянна, в нашем случае — ). Будем отмечать карточки, которые забирает -ый игрок крестиками, а карточки второго — ноликами. Наша игра свелась в игру в крестики-нолики. Но, как известно, при правильной игре в крестики-нолики, ни у кого нет выигрышной стратегии.

Докажем, что Сяо может расставить на ребрах двух кубов стрелочки так, чтобы вне зависимости от действий Бяо совпала ровно половина стрелочек. Сначала покажем построение на первом кубе. Выделим одну вершину на кубе – скажем, верхний правый угол на верхней грани. Расставим стрелки на ребрах так, чтобы они образовывали поток из этой вершины в диаметрально противоположную. Теперь рассмотрим второй куб. Выделим в нем ту же вершину, сделаем все ребра исходящими из нее. Для каждой из трех смежных с ней вершин сделаем все ребра входящими в нее. Для диаметрально противоположной вершины наоборот сделаем все ребра входящими в нее. Тогда для всех вершин, смежных с диаметрально противоположной, все ребра являются исходящими.

Отметим, что каждая вершина второго куба такова, что либо все ребра из нее исходят, либо все входят. Более того, если в некоторую вершину ребра входят, значит из каждой соседней вершины ребра выходят, и наоборот. Это значит, что результатом любого вращения второго куба может быть только один из двух вариантов расстановки стрелочек: исходный, и такой, который получается из исходного заменой всех стрелочек на противоположные. Первый вариант получается всегда, когда из верхнего правого угла верхней грани ребра исходят, а второй – когда наоборот входят. И нетрудно видеть, что для каждого варианта ровно из стрелочек совпадают с расстановкой на первом кубе.

Теперь докажем, что Бяо может всегда действовать так, чтобы после поворота второго кубика совпало хотя бы ребер. Выделим произвольное ребро на первом кубе. Отметим, что второй куб всегда можно повернуть так, чтобы направление на этом ребре у них совпало. Действительно, возможно, оно у них и так совпадает, и поворот не требуется. Иначе, выделим произвольную грань, которой принадлежит это ребро, и рассмотрим композицию поворота на относительно оси, перпендикулярной этой грани, и на относительно оси, параллельной этой грани. Первый поворот переводит ребро в противоположное на выбранной грани, а второй – наоборот, переводит противоположное ребро в исходное. В результате этих двух поворотов получилась расстановка стрелочек, в которой направление выбранного ребра поменялось. Это означает, что из всех способов поворота второго куба ровно у половины направление на выделенном ребре совпадает с направлением на первом кубе, и ровно у половины – нет. Действительно, композиция поворота на относительно оси, параллельной фиксированной грани, и поворота на относительно оси, перпендикулярной этой грани, является обратным преобразованием к композиции выше. Поэтому композиция поворотов выше является взаимно однозначным соответствием, и разбивает все повороты второго куба на пары, в каждой из которых у одного поворота направление на фиксированном ребре совпадает с первым кубом, а у другого – нет.

Рассмотрим всевозможные варианты расстановок стрелочек, полученные поворотом второго куба. Обозначим их количество как Просуммируем по всем ним количество совпадающих по направлению ребер с ребрами первого куба. По доказанному выше ясно, что получится число так как для каждого из ребер ровно половина из расстановок совпадает с первым кубом по направлению этого ребра. Тогда, по принципу Дирихле, существует расстановка, в которой с первым кубом совпадает по направлению хотя бы ребер. Бяо достаточно вернуть эту расстановку.

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

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

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

Играя за Сашу, поделим всю доску на квадратики затем введём шахматную раскраску на них. “Чёрные” квадратики будем красить “вертикально”, то есть на ход Пети закрашивать вторую клетку из вертикальной доминошки, в которую он попал. В “белых” будем действовать аналогично “горизонтально”. В итоге все квадратики будут иметь один из видов (заменим красный и синий цвета на крестики и нолики)

При этом первые два не могут быть рядом (будем звать их горизонтальными), как и (вертикальные), а можно получить в любом квадратике (диагональные). Нетрудно видеть, что при таких условиях из них можно сложить “полосу” не длиннее четырёх крестиков (ширины ). Для этого нужно взять горизонтальный, а затем добавить по бокам вертикальный и диагональный, либо наоборот. Если же рассматривать полосу ширины два, то она не может иметь длину больше двух. Действительно, либо она идёт прямо по квадратику и имеет длину не более одного, либо идёт между квадратиками, тогда хотя бы один из них не является вертикальным (считаем, что полоса ориентирована вертикально), откуда даже её общая часть с ними имеет длину не более единицы. В итоге максимальная длина такой полосы, если она находится на пересечении квадратиков, будет равна площадь — Полоса длины три или четыре (а шире их не бывает) имеет длину не более единицы, поскольку иначе бы существовал квадратик полностью из крестиков либо два горизонтальных/вертикальных были бы рядом. В результате такая стратегия приводит к максимальному выигрышу для Коли.

Чтобы добиться этого выигрыша, Коле нужно покрасить фигуру ниже (можно убедиться, что так сделать можно всегда, если Саша хочет избежать фигуры площади )

Где нолики стоят там, где они должны быть, чтобы фигура площади не получилась уже на следующем ходу. Далее Коля может воспользоваться неограниченной с двух сторон последовательностью из двух крестиков в центре — её нетрудно за два хода “вытянуть” до длины

Приведём стратегию Гели, когда Катя получит не более двух рублей. Выстроим прямоугольники в один большой прямоугольник будем красить с левого верхнего угла направо по стороне длины в черный цвет, а с правого нижнего налево вдоль стороны такой же длины — в белый (если строчка закончилась начнем снова так же красить следующую строчку). Тогда строчки длины будут одноцветным и одна, быть может, разноцветной: сначала сколько-то черных клеток, потом все белые. Отсюда видно, что получилось не более различных видов раскраски.

Чтобы добиться двух рублей, играя за Катю, достаточно раз сказать черный цвет и раз белый. Очевидно, что хотя бы два разноцветных прямоугольника мы так получим.

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

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

Заметим, что Вася может открыть не более одной коробки. Действительно, если Петей открывается коробка с чётным числом карандашей, то следующую коробку также придётся открывать Пете. Тогда Петя должен открыть хотя бы одну коробку с нечётным числом карандашей. Васе же достаточно ровно в этот момент открыть другую нечётную коробку — суммарно в них будет чётное число карандашей, поэтому следующую коробку также открывает Петя. Почему одну коробку Васе придётся открыть? Потому что Петя может начать игру с нечётной коробки, возьмёт из неё последний карандаш, поэтому Васе придётся открыть вторую. В итоге Вася откроет на три коробки меньше и выиграет рубля.