======= 140 ========Задача ММ140 навеяна
вот этой.
ММ140 (10 баллов)
На квадратной площади, разлинованной на
![$n \times n$ $n \times n$](https://dxdy-04.korotkov.co.uk/f/3/a/d/3add1221abfa79cb14021bc2dacd572582.png)
клеток (полей) собрались
![$n^2$ $n^2$](https://dxdy-01.korotkov.co.uk/f/0/2/1/021273d50c6ff03efebda428e9e42d7782.png)
человек, каждый из которых является либо рыцарем (всегда говорят правду), либо лжецом (всегда лгут). Каждый расположился на отдельном поле. После этого каждый произнес: "Среди моих соседей поровну рыцарей и лжецов". Какова наибольшая возможная доля рыцарей среди собравшихся?
Примечания:
![$n>1$ $n>1$](https://dxdy-04.korotkov.co.uk/f/3/5/8/358039a361da9e2940dba6fc766af1c482.png)
;
Соседними считаются поля, имеющие общую сторону;
Каждый из собравшихся знает, кем являются его соседи.
===============РешениеСразу заметим, что в крайних линиях (горизонталях и вертикалях) могут стоять только лжецы: если поле не угловое, то у него нечетное число соседей; оба соседа человека, занимающего угловое поле лжецы, следовательно он сам тоже лжец.
У каждого рыцаря ровно два соседа лжецы. При этом один лжец может соседствовать максимум четырем рыцарям. Если бы это было верно для всех лжецов, доля рыцарей получилась бы
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
. Но по краям площади стоят лжецы, поэтому значение
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
не достижимо (хотя легко достигается на бесконечной площади).
Покажем, что доля рыцарей может превышать любое число, меньшее
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
.
Из многочисленных конфигураций, приводящих к решению, я воспользуюсь одной из предложенных Сергеем Половинкиным (она наиболее плотная из всех и достижение долей рыцарей достаточно близких к
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
не требует триллионных значений
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
).
Регулярный (повторяющийся) элемент заполнения этой конфигурации можно увидеть на следующем рисунке:
![Изображение](http://img-fotki.yandex.ru/get/5505/val-etc.7/0_4c156_8f123795_XL.jpg)
А вот как можно выйти на такое заполнение, если стартовать с краев площади:
![Изображение](http://img-fotki.yandex.ru/get/5904/val-etc.7/0_4c155_eddeac71_XL.jpg)
Доля рыцарей на регулярном участке заполнения равна
![$\frac{29}{48}\approx 0.604$ $\frac{29}{48}\approx 0.604$](https://dxdy-02.korotkov.co.uk/f/d/c/c/dcc01f489a004adfa8f979a3444d674a82.png)
.
Ясно, что на краях и в слоях, близких к краям площади, плотность рыцарей меньше. Но с ростом n число клеток в крайних слоях растет линейно, а число клеток во внутренней области квадратично. Поэтому, используя приведенную схему заполнения можно получить долю рыцарей, сколь угодно близкую к
![$\frac{29}{48}$ $\frac{29}{48}$](https://dxdy-01.korotkov.co.uk/f/4/c/9/4c94d24c169b72e6e90a89be0965843282.png)
.
Но нас интересует не
![$\frac{29}{48}$ $\frac{29}{48}$](https://dxdy-01.korotkov.co.uk/f/4/c/9/4c94d24c169b72e6e90a89be0965843282.png)
, а
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
! Поэтому увеличим сторону квадрата, составляющего регулярный участок заполнения внутренней области.
На следующем рисунке представлен участок заполнения, на котором хорошо видны такие квадраты.
![Изображение](http://img-fotki.yandex.ru/get/4702/val-etc.7/0_4c15b_f887fce4_XL.jpg)
А вот как будет выглядеть четвертинка (остальные четверти можно получить зеркальными отражениями) площади 327х327, заполненной подобным образом.
![Изображение](http://img-fotki.yandex.ru/get/5208/val-etc.7/0_4c154_ced12225_XL.jpg)
Доля рыцарей на регулярном участке уже
![$\frac{31}{49}\approx 0.633$ $\frac{31}{49}\approx 0.633$](https://dxdy-01.korotkov.co.uk/f/c/6/1/c61d4ea0302e04016bfbc767803e3f5982.png)
. Теперь, увеличивая
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
, можно сколь угодно приблизиться к
![$\frac{31}{49}$ $\frac{31}{49}$](https://dxdy-02.korotkov.co.uk/f/1/f/c/1fce840a34ea342a327959bb85b0064c82.png)
.
В частности, для площади 327х327 превышает
![$0.6$ $0.6$](https://dxdy-04.korotkov.co.uk/f/3/0/5/3055682176965f287303ba5e62b6b83682.png)
(327 - это наименьшее n, для которого мне это удалось).
Доля рыцарей на регулярном квадратном участке меньше
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
, за счет "лагун" из лжецов в узлах решетки, образующейся при регулярном заполнении площади, а также на границах, разделяющих квадратные участки. Но размер лагун, не меняется при увеличении размеров регулярного участка заполнения. А размер сторон линейно зависит от сторон повторяющегося квадрата заполнения, в то время как число клеток этого квадрата растет квадратично :)
Поэтому для любого числа
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
, меньшего
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
, можно подобрать размер регулярного участка заполнения, при котором доля рыцарей на регулярном участке превысит
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
, а затем, увеличивая
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
и повторяя регулярный участок должное число раз, превысить
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
уже на всей площади.
ОбсуждениеНекоторые участники привели аккуратные выкладки, показывающие, что (недостижимая) верхняя грань доли рыцарей равна
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
.
Я не стал этого делать, посчитав приведенное выше рассуждения более прозрачными и, в то же время, достаточно строгими.
Приведу еще несколько конфигураций, с помощью которых можно сколь угодно подойти к доле рыцарей в
![$\frac23$ $\frac23$](https://dxdy-02.korotkov.co.uk/f/1/3/4/134f84da790c6725c0c1a3bf987a048682.png)
.
Заполнение "цепями" ("гармошками") было предложено Дмитрием Пашуткиным и Сергеем Половинкиным (названия их же):
![Изображение](http://img-fotki.yandex.ru/get/5303/val-etc.7/0_4bfe5_c6f766c_XL.jpg)
Гармошки легко сужаются при приближении к краям площади.
Красиво смотрится "круговая" конфигурация, предложенная Николаем Дерюгиным:
![Изображение](http://img-fotki.yandex.ru/get/5903/val-etc.7/0_4c159_b8fd1f79_XL.jpg)
Круговое заполнение можно сочетать с крестообразным:
![Изображение](http://img-fotki.yandex.ru/get/5208/val-etc.7/0_4bfe8_b4317a4e_L.jpg)
Наконец, сразу несколько участников предложили ромбовидные конфигурации:
![Изображение](http://img-fotki.yandex.ru/get/5302/val-etc.7/0_4c158_906a1a38_XL.jpg)
На последней картинке явственно просматриваются модные нынче мотивы самоподобия.
Сергей Половинкин попытался найти максимально возможное количество рыцарей для малых значений
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
. Мне довольно быстро удалось улучшить его результаты для большинства рассматриваемых
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
. Получилось так:
Очень может быть, что и эти значения не окончательны.
Участники, которые до подведения итогов тура успеют прислать улучшения, могут рассчитывать на дополнительные призовые баллы. (Улучшения для
![$n=4$ $n=4$](https://dxdy-02.korotkov.co.uk/f/1/8/0/180bde3f581b83f9e0205ff90404a62d82.png)
и
![$n=5$ $n=5$](https://dxdy-02.korotkov.co.uk/f/1/5/2/1527cca23083db7049d5be6e93eb2b9382.png)
оцениваются в 100 призовых баллов
![Very Happy :D](./images/smilies/icon_biggrin.gif)
)
НаградыЗа правильное, строго обоснованное решение задачи ММ140 Сергей Половинкин и Дмитрий Пашуткин получают по 12 призовых баллов.
Николай Дерюгин (он нашел необходимые конфигурации, но ошибся при оценивании доли рыцарей) получает 7 призовых баллов.
Анатолий Казмерчук и Алексей Волошин получают по 6 призовых баллов, А Евгений Гужавин - 5 баллов.
Эстетическая оценка задачи 4.6 баллаРазбор задачи ММ140 подготовил Владимир Лецко