Высшая проба 2024, 8 класс, задача 6
( баллов) Дана таблица с строками и десятью столбцами, Петя и Вася по очереди ставят в клетки таблицы крестики и нолики. За ход Петя ставит два крестика (или, если осталось одно незаполненное поле, то крестик), а Вася ставит один нолик. Начинает Петя. Игра заканчивается, когда все клетки таблицы заполнены. Если есть строка, заполненная только крестиками, побеждает Петя, иначе Вася. Для какого минимального Петя может гарантировать себе победу?
Если в таблице хотя бы строк, побеждает Петя. Действительно, он может сначала в каждую строку поставить по крестику — это ходов, Вася за ходов поставит по нолику не более чем в из этих строк. Дальше Петя выбирает строк, которые пока не содержат ноликов и ставит в них по второму крестику — хода, Вася «испортит» не более строк. И так далее до получения Петей двух строк с крестиками. Вася «испортит» из них не больше одной, и Петя сможет поставить крестика в другую.
Теперь докажем, что при меньшем числе строк Вася может гарантировать себе победу. Пусть Вася ставит нолик в ту же строку, что и Петя, если тот поставил два крестика в одну строку. В ином случае Вася ставит нолик в одну из строк с наибольшим числом крестиков среди тех, в которых ещё нет ноликов. Если ни одно из этих действий невозможно, Вася может ставить нолик на любое свободное место.
Пусть победил Петя. Забудем про все ходы, на которых все символы были поставлены в одну строку, и соответствующие им строки — в таких строках есть хотя бы по одному нолику, значит, ни в одной из них Петя не сможет поставить крестиков. Тогда за ход до победы у Пети была строка хотя бы с крестиками и без . Если Вася не поставил туда , была ещё хотя бы одна строка хотя бы с крестиками. Они могли получиться только если строк с крестиками было не меньше : если в двух строках хотя бы с крестиками не стоят , то было ещё хотя бы две строки, в которых не меньше крестиков, и в которые Вася поставил нолики.
Аналогичным образом доказываем, что строк с крестиками должно было быть хотя бы , с — , с — $25
:— приведена стратегия для Пети для 256 строк и доказано, что она приведёт к успеху.
:— стратегия на 512 или 1024, потому что не учтено, что в конце в одну строку можно поставить два крестика.
:—оценка(доказательство,чтоВасяпобедит,еслисторонаменьше256). Всероссийская олимпиада школьнико4в «Высшая проба» 2024 год, 2 этап 4.