Лжецы среди соседей (по мотивам УрТЮМа)

[Ktina]

а) В посёлке Малые Сардаанки натуральное число домов. Некоторые дома соединены проводами. Соседями называются двое, дома которых связаны проводом.

Доказать, что всегда удастся поселить в каждый дом по одному человеку: лжецу или рыцарю — так, чтобы каждый на вопрос: «Есть ли среди ваших соседей лжецы?» ответил положительно. (Каждый знает про каждого из своих соседей, лжец он или рыцарь).

б) В посёлке Большие Сардаанки счётное число домов. Некоторые дома соединены проводами. Соседями называются двое, дома которых связаны проводом.

Всегда ли удастся поселить в каждый дом по одному человеку: лжецу или рыцарю — так, чтобы каждый на вопрос: «Есть ли среди ваших соседей лжецы?» ответил положительно? (Каждый знает про каждого из своих соседей, лжец он или рыцарь).

в) В посёлке Чудовищных Размеров Сардаанки континуум домов...
Тот же вопрос.

[12d3]

а) селим везде рыцарей. Если у рыцаря все соседи рыцари, меняем его на лжеца, повторять до победного. Количество домов конечно, поэтому победный когда-нибудь настанет.

-- Пт дек 26, 2014 19:09:49 --

Б) то же самое, только сначала рыцарей перенумеруем, а потом будем применять к ним операцию замены на лжеца в порядке нумерования. За конечное число шагов можно точно узнать, кто будет жить в конкретном доме.

[Red_Herring]

12d3 в сообщении #952638 писал(а):

а) селим везде рыцарей. Если у рыцаря все соседи рыцари, меняем его на лжеца, повторять до победного. Количество домов конечно, поэтому победный когда-нибудь настанет.

И если при Вашем "победном" у какого-нибудь лжеца есть сосед-лжецы?

[Evgenjy]

а) Элементарно по индукции. $n=1$, селим лжеца. Количество домов $n+1$, временно отсоединяем один дом, в остальные расселяем согласно условию, что возможно по предположению индукции. Если $n+1$-й дом соединен только с рыцарями, селим туда лжеца. Если соединен хотя бы с одним лжецом, селим туда рыцаря.

А вот б) и в) $-$ это сложнее. Трансфинитная индукция здесь, по-моему, не проходит. Возможно есть контрпример.

[12d3]

Red_Herring в сообщении #952653 писал(а):

И если при Вашем "победном" у лжеца все соседи лжецы?

При проведении такой процедуры не могут образоваться два соседа - лжеца. А рыцари без соседей-лжецов когда-нибудь кончатся.

[Evgenjy]

12d3 в сообщении #952638 писал(а):

а) селим везде рыцарей. Если у рыцаря все соседи рыцари, меняем его на лжеца, повторять до победного. Количество домов конечно, поэтому победный когда-нибудь настанет.

По-моему правильное решение и луче, чем по индукции, поскольку применимо и к б):

12d3 в сообщении #952638 писал(а):

Б) то же самое, только сначала рыцарей перенумеруем, а потом будем применять к ним операцию замены на лжеца в порядке нумерования.

12d3 в сообщении #952638 писал(а):

За конечное число шагов

Видимо Вы имели в виду: "За счетное"?

[12d3]

Evgenjy в сообщении #952739 писал(а):

Видимо Вы имели в виду: "За счетное"?

Если мы возьмем какой-то конкретный дом, мы за конечное число шагов узнаем, кто в нем живет. Чтоб узнать, кто живет во всех домах, нужно, конечно, счетное число шагов.
Насчет пункта "в", сильно подозреваю, что есть контрпример, но что-то он пока не придумался.

[grizzly]

12d3 в сообщении #952777 писал(а):

Насчет пункта "в", сильно подозреваю, что есть контрпример

А чем такое же доказательство не подходит? Ну аксиома выбора понадобится для трансфинитной индукции. Сразу же приведём этот пгт.ЧРС в какой-нибудь вполне порядок. А потом по индукции: если для всех предыдущих домиков процедуру (замены рыцаря на лжеца при необходимости) применили и для них всё стало нормально, то после применения процедуры в следующем домике для всех домиков, включая новый, всё нормально.

[Ktina]

Вот решение пункта а), предложенное руководителем кружка для 6-го класса:

Дмитрий Александрович Коробицын писал(а):

Рассмотрим наибольшее подмножество $A$ домов, никакие два из которых не являются соседними. Поселим в каждый дом множества $A$ лжеца, а во все остальные — по рыцарю. Тогда заметим, что у каждого рыцаря есть сосед-лжец, иначе бы дом этого рыцаря можно было бы добавить в множество $A$. По построению ни у какого лжеца нет соседей-лжецов.

Ссылка на это решение:
http://mmmf.msu.ru/vecher/circles/z6/10.html
(задача №8 (последняя))

[Evgenjy]

Ktina в сообщении #952911 писал(а):

Вот решение пункта а), предложенное руководителем кружка для 6-го класса:

Дмитрий Александрович Коробицын
писал(а):
Рассмотрим наибольшее подмножество $A$ домов, никакие два из которых не являются соседними. Поселим в каждый дом множества $A$ лжеца, а во все остальные — по рыцарю. Тогда заметим, что у каждого рыцаря есть сосед-лжец, иначе бы дом этого рыцаря можно было бы добавить в множество $A$. По построению ни у какого лжеца нет соседей-лжецов.

Думаю, что не так все просто. Следует доказать, что такое множество существует (и не пусто). Для конечного случая доказательство существования думаю проходит, хотя применить напрямую метод 12d3 и проще и эффективнее. А для случаев задач б) и в), у меня большие сомнения. Тем более, что для задачи б) опять же лучше метод 12d3.

[Red_Herring]

Evgenjy в сообщении #952963 писал(а):

Думаю, что не так все просто.

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

[grizzly]

Evgenjy в сообщении #952963 писал(а):

опять же лучше метод 12d3.

Ну хотя бы теперь нужно было заметить о, пусть небольшом, формальном и легко устранимом, но всё-таки недостатке этого метода. Часть процедуры "все соседи рыцари" нужно было заменить на "нет соседей лжецов" (до и далее по тексту). Это ведь не одно и то же.

[Evgenjy]

Red_Herring в сообщении #952967 писал(а):

данном доказательстве речь идет о наибольшем в том смысле, что оно не содержится ни в каком другом множестве обладающим

Это , конечно, так. Главное, что этот метод требует доказательство существования. И еще, если уж быть совсем точным, к чему призывает grizzly, правда по другому поводу, то следует в начале доказательства писать: "Рассмотрим одно из наибольших подмножеств",- поскольку их может быть несколько. Впрочем проблем с а) нет, решена и задача б).
По поводу задачи в). Теперь я думаю, что grizzly прав, и метод 12d3 можно применить и к континууму, используя трансфинитную рекурсию.

grizzly в сообщении #952969 писал(а):

"все соседи рыцари" нужно было заменить на "нет соседей лжецов"

Согласен.

[Red_Herring]

grizzly в сообщении #952969 писал(а):

"все соседи рыцари" нужно было заменить на "нет соседей лжецов"

А какая разница? Заметим, что отрицанием "все соседи—рыцари" является "есть сосед-лжец". Если у человека вообще нет соседей, то разумеется, у него "все соседи—рыцари" (ну, и "все соседи—лжецы").

[grizzly]

Red_Herring в сообщении #952986 писал(а):

Если у человека вообще нет соседей, то разумеется, у него "все соседи—рыцари" (ну, и "все соседи—лжецы").

Допустим, разумеется. Я же не говорю, что допущена грубая ошибка. Если бы я полагал, что авторское решение основано на таком рассуждении, я не счёл бы его красивым. Но я ведь счёл :)