ВсОШ 2024, 11 класс, задача 3
Юрий подошёл к великой таблице майя. В таблице столбцов и строк. Юрий знает, что в каждой клетке таблицы изображено солнце или луна, и любые две строки отличаются (хотя бы в одном столбце). Каждая клетка таблицы закрыта листом. Поднялся ветер и сдул некоторые листы: по два листа с каждой строки. Могло ли так случиться, что теперь Юрий хотя бы про строк может узнать, что в каждой из них изображено в каждом из столбцов? (И. Богданов, К. Кноп)
Ответ. Могло.
Решение. Заметим, что существует всего различных строк длины , в которых каждый символ - солнце или луна; значит, каждая такая строка встречается в таблице ровно один раз. Разобьём все позиции на две половины по столбцов - "левую" и "правую". Предположим, что в каждой строке, в которой есть два солнца в одной половине (назовём их солнечными), ветер сдул листья с одной из таких пар солнц, а в каждой несолнечной строке - таких строк ровно - ветер обнаружил положения всех солнц (в несолнечной строке не более двух солнц, так что ветер мог так поступить). Тогда Юрий сообразит, что те строки, где открыты два солнца в одной половине - точно солнечные, а значит, несолнечные строки - это в точности те строк, в которых ветер не открывал два солнца в одной половине. У каждой из них открыты все солнца, так что закрытые листьями изображения в этих строках - луна.
Замечание. Существуют и принципиально другие конструкции, также позволяющие определить строк. Приведём одну из них.
Скажем, что строка монолитная, если все солнца в ней стоят подряд (строка из одних лун также монолитна). Монолитную строку назовём сбалансированной, если хотя бы один из двух средних символов - солнце, либо если солнц нет вообще. Сбалансированных строк ровно . Любая несбалансированная строка содержит либо солнце, стоящее слева от луны в левой половине, либо луну, стоящую слева от солнца в правой; сбалансированная же строка таких пар не содержит. Пусть ветер откроет именно такую пару символов в каждой несбалансированной строке; тогда Юрий узнает множество всех сбалансированных строк. Далее, в каждой сбалансированной строке, содержащей хотя бы два солнца, ветер откроет самое левое и самое правое из них; можно показать, что тогда все эти строки также однозначно определятся. Наконец, в оставшихся трёх сбалансированных строках ветер откроет два средних символа, позволяя определить и эти строки.