Задача 264. Игра в «Заполнение доски»-XXVI
Есть 20 неокрашенных клетчатых прямоугольников 1×4. Андрей и Борис ходят по очереди, начинает Андрей. Каждым ходом Андрей выбирает цвет — черный или белый, — а Борис красит в этот цвет одну из еще не окрашенных клеток в любом из прямоугольников. Игра заканчивается, когда все прямоугольники полностью покрашены. Андрей получает от Бориса столько рублей, сколько сможет выбрать по-разному окрашенных прямоугольников. Какое наибольшее число рублей она может наверняка получить, как бы ни играл Борис?
Решение:
Приведём стратегию Бориса, когда Андрей получит не более двух рублей. Выстроим прямоугольники в один большой прямоугольник 4×20, будем красить с левого верхнего угла направо по стороне длины 20 в черный цвет, а с правого нижнего налево вдоль стороны такой же длины — в белый (если строчка закончилась начнем снова так же красить следующую строчку). Тогда 3 строчки длины 20 будут одноцветным и одна, быть может, разноцветной: сначала сколько-то черных клеток, потом все белые. Отсюда видно, что получилось не более 2 различных видов раскраски.
Чтобы добиться двух рублей, играя за Андрея, достаточно 1 раз сказать черный цвет и 79 раз белый. Очевидно, что, хотя бы два разноцветных прямоугольника мы так получим.
Ответ:
2.
Задача 265. Игра в «Заполнение доски»-XXVII
Андрей и Борис играют в игру, Андрей ходит первым. Они по очереди ставят фишки на клетчатую доску 7×8 (7 строк и 8 столбцов). Каждый раз, когда Борис ставит фишку, он получает 4 очка за каждую фишку, уже стоящую в той же строке и 3 очка за каждую фишку, уже стоящую в том же столбце.
На одной клетке может стоять только одна фишка. Игра заканчивается, когда все клетки доски заполнены.
Какое наибольшее количество очков может заработать Борис вне зависимости от действий Андрея?
Решение:
Давайте скажем, что Андрей тоже получает очки по тому же принципу, что и Борис. В таком случае, каждая пара клеток в одной строке даст в итоге какому-то из игроков 4 очка, а каждая пара клеток в одном столбце — 3 очка. В одной строке можно найти 8×7/2=28 пар клеток, а в одном столбце — 7×6/2=21 пару. Общая сумма очков, набранных обоими игроками в конце игры, будет равна
7×28×4+8×21×3=1288.
Приведём стратегию за Бориса, позволяющую ему каждый ход получать на 4 очка больше, чем перед этим Андрей. Для этого разобъём каждую строку на 4 прямоугольника 1×2. Как только Андрей ставит фишку в одну из клеток прямоугольника, Борис тут же занимает вторую. Столбцы, в которых находятся эти клетки, идентичны из-за стратегии Бориса, а в строке к моменту её хода находится на одну фишку больше — ровно на ту, которую поставил Андрей.
С другой стороны, если Андрей будет каждый раз выбирать клетку, которая приносит максимальное количество очков, Борис своим следующим ходом сможет набрать максимум на 4 очка больше, так как добавлением одной фишки Андрей повышает “ценность” каждой из оставшихся клеток не более, чем на 4.
Каждый игрок сделает 28 ходов и, при правильной игре, Борис наберёт на 112 очков больше. Зная сумму и разность двух чисел, можно легко найти сами числа, это 700 и 588.
Во всех остальных вариантах второй игрок всегда получает большее количество очков за фишку в ряду, длина которого чётна, поэтому описанная стратегия за второго игрока всегда работает.
Ответ:
700
Задача 266. Игра в «Крестики-нолики»-VII
Игра происходит на клетчатом поле 9×9. Андрей и Борис ходят по очереди, начинает Андрей. Он ставит в свободные клетки крестики, Борис — нолики. Когда все клетки заполнены, подсчитывается количество строк и столбцов, в которых крестиков больше, чем ноликов, — число k, и количество строк и столбцов, в которых ноликов больше, чем крестиков, — число n (всего строк и столбцов — 18). Какую наибольшую разность k-n может обеспечить Андрей, как бы ни играл Борис?
Решение:
Мы уже решали эту задачу симметричной стратегией для Андрея, то есть оценку на k-n≥2 мы уже получили (так как по этой стратегии у Андрея больше столбцов, чем у Бориса, и строк). Приведем стратегию для Бориса, которая обеспечивает k-n≤2.
Будем играть за Бориса и стараться ходить симметрично Андрея относительно центральной клетки. То есть после каждого хода Андрея ставим нолик в симметричную клетку, если она свободна. Если симметричная клетка занята, то ставим в любую другую свободную.
Таким образом в любой момент времени после хода Бориса будет верен следующий инвариант: для каждого крестика Андрея (кроме центрального) будет пара — симметричный ему нолик, и еще может быть будут нолики без пары. Инвариант всегда выполняется, так как он выполняется в самом начале игры (до первых ходов) и, если он выполнялся на данном шаге, то будет выполняться и на следующем (благодаря нашей стратегии).
Следовательно, и в конце игры доска будет симметричной относительно центральной клетки (в любых двух симметричных клетках будет нолик и крестик). То есть число строк, в которых больше ноликов, будет не больше чем на 1 меньше числа строк, в которых больше крестиков (так как только центральная строка не имеет своей противоположной симметричной пары). Аналогично со столбцами.
Значит, по такой стратегии k-n≤2.
Ответ: 2
Задача 267. Игра в «Заполнение доски»-XXVIII
Андрей и Борис играют в игру на клетчатой доске 100×100. Андрей начинает и своим ходом красит одну клетку в красный цвет, а Борис — в синий. Ходят по очереди, перекрашивать ранее закрашенные клетки нельзя. В конце игры Андрей ищет красный клетчатый прямоугольник наибольшей площади, и Борис платит ему столько рублей, сколько в этом прямоугольнике клеток. Какой наибольший заработок может гарантировать себе Андрей, как бы ни играл Борис?
Решение:
Играя за Бориса, поделим всю доску на квадратики 2×2, затем введём шахматную раскраску на них. “Чёрные” квадратики будем красить “вертикально”, то есть на ход Андрея закрашивать вторую клетку из вертикальной доминошки, в которую он попал. В “белых” будем действовать аналогично “горизонтально”. В итоге все квадратики будут иметь один из видов (заменим красный и синий цвета на крестики и нолики)
При этом первые два не могут быть рядом (будем звать их горизонтальными), как и 3,4 (вертикальные), а 5,6 можно получить в любом квадратике (диагональные). Нетрудно видеть, что при таких условиях из них можно сложить “полосу” не длиннее четырёх крестиков (ширины 1). Для этого нужно взять горизонтальный, а затем добавить по бокам вертикальный и диагональный, либо наоборот. Если же рассматривать полосу ширины два, то она не может иметь длину больше двух. Действительно, либо она идёт прямо по квадратику и имеет длину не более одного, либо идёт между квадратиками, тогда хотя бы один из них не является вертикальным (считаем, что полоса ориентирована вертикально), откуда даже её общая часть с ними имеет длину не более единицы. В итоге максимальная длина такой полосы, если она находится на пересечении 4 квадратиков, будет равна 2, площадь — 4. Полоса длины три или четыре (а шире их не бывает) имеет длину не более единицы, поскольку иначе бы существовал квадратик полностью из крестиков либо два горизонтальных/вертикальных были бы рядом. В результате такая стратегия приводит к максимальному выигрышу 4 для Андрея.
Чтобы добиться этого выигрыша, Андрею нужно покрасить фигуру ниже (можно убедиться, что так сделать можно всегда, если Борис хочет избежать фигуры площади 4)
где нолики стоят там, где они должны быть, чтобы фигура площади 4 не получилась уже на следующем ходу. Далее Андрей может воспользоваться неограниченной с двух сторон последовательностью из двух крестиков в центре — её нетрудно за два хода “вытянуть” до длины 4.
Ответ:
4
Задача 268. Цена игры-I
Андрей и Борис играют в кости на деньги. Ведущий игру Андрей выигрывает, если при бросании им двух игральных кубиков сумма выпавших на них очков не превосходит 4 и проигрывает во всех остальных случаях. Проиграв, Андрей отдаёт Борису 1 рубль, выиграв — получает от Бориса k рублей. Игра считается справедливой, если среднее значение выигрыша каждым игроком равна нулю. Найти значение k, при котором игра будет справедливой.
Решение:
Заметим, что Андрей выигрывает с вероятностью p=1/6 (подходят исходы (1;1), (1;2), (2,1), (1,3), (3,1), (2,2) — их 6 из 36). Справедливая цена игра означает, что Андрей имеет нулевой средний выигрыш, то есть:
P×k+(1-p) ×(-1)=0
k=(1-p)/p=5
Ответ:
5
Задача 269. Игра в «Распределение»-IV
По кругу стоит 101 блюдце, на каждом по конфете. Сначала Андрей выбирает натуральное m<101, затем Борис — натуральное k<101. Андрей берет конфету с любого блюдца. Отсчитав от этого блюдца k-е блюдце по часовой стрелке, берет с него конфету Борис. Отсчитав уже от этого блюдца m-е блюдце по часовой стрелке, берет с него конфету Малыш (если она там еще есть). Отсчитав от блюдца Малыша k-е блюдце по часовой стрелке, берет с него конфету Борис (если она там еще есть), и т.д. Какое наибольшее число конфет может себе гарантировать Борис, как бы ни играл Андрей?
Решение:
Стратегия Бориса будет взять число k=101-2m, если m<51, и k=202-2m, если m≥51. Можно считать, что Борис отсчитывает 2m в сторону против часовой стрелки. Пронумеруем блюдца с помощью их остатков по модулю 101 против часовой стрелки, то есть 0, 1, …, 100, начиная с первого выбранного Андреем. Тогда Андрей получит блюдца 0, m, 2m…, при этом Борис получает номера 2m, 3m, 4m,… то есть забирает у Андрея все блюдца, кроме первых двух. Остаётся заметить, что 101 — простое число, поэтому в последовательности Андрея 0, m,…,100m и, Бориса 2m, 3m,…, 102m все тарелки будут различны. Отсюда Борис получит все тарелки, кроме двух, то есть 99. Нетрудно убедиться, что меньше 2 конфет Андрей не получит, иначе k+m=101, тогда Борис получит ровно 1 конфету.
Ответ:
99
Задача 270. Вероятности-I
На столе лежит колода игральных карт 36 листов. Два опытных игрока Андрей и Борис (каждый из них всегда делает правильный ход) начинают игру по следующим правилам. В начале игры каждый из игроков совершенно случайно называет одну из цифр от 1 до 3. Их сумма определяет (на всю игру) максимальное число карт, которые при очередном ходе игроки могут забрать со стола. Игрок не может при своем ходе не взять со стола карту. Выигрывает тот из игроков, кто сможет забрать последнюю карту в колоде. Начинает всегда Андрей. Какая вероятность победы Бориса?
Решение:
Введем событие А - выигрывает Борис. Количество упорядоченных случайных пар (m, n), где m=1,2,3, n=1,2,3 равно девяти. Случайная величина m+n принимает значения от 2 до 6 c вероятностями:
Рассмотрим пять гипотез.
Гипотеза H1: m+n=2, P(H1)=1/9. Если игрок при своем ходе сможет оставить на столе число карт кратное трем, то ему обеспечен выигрыш. В противном, это сможет сделать соперник и обеспечить свой выигрыш. При первом ходе Андрей этого сделать не может, следовательно, P(A/H1)=1.
Гипотеза H2: m+n=3, P(H2)=2/9. Если игрок при своем ходе сможет оставить на столе число карт кратное четырем, то ему обеспечен выигрьш. В противном, это сможет сделать соперник и обеспечить свой выигрыш. При первом ходе Андрей этого сделать не может, следовательно, P(A/H2)=1.
Гипотеза H3: m+n=4, P(H3)=3/9. Если игрок при своем ходе сможет оставить на столе число карт кратное пяти, то ему обеспечен выигрыш. В противном, это сможет сделать соперник и обеспечить свой выигрыш. При первом ходе Андрей этого сделать может, забрав со стола одну карту, следовательно, P(A/H3)=0.
Гипотеза H4: m+n=5, P(H4)=2/9. Если игрок при своем ходе сможет оставить на столе число карт кратное шести, то ему обеспечен выигрыш. В противном, это сможет сделать соперник и обеспечить свой выигрыш. При первом ходе Андрей этого сделать не может, следовательно, P(A/H4)=1.
Гипотеза H5: m+n=6, P(H5)=1/9. Если игрок при своем ходе сможет оставить на столе число карт кратное семи, то ему обеспечен выигрыш. В противном, это сможет сделать соперник и обеспечить свой выигрыш. При первом ходе Андрей этого сделать может, забрав со стола одну карту, следовательно, P(A/H5)=0.
Наконец, складываем эти вероятности: 5/9.
Ответ:
5/9
Задача 271. Цена игры-II
У Андрея есть 10 карточек с числами 1, 2, 4, 8, 16,…, 512. Он пишет на доске число 0 и предлагает Борису сыграть в игру. Борис своим ходом называет целое число 0<p<10, это число может быть разным от раунда к раунду. Андрей выбирает p карточек, перед которыми ставит знак «+», а перед остальными карточками ставит знак «-». Результат вычисляется и прибавляется к числу на доске. Какой наибольший по модулю результат через несколько раундов может получить Борис, как бы ни действовал Андрей?
Решение:
Сначала докажем, что Андрей может всегда получать результат из отрезка (-256; +256). Будем считать, что текущее число на доске неположительно (в противном случае можно заменить все знаки в рассуждениях на противоположные). Разберем два случая для числа p, называемым Борисом на очередном раунде.
Случай 1. Пусть 1≤p≤8.
Тогда поставим знаки так: +512-256-128, а остальные знаки расставим произвольным образом. Так как 512>1+2+…+256=511, результат будет положительным, и число на доске не станет меньше -256. С другой стороны 512-256-128+64+32+16+8+4+2+1=255, значит, число на доске не станет больше 255.
Случай 2. Пусть p=9.
Если текущее число на доске не равно -256, Андрей может поставить знак минус перед числом 512 и плюсы перед остальными знаками. Результат после вычислений будет равен +1, поэтому число на доске останется на отрезке (-256; +256). Если же текущее число на доске равно -256, Саша может поставить знак минус перед числом 256 и плюсы перед остальными знаками. Результат вычислений будет равен 511, поэтому следующее число на доске будет равно 255 за пределы отрезка Андрей не вышел.
Теперь докажем, что Борис может добиться результата 256. Будем называть всегда p=1. Если Андрей ставит плюс перед числом 512, результат вычислений будет равен +1 и число на доске увеличится. Чтобы не допустить появления числа, превосходящего 255, Андрею нужно в какой-то момент поставить знак плюс перед другим числом. В такой ситуации результат вычисления отрицательный и по модулю не меньше 511. Поэтому следующее число на доске не больше, чем 255-511=-256, и Борис добился желаемого результата.
Ответ:
256
Задача 272. Цена игры-III
Андрей и Борис играют в следующую игру. Андрей в каждую клетку таблицы 8 × 8 записывает число от 1 до 64, используя каждое по одному разу. После этого Борис выбирает одну из клеток и ставит на эту клетку ладью. Затем он выбирает вторую клетку, на которую можно переместиться одним ходом ладьи из первой клетки, и перемещает ладью на эту клетку. Далее он выбирает третью клетку, на которую можно переместиться одним ходом ладьи из второй клетки, и перемещает ладью на эту клетку. Выбирать ранее посещённые клетки запрещено. После этого Борис складывает все три числа, записанных в клетках, на которых стояла ладья. Какую максимальную сумму гарантированно может получить Борис независимо от того, каким способом Андрей заполнит таблицу? (Ладья может перемещаться на любое количество клеток по горизонтали или вертикали.)
Решение:
Лемма. а) На доске 8×8 выбраны 11 произвольных клеток. Тогда среди них можно найти три клетки такие, что от одной из них можно двумя ходами ладьи обойти вторую и третью клетки.
б) На доске, суммарное числом столбцов и строк в которой не более 11, выбраны 8 клеток. Тогда среди них можно найти три клетки такие, что от одной их них можно двумя ходами ладьи обойти вторую и третью клетки.
Доказательство леммы. Если в столбце/строке выбрана одна клетка, будем называть её одиночной, а если две — будем называть каждую из двух клеток парной. Будем говорить, что клетка занимает строку/столбец, если она стоит в этой строке/столбце. Заметим, что никакие другие клетки не могут быть выбраны в столбце/строке, где стоит одиночная или парная клетки. Тогда каждая пара клеток занимает суммарно 3 строки и столбца, а каждая одиночная — 1 строку и 1 столбец.
a) Обозначим число одиночных клеток за х, а число парных клеток — за 2y. Если лемма не выполняется, то нельзя 11 клетками занять более 8 строк и 8 столбцов, то есть 16 в сумме. Тогда имеем систему
x+2y=11
2x+3y≤16
Но 2x+3y=1.5 (x+2y)+0.5x=16.5 +0.5x>16 — противоречие. Следовательно, предположение неверно и пункт а) леммы доказан.
б) Аналогично пункту а) леммы обозначим число одиночных клеток за x, а число парных клеток за — 2y. Если лемма не выполняется, то нельзя 8 клетками занять более 11 строк и столбцов в сумме. Тогда имеем систему
x+2y=8
2x+3y≤11
Но 2x+3y=1.5 (x+2y)+0.5x=12+0.5x>11 — противоречие. Следовательно, предположение неверно и пункт б) леммы доказан.
Рассмотрим 11 клеток с числами от 54 до 64. Из пункта а) леммы следует, что какие-то три из них второй игрок может обойти, придерживаясь условий задачи. Минимальная сумма трёх из этих чисел равна 54+55+56=165, значит второй игрок всегда может получить сумму не менее 165. Предположим, что сумму больше 165 не всегда удастся получить. Тогда никакие три из клеток с числами от 54 до 64 помимо 54, 55, 56 не должны оказаться в одной строке/столбце или образовывать "угол".
При этом числа 54, 55, 56 обязаны оказаться в одной строке/столбце или образовывать "угол иначе найдётся другая тройка чисел с большей суммой. Если эти числа располагаются в одной строке/столбце, или образуют "угол то занимают суммарно 4 строки и столбца. Без ограничения общности, пусть эти числа стоят так, как показано ниже, ведь если поменять какие-то строки/столбцы местами, искомая сумма не изменится.
И в том, и в другом случае оставшиеся 8 клеток с числами от 57 до 64 располагаются в выделенном прямоугольнике, количество строк и столбцов в которых суммарно равно 12. Если эти 8 клеток занимают не все строки или столбцы, то они занимают суммарно не более 11 строк и столбцов. Тогда из пункта б) леммы следует, что какие-то три числа стоят в одной строке/столбце или образуют “угол”, а значит, выбрав эти три клетки, мы увеличим искомую сумму. Если эти 8 клеток, среди которых x одиночных и 2y парных клеток, занимают все строки и столбцы, то имеем систему
x+2y=8
2x+3y=12
откуда x=0, y=4. Следовательно, все клетки в выделенном прямоугольнике парные. Тогда найдётся число не менее 52 (на второй таблице число 53 может дополнять серые клетки до квадрата), которое стоит в одной строке или в одном столбце с какой-то парной клеткой из выделенного прямоугольника. Взяв это число и две парные клетки, получим сумму не менее 52+57+58=167. Значит, примера, гарантирующего сумму 165, но не гарантирующего сумму 166, не существует.
Пример, гарантирующий сумму 166, но не гарантирующий сумму 167:
Здесь сумма 166 достигается, например, на числах 54, 55, 57. Все остальные суммы в пределах правого нижнего прямоугольника 4×6 не превосходят 166. Максимальная сумма в пределах правого нижнего прямоугольника 4x6 не будет превосходить 166, так как 60+59+46=165. Оставшиеся числа можно ставить в любые из оставшихся клеток, так как максимальная ещё не рассмотренная сумма будет равна 34+63+36=163.
Ответ:
166