Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 76
покзалось, что довольно просто
нечетное
формально докзать за 6 минут пока идет билд не получилось. но попробовал разные варианты на простых случаях 2,3 и на всякий случай 4 и убедился, что для четных не работает, а для 3 легко придумать.
нечетное
формально докзать за 6 минут пока идет билд не получилось. но попробовал разные варианты на простых случаях 2,3 и на всякий случай 4 и убедился, что для четных не работает, а для 3 легко придумать.
Выделить для просмотра:
На мой взгляд, придворных нечетное количество. Допустим, их трое. Тогда первый следит за третьим, который следит за вторым, который следит за первым. Для любого нечетного N связи выстраиваются следующим образом:
Если туплю, простите
На мой взгляд, придворных нечетное количество. Допустим, их трое. Тогда первый следит за третьим, который следит за вторым, который следит за первым. Для любого нечетного 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)-ым придворным.Если туплю, простите
мне кажется... (начало ответа -> при такой постановке вопроса у короля бесконечное количество придворных) либо сам король следит хотя бы за одним из них.
Вообщем должен быть человек, за которым никто не следит, или который сам не следит ни за кем. <- конец ответа)
Вообщем должен быть человек, за которым никто не следит, или который сам не следит ни за кем. <- конец ответа)
Мой ответ:
Четное количество, так как еще последний следит за тем кто следит за первым.
Четное количество, так как еще последний следит за тем кто следит за первым.
Нечетное. Первый, тот за кем следит первый - он же тот кто следит за вторым, и второй. Трое - это минимум. Дальше можно вставлять их только по два в цепочку, получая каждый раз нечетное число.
"первый придворный из списка следит за тем, кто следит за вторым"
Я еще не проснулся до конца, или первый придворный следит сам за собой (как и второй и т.д.)?
Я еще не проснулся до конца, или первый придворный следит сам за собой (как и второй и т.д.)?
> или первый придворный следит сам за собой
Нет, он следит сам за тем кто следит за вторым. Если бы он следил сам за собой, он не смог бы следить за вторым.
Нет, он следит сам за тем кто следит за вторым. Если бы он следил сам за собой, он не смог бы следить за вторым.
четное
Правильный ответ:
>>
Придворных всего 3, иначе предпоследний не сможет следить за тем кто следит за последним.
1 > 3 первый следит за тем кто следит за вторым, т.е. за третьим
3 > 2 третий (последний) следит за тем, кто следит за первым, т.е. второй
2 > 1 и второй (предпоследний) следит за тем, кто следит за третьим :)
<<
>>
Придворных всего 3, иначе предпоследний не сможет следить за тем кто следит за последним.
1 > 3 первый следит за тем кто следит за вторым, т.е. за третьим
3 > 2 третий (последний) следит за тем, кто следит за первым, т.е. второй
2 > 1 и второй (предпоследний) следит за тем, кто следит за третьим :)
<<
Вот вам пример!
Из семи придворных. Первый следит за 5-м, 5-й - за 2-м, 2-й - за 6-м, 6-й - за 3-м, 3-й - за 7-м (последний), 7-й - за 4-м, а 4-й - за первым. Вот :)
Из семи придворных. Первый следит за 5-м, 5-й - за 2-м, 2-й - за 6-м, 6-й - за 3-м, 3-й - за 7-м (последний), 7-й - за 4-м, а 4-й - за первым. Вот :)
Для пяти: 1->4, 2->5, 5->3, 4->2, 3->1. Таким образом, предпоследний (4) следит за (2), который следит за (5).
Приношу извинения, ошибся.
Их может быть любое нечетное количетсво, dio77 прав, за что ему + в карму.
Их может быть любое нечетное количетсво, dio77 прав, за что ему + в карму.
Ответ - нечётное. Причём любое нечётное больше трёх подходит, любое чётное - не подходит.
Основная идея док-ва: Несложно доказать, что первый придворный обязан следить за придворным с номером (n+2)/2, где n - общее количество придворных. Полное доказательство приводить не буду. Если есть желание услышать - дайте знать :)
Основная идея док-ва: Несложно доказать, что первый придворный обязан следить за придворным с номером (n+2)/2, где n - общее количество придворных. Полное доказательство приводить не буду. Если есть желание услышать - дайте знать :)
Нечетное. Притом я обнаружил лишь один способ составления зависимостей для нечетного числа придворных.
Пример для девяти:
1>6 6>2 2>7 7>3 3>8 8>4 4>9 9>5 5>1
Пример для девяти:
1>6 6>2 2>7 7>3 3>8 8>4 4>9 9>5 5>1
Видимо я что-то не понял... но вроде бы и чётное и ничётное проходят...
Вот пример:
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
Поправьте, если не прав...
Вот пример:
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 - четное количество :)
Римскими цифрами буду обозначать придворных, арабскими - те кто следят за придворными, т.е. общее количество придворных будет 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 - нечётное
Пусть всего придворных 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…
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)-*-*
Теперь всё сходится.
*-*-*-*-*
/ \
* *
\ /
*-*-*-*-*
Направление слежки - по часовой стрелке. Нумеруем произвольный как №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
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.
Может, есть красивое доказательство наподобие тех, которые мы встречаем в книгах по функанализу или топологии... я придумать пока не могу.
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.
Может, есть красивое доказательство наподобие тех, которые мы встречаем в книгах по функанализу или топологии... я придумать пока не могу.
Вроде бы так никто и не сказал, почему не может быть чётное количество придворных. Мой ответ.
Обозначим "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
Очевидно, что f(i)===i+1/2 mod n. Однако число 2 обратимо по модулю n только в случае нечетного n.
Переформулирем задачу. Найти все такие n, при которох для всех 0<=iПредлагаю хардкорным математикам, в число которых я, к сожалению, не вхожу, довести следующий эскиз до ума.
Переформулирем задачу. Найти все такие n, при которох для всех 0<=iПредлагаю хардкорным математикам, в число которых я, к сожалению, не вхожу, довести следующий эскиз до ума.
Переформулирем задачу. Найти все такие n, при которох для всех 0<=iПредлагаю хардкорным математикам, в число которых я, к сожалению, не вхожу, довести следующий эскиз до ума.
Переформулирем задачу. Найти все такие n, при которох для всех 0<=i
Очевидно, что f(i)===i+1/2 mod n. Однако число 2 обратимо по модулю n только в случае нечетного n.
Прощу прощения за то, что хабр нагло исковеркал мой комментарий.
Попробовал решить графически дугами. Для троих получилось, для четверых никак :)
Нечётно. Дальше получаются звёзды и цветы.
Нечётно. Дальше получаются звёзды и цветы.
нечетное. Ведь для того, чтобы иметь замкнутый круг достаточно всего 2 человека, которые следят друг за другом.
Друг-математик сидит за спиной и неуверенно пожимает плечами, зачем усложнять то, что заведомо просто в решении?
Друг-математик сидит за спиной и неуверенно пожимает плечами, зачем усложнять то, что заведомо просто в решении?
Придворных всего трое (знаю, такой вариант тут уже закритиковали, но всё же, у мен аргументы).
В условии не сказано, кто следит за первым, однако там сказано, что за ним кто-то следит. Единственными исключениями из правилс лежения являются последний и предпоследний. Значит, мы не можем выбрать произвольного придворного и назначить его следить за первым. Следящий за первым предворный должен быть где-то в условиях. А потому возможное решение только такое:
1 » 3
2 » 1
3 » 2
Итак, первый следит за тем кто следит за вторым. За вторым следит третий, так что тут правильно
Второй следит за тем, кто следит за третьим. За третьим следит первый, и соответственно 2 следит за первым.
Также предпоследний (второй) следит за тем, кто следит последним, т.е. за первым.
Последний следит за тем, кто следит за первым, т.е. за вторым. Сходятся все условия.
Во всех иных вариантах за первым никто не следит или же назначается произвольный придворный, т.е. из условий делаются исключения.
В условии не сказано, кто следит за первым, однако там сказано, что за ним кто-то следит. Единственными исключениями из правилс лежения являются последний и предпоследний. Значит, мы не можем выбрать произвольного придворного и назначить его следить за первым. Следящий за первым предворный должен быть где-то в условиях. А потому возможное решение только такое:
1 » 3
2 » 1
3 » 2
Итак, первый следит за тем кто следит за вторым. За вторым следит третий, так что тут правильно
Второй следит за тем, кто следит за третьим. За третьим следит первый, и соответственно 2 следит за первым.
Также предпоследний (второй) следит за тем, кто следит последним, т.е. за первым.
Последний следит за тем, кто следит за первым, т.е. за вторым. Сходятся все условия.
Во всех иных вариантах за первым никто не следит или же назначается произвольный придворный, т.е. из условий делаются исключения.
Большая часть ответов это не более чем рассмотрение частных случаев. Что никак не может считаться решением. Если я знаю что верен один из двух ответов (чет-нечет), то понятно что можно взять три - убедиться что условие выполняется и дать ответ. Тут особо и заморачиваться не надо.
Но по-хорошему необходимо доказать две вещи:
1) при всех четных условие не выполняется
2) при всех четных - выполняется
Но по-хорошему необходимо доказать две вещи:
1) при всех четных условие не выполняется
2) при всех четных - выполняется
я могу доказать на рисунке, что не может быть нечетное колличество придворных, а надо еще? Ниже там есть доказательство, однако там половина слов таких что я даж не знаю чего они означают
Все придворные имеют две связи: 1-за ним кто-то следит, 2-он следит за кемто
Всех придорных тогда можно представить в виде бусинок на ниточке
Первая бусинка "следит" за второй, вторая за третьей ... предпоследняя з последней и последняя за первой см рис 1
http://www.picamatic.com/show/2008/05/04/09/215178_bigthumb.gif
При нечетном n мы можем расположить бусинки не разрывая нитку(связи кто за кем следит) как на рис 2
Сначала поочередно все нечетные(синие) за ними все четные(зеленые)
В этом новом ряде соблюдаются все условия задачи
n бусинка находится в средине ряда и следит за первой потому-что та в свою очередь следит за первой синей бусинкой
Если же у нас будет четное колличество бусинок-придворных, то тогда n-бусинка будет находиться в конце нового ряда и будет следить за первой, что противоречит второму условию задачи
Всех придорных тогда можно представить в виде бусинок на ниточке
Первая бусинка "следит" за второй, вторая за третьей ... предпоследняя з последней и последняя за первой см рис 1
http://www.picamatic.com/show/2008/05/04/09/215178_bigthumb.gif
При нечетном n мы можем расположить бусинки не разрывая нитку(связи кто за кем следит) как на рис 2
Сначала поочередно все нечетные(синие) за ними все четные(зеленые)
В этом новом ряде соблюдаются все условия задачи
n бусинка находится в средине ряда и следит за первой потому-что та в свою очередь следит за первой синей бусинкой
Если же у нас будет четное колличество бусинок-придворных, то тогда n-бусинка будет находиться в конце нового ряда и будет следить за первой, что противоречит второму условию задачи
Аналогичная задача встречалась буквально 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.
При каких 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 градусов:)
внешений круг поворачивается на 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 ЧТО И ЕСТЬ ДОКАЗАТЕЛЬСТВО!
У нас фактически есть множество натуральных чисел от 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 ЧТО И ЕСТЬ ДОКАЗАТЕЛЬСТВО!
Нарисовал частный случай на бумаге, получилось четное.
Это конечно не четкое доказательство, но по картинке судя по другому быть не может.
Это конечно не четкое доказательство, но по картинке судя по другому быть не может.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача о придворных.