Цена игры

Очевидно, что Васе нужна стратегия, в которой он не более двух раз “проваливается”, то есть называет число, большее задуманного Петей (так как после третьего "провала"весь фонд уходит Пете). Сначала предложим стратегию, позволяющую Васе гарантированно получить указанное количество фунтиков, а потом докажем, что это максимальное количество, которое он может гарантировать.

Стратегия Васи с одним “провалом”: пусть (т.е. наименьшее натуральное , при котором ). Шаги до “провала”: Вася называет числа пока Петя не скажет, что для очередного (первый "провал") или что угадано число Сумма арифметической прогрессии а значит, такой момент обязательно наступит. Если это в момент первого "провала то в этот момент Петя получает из фонда фунтиков, в фонде остаётся фунтиков, а Вася приступает к выполнению шагов до "угадал".

Шаги до “угадал”: Вася называет (не более чем последовательные числа от до (которое меньше ) до тех пор, пока Петя не скажет, что задуманное число угадано, а Вася, сыграв раундов, получает из фонда фунтиков.

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

Назовём треть веса колбасы фунтом. Покажем, как Хасан может получить не менее фунтов. Сначала он делит колбасу на кусок 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 конфет Малыш не получит, иначе тогда Карлсон получит ровно конфету.

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

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

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

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

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

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

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

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

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

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

То есть

Иными словами, в интересующей нас клетке должно стоять число

Пользуясь этой формулой и значениями в клетках на краях, заполним всю табличку:

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

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

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

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

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

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

Играя за Петю, хочется каждый раз брать карточку с наибольшим числом. Однако Вася тоже может брать такие карточки и мешать нам. Поймем, что на первом ходе Петя может взять карточку с числом 10, на втором шаге — с числом хотя бы 8 (хотя бы одна карточка из трех наибольших еще осталась), на третьем — хотя бы 6, на четвертом — хотя бы 4, на пятом — хотя бы 2 (каждый раз берем наибольшую карточку из оставшихся). То есть мы доказали, что Петя всегда может набрать себе хотя бы .

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

Тем самым мы доказали, что Петя всегда может забрать себе 30, а Вася всегда может сделать так, чтобы больше 30 Петя не забрал. Следовательно, наш ответ — ровно 30.

Приведем стратегию, когда Петя может забрать себе все шашки.

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

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

Будем играть за Васю и стараться ходить симметрично Пете относительно центральной клетки. То есть после каждого хода Пети ставим нолик в симметричную клетку, если она свободна. Если симметричная клетка занята, то ставим в любую другую свободную.

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

Следовательно, и в конце игры доска будет симметричной относительно центральной клетки (в любых двух симметричных клетках будет нолик и крестик). То есть число строк, в которых больше ноликов, будет не больше чем на 1 меньше числа строк, в которых больше крестиков (так как только центральная строка не имеет своей противоположной симметричной пары). Аналогично со столбцами.

Значит, по такой стратегии .

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

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

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

Значит, Вася всегда может добиться наибольшего возможного количества — 400.

Всего 6 четных коробок и 5 нечетных.

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

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

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

Тем самым за всю игру мы открыли ровно 3 коробки.

Осталось показать, что у Васи есть стратегия, в которой Вася откроет не более 8 коробок.

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

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

Упорядочим получившиеся куски по увеличению веса. Из первого примера мы знаем, что Петя гарантированно может взять себе куски, вес которых будет хотя бы сумма весов 20-го, 18-го, …, 4-го и 2-го кусков, причем никакой больший вес Петя не сможет взять при правильной игре Васи. Тогда Васе в момент разрезания кусков нужно добиться того, чтобы перечисленные куски давали наименьшую возможную сумму весов. Сумма всех перечисленных кусков хотя бы половина от общей массы всего сыра. Следовательно, наименьшая возможная сумма — половина всей массы.

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

Тем самым, наибольшая сумма весов, которую может гарантированно получить Петя, — половина всей массы сыра.