Решение задачи MM140 IV открытой интернет-олимпиады по математике: XIV тура Математического марафона

главная страница сайта Приглашение в мир математики

======= 140 ========

Задача ММ140 навеяна вот этой.

ММ140 (10 баллов)

На квадратной площади, разлинованной на $n \times n$ клеток (полей) собрались $n^2$ человек, каждый из которых является либо рыцарем (всегда говорят правду), либо лжецом (всегда лгут). Каждый расположился на отдельном поле. После этого каждый произнес: "Среди моих соседей поровну рыцарей и лжецов". Какова наибольшая возможная доля рыцарей среди собравшихся?
Примечания:
$n>1$ ;
Соседними считаются поля, имеющие общую сторону;
Каждый из собравшихся знает, кем являются его соседи.

===============

Решение

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

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

Из многочисленных конфигураций, приводящих к решению, я воспользуюсь одной из предложенных Сергеем Половинкиным (она наиболее плотная из всех и достижение долей рыцарей достаточно близких к $\frac23$ не требует триллионных значений $n$ ).
Регулярный (повторяющийся) элемент заполнения этой конфигурации можно увидеть на следующем рисунке:

А вот как можно выйти на такое заполнение, если стартовать с краев площади:

Доля рыцарей на регулярном участке заполнения равна $\frac{29}{48}\approx 0.604$ .
Ясно, что на краях и в слоях, близких к краям площади, плотность рыцарей меньше. Но с ростом n число клеток в крайних слоях растет линейно, а число клеток во внутренней области квадратично. Поэтому, используя приведенную схему заполнения можно получить долю рыцарей, сколь угодно близкую к $\frac{29}{48}$ .

Но нас интересует не $\frac{29}{48}$ , а $\frac23$ ! Поэтому увеличим сторону квадрата, составляющего регулярный участок заполнения внутренней области.
На следующем рисунке представлен участок заполнения, на котором хорошо видны такие квадраты.

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

Доля рыцарей на регулярном участке уже $\frac{31}{49}\approx 0.633$ . Теперь, увеличивая $n$ , можно сколь угодно приблизиться к $\frac{31}{49}$ .
В частности, для площади 327х327 превышает $0.6$ (327 - это наименьшее n, для которого мне это удалось).

Доля рыцарей на регулярном квадратном участке меньше $\frac23$ , за счет "лагун" из лжецов в узлах решетки, образующейся при регулярном заполнении площади, а также на границах, разделяющих квадратные участки. Но размер лагун, не меняется при увеличении размеров регулярного участка заполнения. А размер сторон линейно зависит от сторон повторяющегося квадрата заполнения, в то время как число клеток этого квадрата растет квадратично :)
Поэтому для любого числа $a$ , меньшего $\frac23$ , можно подобрать размер регулярного участка заполнения, при котором доля рыцарей на регулярном участке превысит $a$ , а затем, увеличивая $n$ и повторяя регулярный участок должное число раз, превысить $a$ уже на всей площади. Обсуждение

Некоторые участники привели аккуратные выкладки, показывающие, что (недостижимая) верхняя грань доли рыцарей равна $\frac23$ .
Я не стал этого делать, посчитав приведенное выше рассуждения более прозрачными и, в то же время, достаточно строгими.

Приведу еще несколько конфигураций, с помощью которых можно сколь угодно подойти к доле рыцарей в $\frac23$ .
Заполнение "цепями" ("гармошками") было предложено Дмитрием Пашуткиным и Сергеем Половинкиным (названия их же):

Гармошки легко сужаются при приближении к краям площади.

Красиво смотрится "круговая" конфигурация, предложенная Николаем Дерюгиным:

Круговое заполнение можно сочетать с крестообразным:

Наконец, сразу несколько участников предложили ромбовидные конфигурации:

На последней картинке явственно просматриваются модные нынче мотивы самоподобия.

Сергей Половинкин попытался найти максимально возможное количество рыцарей для малых значений $n$ . Мне довольно быстро удалось улучшить его результаты для большинства рассматриваемых $n$ . Получилось так:
$\begin{tabular}{|l|l|} \hline n& k \\ \hline 4 & 4 \\ \hline 5 & 8 \\ \hline 6 & 10 \\ \hline 7 & 10 \\ \hline 8 & 16 \\ \hline 9 & 28 \\ \hline 10 & 32 \\ \hline 11 & 36 \\ \hline 12 & 44 \\ \hline 13 & 56 \\ \hline 14 & 66 \\ \hline 15 & 88 \\ \hline \end{tabular}$
Очень может быть, что и эти значения не окончательны.
Участники, которые до подведения итогов тура успеют прислать улучшения, могут рассчитывать на дополнительные призовые баллы. (Улучшения для $n=4$ и $n=5$ оцениваются в 100 призовых баллов

)

Награды

За правильное, строго обоснованное решение задачи ММ140 Сергей Половинкин и Дмитрий Пашуткин получают по 12 призовых баллов.
Николай Дерюгин (он нашел необходимые конфигурации, но ошибся при оценивании доли рыцарей) получает 7 призовых баллов.
Анатолий Казмерчук и Алексей Волошин получают по 6 призовых баллов, А Евгений Гужавин - 5 баллов.

Эстетическая оценка задачи 4.6 балла

Разбор задачи ММ140 подготовил Владимир Лецко

Задайте вопрос на блоге о математике

Четвёртая открытая интернет-олимпиада по математике

Решение задачи ММ140