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

[el_ave]

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

нечетное


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

[dio77]

Выделить для просмотра:
На мой взгляд, придворных нечетное количество. Допустим, их трое. Тогда первый следит за третьим, который следит за вторым, который следит за первым. Для любого нечетного 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)-ым придворным.
Если туплю, простите

[Alien]

Солидарен с вами.

[Kapun]

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

[dio77]

А мой пример про трех придворных вас не устраивает?

[Kapun]

ну вот как вариант их (либо трое, либо бесконечность)

[dio77]

Ну почитайте мой ответ вверху, там написано, как выстроить связи для 5,7,9 и т.д.

[Plazik]

Раз король составил список придворных, то количество придворных явно не бесконечно :)

[Plazik]

Мой ответ:
Четное количество, так как еще последний следит за тем кто следит за первым.

[MUSIC]

за первым следит предпоследний, так вот последний следит за предпоследним

[Aloner]

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

[6epcepk]

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

[homm]

> или первый придворный следит сам за собой
Нет, он следит сам за тем кто следит за вторым. Если бы он следил сам за собой, он не смог бы следить за вторым.

[6epcepk]

Не улавливаю: каждый следит за тем, кто идет следующий в списке, верно? Второй идет за первым, поэтому первый должнен следить за вторым. Но на практике, он следит за тем, кто следит за вторым. Кто же этот кардинал, кто следит за вторым?

[homm]

>Не улавливаю: каждый следит за тем, кто идет следующий в списке, верно?
Не верно. Каждый следит за тем, кто следит за тем кто следующий в списке.

[WarGoth]

четное

[Zav]

Правильный ответ:
>>

Придворных всего 3, иначе предпоследний не сможет следить за тем кто следит за последним.
1 > 3 первый следит за тем кто следит за вторым, т.е. за третьим
3 > 2 третий (последний) следит за тем, кто следит за первым, т.е. второй
2 > 1 и второй (предпоследний) следит за тем, кто следит за третьим :)

<<

[Alien]

Вот вам пример!
Из семи придворных. Первый следит за 5-м, 5-й - за 2-м, 2-й - за 6-м, 6-й - за 3-м, 3-й - за 7-м (последний), 7-й - за 4-м, а 4-й - за первым. Вот :)

[dio77]

Для пяти: 1->4, 2->5, 5->3, 4->2, 3->1. Таким образом, предпоследний (4) следит за (2), который следит за (5).

[Zav]

Приношу извинения, ошибся.
Их может быть любое нечетное количетсво, dio77 прав, за что ему + в карму.

[homm]

Это был главный приз? :)

[rsa]

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

[rsa]

Описался малость: Первый должен следить за придворным с номером (n+3)/2

[3biga]

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

[homm]

1→3 3→2 2→4 4→3 3→2 2→4 4→3 — безконечный цикл.

[Leon478]

Нечетное. Притом я обнаружил лишь один способ составления зависимостей для нечетного числа придворных.
Пример для девяти:
1>6 6>2 2>7 7>3 3>8 8>4 4>9 9>5 5>1

[BVadim]

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


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



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

[Leon478]

По перврому примеру получается:
1 следит за 3
3 следит за 5
Это не верно, тот за кем следит первый должен следить за вторым.
3 следит за 5

[mariarty]

в задаче сказано

"Предпоследний следит за тем, кто следит за последним"

получается он следит сам за собой.

[BVadim]

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

[Plazik]

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

[daeq3]

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

Пусть всего придворных 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 - нечётное

[daeq3]

Ошибочка небольшая :) n-k+4 = k+1, n = 2k-3. Но смысл не меняется.

[DmitriKadykov]

Вот это пожалуй лучшее решение из всех представленных. Особенно понравилась замена x на k-2. Красиво!

[naething]

Да, все верно. Главное — понять, что по условию для любых m, p = 1, 2, ..., n имеет место равнозначность
m -> p <=> p -> m + 1 (mod n)

[daeq3]

Это единственное условие задачи, поэтому понять его действительно главное :))

[sii]

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

[irbys]

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

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

[irbys]

[sii]

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

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

[sii]

не могу добавить img
http://i163.photobucket.com/albums/t293/modsoccer/3-4.png

[3biga]

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

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

[Plazik]

А если так http://ipicture.ru/uploads/080501/TfZMXEqYTT.gif
Если предпоследнего считать 3, а последнего 4 ?

[3biga]

Это как? :)) А 8-й тогда какой? Если 8-й - 3-й, то все равно должно соблюдаться правило, что 2-й следит за тем, кто следит за 8-м (он же 3-й), а 8-й следит за тем, кто следит за 4-м.
Вы путаете порядок и имена элементов.

[dio77]

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

[3biga]

на два комментария выше то же самое, только с группировкой по кругам :)

[dio77]

Я видел, потому и запостил такой вариант. Имхо он нагляднее)

[Yorick]

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


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

[Yorick]

упс, с символами косяк.
Вобщем интерпретация:
j -> (1+n)/2 + j при j <= (n-1)/2
j -> (1-n)/2 + j при j > (n-1)/2

[zanooda]

[DmitriKadykov]

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

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

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

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

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

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

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

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

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

[DmitriKadykov]

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

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

[Mercury13]

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

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

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

[Mercury13]

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.

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

[Tricky]

Доказательство нужно строить отпративного.

[qweqwe2]

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

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

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

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

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

[qweqwe2]

Прощу прощения за то, что хабр нагло исковеркал мой комментарий.

[qweqwe2]

Требуется найти все такие n, при которох для всех 0<=iТребуется найти все такие n, при которох для всех 0<=iТребуется найти все такие n, при которох для всех 0<=iТребуется найти все такие n, при которох для всех 0<=i

[qweqwe2]

Ладно, буду ждать суперхабра.

[Hitryi_Pryanik]

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

[nBite]

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

[TiGR]

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

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

1 » 3
2 » 1
3 » 2

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

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

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

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

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

[TiGR]

Странно, хабр закинул комментарий к этому, но я писал ответ на топик, а не на это сообщение.

[DmitriKadykov]

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

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

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

[rootalex]

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

[rootalex]

Все придворные имеют две связи: 1-за ним кто-то следит, 2-он следит за кемто
Всех придорных тогда можно представить в виде бусинок на ниточке
Первая бусинка "следит" за второй, вторая за третьей ... предпоследняя з последней и последняя за первой см рис 1
http://www.picamatic.com/show/2008/05/04/09/215178_bigthumb.gif

При нечетном n мы можем расположить бусинки не разрывая нитку(связи кто за кем следит) как на рис 2
Сначала поочередно все нечетные(синие) за ними все четные(зеленые)
В этом новом ряде соблюдаются все условия задачи
n бусинка находится в средине ряда и следит за первой потому-что та в свою очередь следит за первой синей бусинкой

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

[Niks]

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

[retrovisor]

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

При каких 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.

[nicola]

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

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

[DmitriKadykov]

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

У нас фактически есть множество натуральных чисел от 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 ЧТО И ЕСТЬ ДОКАЗАТЕЛЬСТВО!

[Krizai]

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

[Krizai]

Тю, проглючил, конечно же нечетное - со счету сбился :)