Игры

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

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

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

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

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

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

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

Заметим, что пока не все клетки покрыты, у первого всегда есть ход. Клеток всего а после ходов второго их количество кратно Значит, у первого всегда будет ход и он победит. В качестве стратегии будем ходить в первую попавшуюся клетку.

Нужно показать, что Аня всегда может добиться, чтобы разноцветных пар было не меньше 50, а Боря сможет помешать ей добиться, чтобы таких пар было больше 50.

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

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

Всего в круге имеется 100 пар соседних точек, и каждый игрок делает по 50 ходов. В итоге Боря добьётся того, что хотя бы 50 пар будут одноцветными, а Аня — что хотя бы 49 пар будут разноцветными. Однако количество разноцветных пар всегда чётно. Действительно, после окончания игры пройдём полный круг, начиная с какой-либо отмеченной точки (пусть для определённости с красной). Группы из идущих подряд красных и синих точек будут чередоваться: К—С—К—С—…—К, и значит, встретим пар разноцветных соседей вида К—С столько же, сколько пар вида С—К. Поэтому если пар разноцветных соседних точек не меньше 49, то их хотя бы 50.

Пусть в процессе было ходов.

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

количество клубней у (любого) мальчика перед первым ходом.

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

Поскольку все числа целые, получаем, что

при всех

Теперь можно получить оценки на числа действуя «с конца». Определим числа условиями

Докажем, что и индукцией по При неравенства очевидны; для перехода, чтобы доказать неравенство при некотором достаточно заметить, что

Итак, мы получаем, что Приведём таблицу первых значений чисел

Значит, из условия получаем, что

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

клубней, а перед любым предыдущим его ходом у него будет клубней при причём

Значит, этот ход удовлетворяет условию, и дети могут сделать 19 таких ходов.

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

Тогда отрезки и образуют треугольник: в сумме и как половина больше а неравенства и верны в силу равенства и

Назовём треть веса колбасы фунтом. Покажем, как Хасан может получить не менее фунтов. Сначала он делит колбасу на кусок A в фунт и кусок B в фунта. Если Жасан разделит B, то получатся части весом больше фунта и меньше фунта, поэтому Жасан достанется кусок A в фунт, а Хасану — остальное. Если же Жасан разделит кусок A, то кусок B останется самым большим и достанется Хасану, то есть Хасан получит даже больше фунтов. Покажем, как Жасан обеспечит себе не менее фунта. Когда Хасан разрежет колбасу на два куска, Жасан посмотрит, есть ли среди них кусок в фунт. Если есть, то он режет другой кусок на две части. Если нет, то Жасан от большего куска отрезает фунт. В обоих случаях получаться три куска: меньше фунта, ровно фунт и больше фунта, и Жасану достанется фунт.

Лемма. а) На доске выбраны 11 произвольных клеток. Тогда среди них можно найти три клетки такие, что от одной из них можно двумя ходами ладьи обойти вторую и третью клетки.

б) На доске, суммарное числом столбцов и строк в которой не более 11, выбраны 8 клеток. Тогда среди них можно найти три клетки такие, что от одной их них можно двумя ходами ладьи обойти вторую и третью клетки.

Доказательство леммы. Если в столбце/строке выбрана одна клетка, будем называть её одиночной, а если две — будем называть каждую из двух клеток парной. Будем говорить, что клетка занимает строку/столбец, если она стоит в этой строке/столбце. Заметим, что никакие другие клетки не могут быть выбраны в столбце/строке, где стоит одиночная или парная клетки. Тогда каждая пара клеток занимает суммарно 3 строки и столбца, а каждая одиночная — 1 строку и 1 столбец.

a) Обозначим число одиночных клеток за а число парных клеток — за Если лемма не выполняется, то нельзя 11 клетками занять более 8 строк и 8 столбцов, то есть 16 в сумме. Тогда имеем систему

Но — противоречие. Следовательно, предположение неверно и пункт а) леммы доказан.

б) Аналогично пункту а) леммы обозначим число одиночных клеток за а число парных клеток за — Если лемма не выполняется, то нельзя 8 клетками занять более 11 строк и столбцов в сумме. Тогда имеем систему

Но — противоречие. Следовательно, предположение неверно и пункт б) леммы доказан.

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим 11 клеток с числами от 54 до 64. Из пункта а) леммы следует, что какие-то три из них второй игрок может обойти, придерживаясь условий задачи. Минимальная сумма трёх из этих чисел равна

значит второй игрок всегда может получить сумму не менее 165 . Предположим, что сумму больше 165 не всегда удастся получить. Тогда никакие три из клеток с числами от 54 до 64 помимо 54, 55, 56 не должны оказаться в одной строке/столбце или образовывать "угол".

При этом числа 54, 55, 56 обязаны оказаться в одной строке/столбце или образовывать "угол иначе найдётся другая тройка чисел с большей суммой. Если эти числа располагаются в одной строке/столбце, или образуют "угол то занимают суммарно 4 строки и столбца. Без ограничения общности, пусть эти числа стоят так, как показано ниже, ведь если поменять какие-то строки/столбцы местами, искомая сумма не изменится.

И в том, и в другом случае оставшиеся 8 клеток с числами от 57 до 64 располагаются в выделенном прямоугольнике, количество строк и столбцов в которых суммарно равно 12. Если эти 8 клеток занимают не все строки или столбцы, то они занимают суммарно не более 11 строк и столбцов. Тогда из пункта б) леммы следует, что какие-то три числа стоят в одной строке/столбце или образуют “угол”, а значит, выбрав эти три клетки, мы увеличим искомую сумму. Если эти 8 клеток, среди которых одиночных и парных клеток, занимают все строки и столбцы, то имеем систему

откуда Следовательно, все клетки в выделенном прямоугольнике парные. Тогда найдётся число не менее 52 (на второй таблице число 53 может дополнять серые клетки до квадрата), которое стоит в одной строке или в одном столбце с какой-то парной клеткой из выделенного прямоугольника. Взяв это число и две парные клетки, получим сумму не менее Значит, примера, гарантирующего сумму 165, но не гарантирующего сумму 166, не существует.

Пример, гарантирующий сумму 166, но не гарантирующий сумму 167:

Здесь сумма 166 достигается, например, на числах 54, 55, 57. Все остальные суммы в пределах правого нижнего прямоугольника не превосходят 166. Максимальная сумма в пределах правого нижнего прямоугольника не будет превосходить 166, так как Оставшиеся числа можно ставить в любые из оставшихся клеток, так как максимальная ещё не рассмотренная сумма будет равна

Пронумеруем столбцы слева направо, и строчки сверху вниз. Будем обозначать через клетку на пересечении -ого столбца и -ой строчки. Играем за первого игрока. Сначала сходим в клетку . Теперь, если второй игрок не сходит в клетку , то мы сможем сходить в одну из клеток или и тем самым заблокировать для второго игрока клетку . Тогда далее будем играть произвольно, не ходя в клетку . Если мы в какой-то момент не можем сделать ход, то и второй игрок не может сделать хода. Тогда нам достаточно сходить в клетку . Значит, первым своим ходом второй игрок ходит в . Тогда сходим далее в клетку . Легко видеть, что мы создали себе «запас» в виде клетки , в которую мы сможем сходить на любом ходе (второй игрок не может ее заблокировать). То есть снова будем ходить произвольно, пока можем. Если когда-нибудь не сможем, то сходим в и у второго не будет хода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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