Задача о придворных.

покзалось, что довольно просто

нечетное


формально докзать за 6 минут пока идет билд не получилось. но попробовал разные варианты на простых случаях 2,3 и на всякий случай 4 и убедился, что для четных не работает, а для 3 легко придумать.

Выделить для просмотра:
На мой взгляд, придворных нечетное количество. Допустим, их трое. Тогда первый следит за третьим, который следит за вторым, который следит за первым. Для любого нечетного N связи выстраиваются следующим образом:
пусть h = (N div 2). Тогда (for i=0;i<h;i++) i-тый придворный следит за (i+h+1)-ым придворным. И (for i=N-1;i>=h;i--) i-ый придворный следит за (i-h)-ым придворным.
Если туплю, простите

мне кажется... (начало ответа -> при такой постановке вопроса у короля бесконечное количество придворных) либо сам король следит хотя бы за одним из них.
Вообщем должен быть человек, за которым никто не следит, или который сам не следит ни за кем. <- конец ответа)

Нечетное. Первый, тот за кем следит первый - он же тот кто следит за вторым, и второй. Трое - это минимум. Дальше можно вставлять их только по два в цепочку, получая каждый раз нечетное число.

"первый придворный из списка следит за тем, кто следит за вторым"
Я еще не проснулся до конца, или первый придворный следит сам за собой (как и второй и т.д.)?

Ответ - нечётное. Причём любое нечётное больше трёх подходит, любое чётное - не подходит.
Основная идея док-ва: Несложно доказать, что первый придворный обязан следить за придворным с номером (n+2)/2, где n - общее количество придворных. Полное доказательство приводить не буду. Если есть желание услышать - дайте знать :)

Видимо я что-то не понял... но вроде бы и чётное и ничётное проходят...
Вот пример:


1      2      3      4      5      Кто

?1     ?2    ?3     ?4    ?5    За кем следит
3      4      5      1      2

?5     ?1    ?2    ?3    ?4    Кто за ним следит
2      3      4      5       1




1      2      3      4      5      6      Кто

?1     ?2    ?3    ?4    ?5    ?6     За кем следит
3      4      5      6      1      2

?6     ?1    ?2    ?3    ?4    ?5     Кто за ним следит
2      3      4      5      6      1



Поправьте, если не прав...

Сори, невнимательно посмотрел на решение...

Моя теория про четное количество:
Римскими цифрами буду обозначать придворных, арабскими - те кто следят за придворными, т.е. общее количество придворных будет 2*(количество римских или арабских цифр)
Возьмем пример из 10 придворных:
I->1->II->2->III->3->IX->4->X->5->I
Т.е. I следит за тем кто следить за вторым, 1 следит за вторым, II следит за тем кто следит за третьим, 2 следит за третьим и т.д. X следит за тем кто следит за первым, 5 следит за первым, таким образом число придворных 10 - четное количество :)

Общее доказательство:

Пусть всего придворных n и 1 -> k (-> - следит), тогда:
k -> 2
k-1 -> 1
n -> k-1
k-2 -> n
n-1 -> k-2
k-3 -> n-1
И т.д. тоесть всегда k-x -> n-x+2
Тогда (k -(k-2) = 2) -> (n-(k-2)+2 = n-k), в тоже время 2 -> k+1, поскольку k->2 (см. начало), отсюда:
n-k = k+1
n = 2k+1 - нечётное

если я был советником индийского короля Али-Паши VII ,представил бы так.

Может быть только нечётное количество придворных. Тегов на вставку картинки не нашёл, так что помещаю просто ссылку на решение. А и ещё, чётным число не может быть, так как иначе переход через единицы не пойдёт.

http://www.ljplus.ru/img4/w/_/w_ounce/4h…

Если я был советником индийского короля Али-Паши VII ,представил бы так.(с)

их четверо
их трое

Ответ: Нечетное

Графическое решение

Не могу больше скрывать:)

Частные случаи для 3, 5 и 7:


Интерпретация (символ "

Т. к. в любом случае каждый следит за каждым то можно нарисовать следующее кольцо:

*-*-*-*-*
/ \
* *
\ /
*-*-*-*-*

Направление слежки - по часовой стрелке. Нумеруем произвольный как №1 и....

Для четного (2n) кол-ва получаем что

*-2-*-4-*
/ \
1 ....
\ /
2n-*-*-*-*

Для любого n последний (его номер 2n) будет следить за первым, что не есть хорошо.

Добавляем ещё одного:

*-2-*-4-*-6
/ \
1 ....
\ \
(2n)-(2n+1)-(2n-1)-*-*

Теперь всё сходится.

Иллюстрации к моим рассуждениям лучше смотреть тут:

http://www.picamatic.com/show/2008/05/01/03/197721_201x181.GIF
http://www.picamatic.com/show/2008/05/01/03/197722_201x181.GIF
http://www.picamatic.com/show/2008/05/01/03/197725_201x181.GIF
http://www.picamatic.com/show/2008/05/01/03/197729_201x181.GIF

Вроде бы так никто и не сказал, почему не может быть чётное количество придворных. Мой ответ.

1*. "Цепочки слежки" образуют кольца.
Доказательство. Возьмём любого a1. Он следит за a2, тот за a3 и т.д. Цепочка когда-то должна замкнуться. Если aJ=aK, 1 a2 -> ... -> aN. Выясняем номера остальных: a3=2, a5=3, a7=4... В случае нечётного N всё отлично получается, а в случае чётного - нарываемся на противоречие a1 = N/2+1.

Может, есть красивое доказательство наподобие тех, которые мы встречаем в книгах по функанализу или топологии... я придумать пока не могу.

Sorry, заглючил механизм тэгования на Хабре. Восстанавливаю по памяти.

Вроде бы так никто и не сказал, почему не может быть чётное количество придворных. Мой ответ.

Обозначим "a следит за b" как "a -> b"

1*. "Цепочки слежки" образуют кольца.
Доказательство. Возьмём любого a1. Раскручиваем цепочку: a1 -> a2 -> a3 ->... Цепочка когда-то должна замкнуться. Если aJ=aK (1<J<K), то за этим aJ=aK следят сразу двое: a(J-1) и a(K-1). Противоречие.

2* Кольцо всего одно.
Пусть это не так. Находим каких-то a и a+1 в разных кольцах. Тогда должен быть такой b, что a -> b -> a+1. Естественно, такого быть не может.

3*. Grand finale. Количество придворных нечётно.
Записываем наше кольцо: a1=1 -> a2 -> ... -> aN -> a1=1. Выясняем номера остальных: a3=2, a5=3, a7=4... В случае нечётного N всё отлично получается, а в случае чётного - нарываемся на противоречие a1 = N/2+1.

Может, есть красивое доказательство наподобие тех, которые мы встречаем в книгах по функанализу или топологии... я придумать пока не могу.

Предлагаю хардкорным математикам, в число которых я, к сожалению, не вхожу, довести следующий эскиз до ума.

Переформулирем задачу. Найти все такие n, при которох для всех 0<=iПредлагаю хардкорным математикам, в число которых я, к сожалению, не вхожу, довести следующий эскиз до ума.

Переформулирем задачу. Найти все такие n, при которох для всех 0<=iПредлагаю хардкорным математикам, в число которых я, к сожалению, не вхожу, довести следующий эскиз до ума.

Переформулирем задачу. Найти все такие n, при которох для всех 0<=iПредлагаю хардкорным математикам, в число которых я, к сожалению, не вхожу, довести следующий эскиз до ума.

Переформулирем задачу. Найти все такие n, при которох для всех 0<=i<n существует такая функция f, что f(f(i))===i+1 mod n.

Очевидно, что f(i)===i+1/2 mod n. Однако число 2 обратимо по модулю n только в случае нечетного n.

Попробовал решить графически дугами. Для троих получилось, для четверых никак :)
Нечётно. Дальше получаются звёзды и цветы.

нечетное. Ведь для того, чтобы иметь замкнутый круг достаточно всего 2 человека, которые следят друг за другом.
Друг-математик сидит за спиной и неуверенно пожимает плечами, зачем усложнять то, что заведомо просто в решении?

Придворных всего трое (знаю, такой вариант тут уже закритиковали, но всё же, у мен аргументы).

В условии не сказано, кто следит за первым, однако там сказано, что за ним кто-то следит. Единственными исключениями из правилс лежения являются последний и предпоследний. Значит, мы не можем выбрать произвольного придворного и назначить его следить за первым. Следящий за первым предворный должен быть где-то в условиях. А потому возможное решение только такое:

1 » 3
2 » 1
3 » 2

Итак, первый следит за тем кто следит за вторым. За вторым следит третий, так что тут правильно

Второй следит за тем, кто следит за третьим. За третьим следит первый, и соответственно 2 следит за первым.

Также предпоследний (второй) следит за тем, кто следит последним, т.е. за первым.

Последний следит за тем, кто следит за первым, т.е. за вторым. Сходятся все условия.

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

Большая часть ответов это не более чем рассмотрение частных случаев. Что никак не может считаться решением. Если я знаю что верен один из двух ответов (чет-нечет), то понятно что можно взять три - убедиться что условие выполняется и дать ответ. Тут особо и заморачиваться не надо.

Но по-хорошему необходимо доказать две вещи:

1) при всех четных условие не выполняется
2) при всех четных - выполняется

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

Перевод задачи на математический язык.

При каких n существует перестановка p \in S_n (группа перестановок из n элементов), такая что p^2 = (1 2 ... n) (перестановка, состоящая из одного цикла длины n)?

Решение.
Считаем, что n>=2 (для n=1 задача тривиальна). Пусть q = (1 2 ... n). Очевидно, что q^n=1 и q^k != e, если k \in [1,n-1] (через e обозначена тождественная перестановка). Наше уравнение на p приобретает вид p^2 = q.

Т.к. степени перестановки q действуют на множестве {1,2,...,n} транзитивно, то и степени перестановки p тоже действуют на этом множестве транзитивно. Следовательно, перестановка q состоит из одного цикла длины n.

Предположим, что n нечетно. Тогда p = q^((n+1)/2) и p^2 = q^(2*(n+1)/2) = q^(n+1) = q. Явный вид для p = (1 1+n1 1+2*n1 ...), где n1=(n+1)/2.

Рассмотрим случай четного n. Тогда q^(n/2) = p^(2*n/2) = p^n = e и n/2 \in [1,n-1]. Противоречие.

Ответ: для нечетных положительных n.

Обобщение: условие "первый придворный из списка следит за тем, кто следит за тем, кто следит за вторым придворным из списка" записываеся уравнением p^3 = q. И вообще: решить уравение p^b=q, где q = (1 2 .. n). Решение существует для b взаимно простых с n.

вот мой вариант геометрического решения (стрелочка от того кто следит)

внешений круг поворачивается на 180 градусов:)

Мне кажется строгое математическое решение должно выглядеть примерно так.

У нас фактически есть множество натуральных чисел от 1 до n, где n - кол-во придворных. Более того, это множество представляет из себя последовательность, т. к. каждый придворный следит за каждым. Будем понимать что А "следит за" B означает что в этой последовательности число B следует за А. Тогда получим, что наша последовательность имеет вид:

1, x1, 2, x2, .... n, m

Дело в том что исходя из условия, последний придворный (номер n) должен следить за первым, т. е. находиться на предпоследнем месте. Ну а послдений элемент последовательности обозначим как m - про него мы пока что ничего не знаем. Зато, исходя из условия задачи можем переписать последовательность вот так:

1, m+1, 2, m+2, ... n, m

Наша последовательность состоит из двух последовательностей (точней сказать подпоследовательностей):

1, 2, ....
m+1, m+2, ...

Теперь неплохо было бы выяснить в какой из двух псоледовательностей находится число n. Оно не может находится в первой последовательности, т. к. в этом случае получим что вся последовательность выглядит примерно так:
1, m+1, 2, m+2, ... m+n-1, n, m.

В этом случае m+n-1 никак не может быть равен m-1, хотя исходя из условия задачи - должен.
Вывод: элемент с номером n должен находиться во второй подпоследователньости. А последним элементом первой последловательности яляется тот, что стоит перед n. Обозначим его как k:

1, m+1, 2, m+2, ... k, n, m.

Но тогда получается что n = m + k:

1, m+1, 2, m+2, ... k, m + k, m

И ОБЩЕЕ ЧИСЛО ТАКИХ ЭЛЕМЕНТОВ РАВНО 2K+1 ЧТО И ЕСТЬ ДОКАЗАТЕЛЬСТВО!

Нарисовал частный случай на бумаге, получилось четное.
Это конечно не четкое доказательство, но по картинке судя по другому быть не может.