marathon:problem_140 [2012/11/09 09:34] 127.0.0.1 внешнее изменение |
marathon:problem_140 [2021/05/27 08:01] (текущий) letsko |
следовательно он сам тоже лжец. | следовательно он сам тоже лжец. |
| |
У каждого рыцаря рожно два соседа лжецы. При этом один лжец может соседствовать максимум четырем рыцарям. | У каждого рыцаря ровно два соседа лжецы. При этом один лжец может соседствовать максимум четырем рыцарям. |
Если бы это было верно для всех лжецов, доля рыцарей получилась бы 2/3. Но по краям площади стоят лжецы, | Если бы это было верно для всех лжецов, доля рыцарей получилась бы 2/3. Но по краям площади стоят лжецы, |
поэтому значение 2/3 не достижимо (хотя легко достигается на бесконечной площади). | поэтому значение 2/3 не достижимо (хотя легко достигается на бесконечной площади). |
Покажем, что доля рыцарей может превышать любое число, меньшее 2/3. | Покажем, что доля рыцарей может превышать любое число, меньшее 2/3. |
| |
Из многочисленных конфицураций, приводящих к решению, я воспользуюсь одной из предложенных Сергеем Половинкиным | Из многочисленных конфигураций, приводящих к решению, я воспользуюсь одной из предложенных Сергеем Половинкиным |
(она наиболее плотная из всех и достижение долей рыцарей достаточно близких к 2/3 не требует триллионных значений n). | (она наиболее плотная из всех и достижение долей рыцарей достаточно близких к 2/3 не требует триллионных значений n). |
Регулярный (повторяющийся) элемент заполения этой конфигурации можно увидеть на следующем рисунке: | Регулярный (повторяющийся) элемент заполнения этой конфигурации можно увидеть на следующем рисунке: |
| |
{{:marathon:mm140_new_5.jpg|:marathon:mm140_new_5.jpg}} | {{:marathon:mm140_new_5.jpg|:marathon:mm140_new_5.jpg}} |
Доля рыцарей на регулярном участке заполнения равна 29/48 ≈ 0.604. | Доля рыцарей на регулярном участке заполнения равна 29/48 ≈ 0.604. |
Ясно, что на краях и в слоях, близких к краям площади, плотность рыцарей меньше. Но с ростом n число клеток | Ясно, что на краях и в слоях, близких к краям площади, плотность рыцарей меньше. Но с ростом n число клеток |
в крайних слоях растет линейно, а число клеток во внутреннй области квадратично. Поэтому, используя приведенную | в крайних слоях растет линейно, а число клеток во внутренней области - квадратично. Поэтому, используя приведенную |
схему заполнения можно получить долю рыцарей, сколь угодно близкую к 29/48. | схему заполнения можно получить долю рыцарей, сколь угодно близкую к 29/48. |
| |
| |
Приведу еще несколько конфигураций, с помощью которых можно сколь угодно подойти к доле рыцарей в 2/3. | Приведу еще несколько конфигураций, с помощью которых можно сколь угодно подойти к доле рыцарей в 2/3. |
Заполение "цепями" ("гармошками") было предложено Дмитрием Пашуткиным и Сергеем Половинкиным (названия их же): | Заполнение "цепями" ("гармошками") было предложено Дмитрием Пашуткиным и Сергеем Половинкиным (названия их же): |
| |
{{:marathon:mm140_chains7.jpg|:marathon:mm140_chains7.jpg}} | {{:marathon:mm140_chains7.jpg|:marathon:mm140_chains7.jpg}} |
Гармошки легко сужаются при приближении к краям площади. | Гармошки легко сужаются при приближении к краям площади. |
| |
Красиво смотрится "круговая" конфигурация, предложеня Николаем Дерюгиным: | Красиво смотрится "круговая" конфигурация, предложенная Николаем Дерюгиным: |
| |
{{:marathon:mm140_circle_new.jpg|:marathon:mm140_circle_new.jpg}} | {{:marathon:mm140_circle_new.jpg|:marathon:mm140_circle_new.jpg}} |
//Разбор задачи ММ140 подготовил Владимир Лецко// | //Разбор задачи ММ140 подготовил Владимир Лецко// |
---- | ---- |
| Примечание: |
| |
| В 2018 году Luca Petrone нашел для n = 16 два заполнения с 92 рыцарями. Их можно увидеть в [[https://oeis.org/A289362|OEIS]]\\ |
| В июле 2020-го Paul Tabatabai улучшил и этот результат, а также нашел окончательные значения для n = 17 и n = 18: |
| https://cs.uwaterloo.ca/journals/JIS/VOL24/Tabatabai/taba4.html |
| |
| |