Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ140

Задача ММ140 навеяна вот этой: http://e-science.ru/forum/index.php?showtopic=26362

Конкурсная задача ММ140 (10 баллов)

На квадратной площади, разлинованной на nxn клеток (полей) собрались n2 человек, каждый из которых является либо рыцарем (всегда говорят правду), либо лжецом (всегда лгут). Каждый расположился на отдельном поле. После этого каждый произнес: «Среди моих соседей поровну рыцарей и лжецов». Какова наибольшая возможная доля рыцарей среди собравшихся?

Примечания:
n>1;
Соседними считаются поля, имеющие общую сторону;
Каждый из собравшихся знает, кем являются его соседи.

Решение

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

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

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

:marathon:mm140_new_5.jpg

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

:marathon:mm140_new_4.jpg

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

Но нас интересует не 29/48, а 2/3. Поэтому увеличим сторону крадрата, составляющего регулярный участок заполнения внутренней области. На следующем рисунке представлен участок заполнения, на котором хорошо видны такие квадраты.

:marathon:mm140_new_2.jpg

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

:marathon:mm140_new_3.jpg

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

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

Обсуждение

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

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

:marathon:mm140_chains7.jpg

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

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

:marathon:mm140_circle_new.jpg

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

:marathon:mm140_cross.jpg

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

:marathon:mm140_new_7.jpg

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

Ниже приведена составленная совместными усилиями участников сводная таблица наибольших возможных количеств рыцарей (k) для малых значений n.

n k
4 4
5 8
6 10
7 10
8 16
9 28
10 32
11 40
12 46
13 58
14 68
15 88
16 88

Очень может быть, что и эти значения не окончательны. (Улучшения для n=4 и n=5 оцениваются в 100 призовых баллов :D)

Награды

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

Дополнительные баллы за улучшения в вышеприведенной таблице:
Сергей Половинкин - 4
Алексей Волошин - 2
Евгений Гужавин - 1.

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

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


Примечание:

В 2018 году Luca Petrone нашел для n = 16 два заполнения с 92 рыцарями. Их можно увидеть в OEIS
В июле 2020-го Paul Tabatabai улучшил и этот результат, а также нашел окончательные значения для n = 17 и n = 18: https://cs.uwaterloo.ca/journals/JIS/VOL24/Tabatabai/taba4.html

 

 


Страница: [[marathon:problem_140]]

marathon/problem_140.txt · Последние изменения: 2021/05/27 08:01 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006