 |
|
 |
 |
 | Карта сайта |
 | Недавние изменения |
 | Поиск |
 | Вы посетили |
 | История страницы |
 | Вход |
Различия
Здесь показаны различия между двумя версиями данной страницы.
|
marathon:problem_140 [2012/11/09 09:34] 127.0.0.1 внешнее изменение |
marathon:problem_140 [2021/05/27 08:01] (текущий) letsko |
||
|---|---|---|---|
| Строка 21: | Строка 21: | ||
| следовательно он сам тоже лжец. | следовательно он сам тоже лжец. | ||
| - | У каждого рыцаря рожно два соседа лжецы. При этом один лжец может соседствовать максимум четырем рыцарям. | + | У каждого рыцаря ровно два соседа лжецы. При этом один лжец может соседствовать максимум четырем рыцарям. |
| Если бы это было верно для всех лжецов, доля рыцарей получилась бы 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}} | ||
| Строка 38: | Строка 38: | ||
| Доля рыцарей на регулярном участке заполнения равна 29/48 ≈ 0.604. | Доля рыцарей на регулярном участке заполнения равна 29/48 ≈ 0.604. | ||
| Ясно, что на краях и в слоях, близких к краям площади, плотность рыцарей меньше. Но с ростом n число клеток | Ясно, что на краях и в слоях, близких к краям площади, плотность рыцарей меньше. Но с ростом n число клеток | ||
| - | в крайних слоях растет линейно, а число клеток во внутреннй области квадратично. Поэтому, используя приведенную | + | в крайних слоях растет линейно, а число клеток во внутренней области - квадратично. Поэтому, используя приведенную |
| схему заполнения можно получить долю рыцарей, сколь угодно близкую к 29/48. | схему заполнения можно получить долю рыцарей, сколь угодно близкую к 29/48. | ||
| Строка 69: | Строка 69: | ||
| Приведу еще несколько конфигураций, с помощью которых можно сколь угодно подойти к доле рыцарей в 2/3. | Приведу еще несколько конфигураций, с помощью которых можно сколь угодно подойти к доле рыцарей в 2/3. | ||
| - | Заполение "цепями" ("гармошками") было предложено Дмитрием Пашуткиным и Сергеем Половинкиным (названия их же): | + | Заполнение "цепями" ("гармошками") было предложено Дмитрием Пашуткиным и Сергеем Половинкиным (названия их же): |
| {{:marathon:mm140_chains7.jpg|:marathon:mm140_chains7.jpg}} | {{:marathon:mm140_chains7.jpg|:marathon:mm140_chains7.jpg}} | ||
| Строка 75: | Строка 75: | ||
| Гармошки легко сужаются при приближении к краям площади. | Гармошки легко сужаются при приближении к краям площади. | ||
| - | Красиво смотрится "круговая" конфигурация, предложеня Николаем Дерюгиным: | + | Красиво смотрится "круговая" конфигурация, предложенная Николаем Дерюгиным: |
| {{:marathon:mm140_circle_new.jpg|:marathon:mm140_circle_new.jpg}} | {{:marathon:mm140_circle_new.jpg|:marathon:mm140_circle_new.jpg}} | ||
| Строка 123: | Строка 123: | ||
| //Разбор задачи ММ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 | ||
| + | |||