Веселое u-party

[Shuhrat Ismailov]

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

[Renat Akhtyamov]

с чётным количеством столов не получается.
Но если u-party "весёлое", то возможно всё!

[Nadir Zaitov]

Здесь присутствуют: 3 (пользователей: 3 , гостей: 0) Nadir Zaitov (http://uforum.uz/member.php?u=3582), Elise (http://uforum.uz/member.php?u=5126), Evgeniy Sklyarevskiy (http://uforum.uz/member.php?u=23)
Эльзара! Привет! Неужели и ошиблись и попали не в тот раздел? ;)

[Evgeniy Sklyarevskiy]

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

Эльзара! Привет! Неужели и ошиблись и попали не в тот раздел? Она наверное пересаживалась за другой стол как и мы с Вами и попала сюда. Так когда все будут здесь? Это было бы решением задачи :-0)

[Nadir Zaitov]

За 44 мя столами, расположенных по кругу, сидели по одному человеку. По требованию тамады какие-то два человека пересаживаются за соседний стол, причем один по часовой стрелке, а другой - против. Смогут ли все участники застолья собраться за одним столом? Считаем, что столы достаточно большие.Ясно, что если ответ "не может", то это задача на нахождение инварианты семейства состояний и сопоставление с искомым - если вдруг разница - то не может.

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

2. Будем считать, что есть 1 "выделенный" стол и 43 (нечетное число) столов с которых люди должны переходить куда-то. Стол, что напротив выделенного как бы "одинокий" - у всех остальных есть парный стол равноудаленный от "выделенного" стола. Ясно, что легко последовательно передвигая людей с парных столов в сторону выделенного мы получим состояние, когда все с парных столов пересядут за выделенный стол, кроме того, что сидит на "одиноком" столе. Так вот мне кажется, что суммарное расстояние сделать меньше чем, 22 невозможно - т.е. расстояние до "одинокого" стола не уменьшаемо.

[Vitaliy Fioktistov]

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

чот это уже не на uParty а скорее на uGames смахивает....

[Nadir Zaitov]

чот это уже не на uParty а скорее на uGames смахивает.... Попарное разнонаправленное действие... хм... это попахивает u_чего_в_СССР_небыло.

[Shuhrat Ismailov]

А тамада случайно выбирает кому пересаживаться или специально должен собрать всех за один стол и мы должны дать ему алгоритм?
Ясно, что если ответ "не может", то это задача на нахождение инварианты семейства состояний и сопоставление с искомым - если вдруг разница - то не может.
Предлагаю следующий инвариант.
Пронумеруем столы по порядку, начиная с любого. Для каждого человека рассмотрим номер стола, на котором он сидит, и сложим эти 44 номера.
Сначала Получим 1+2+...+44=44*45/2=990
Начнем пересаживать......
Каждый раз для каждого человека будем рассматрим номер стола, на котором он сидит, и складывать эти 44 номера.
Ясно, что после каждого пересаживания эта сумма либо не менятся, либо меняется на 44.
Значит, остаток от деления данной суммы на 4 остается неизменным (инвариант состояния). Так как в начале сумма номеров столов равна 990, что дает остаток 2 от деления на 4.
В конце должно быть, что все люди пересели за один стол с номером n,
для которого рассматриваемая сумма станет равной 44n (а это число делится на 4. Получено противоречие.

[Nadir Zaitov]

Получено противоречие.Интересно, а это не ответ был?2. Будем считать, что есть 1 "выделенный" стол и 43 (нечетное число) столов с которых люди должны переходить куда-то. Стол, что напротив выделенного как бы "одинокий" - у всех остальных есть парный стол равноудаленный от "выделенного" стола. Ясно, что легко последовательно передвигая людей с парных столов в сторону выделенного мы получим состояние, когда все с парных столов пересядут за выделенный стол, кроме того, что сидит на "одиноком" столе. Так вот мне кажется, что суммарное расстояние сделать меньше чем, 22 невозможно - т.е. расстояние до "одинокого" стола не уменьшаемо.

[Shuhrat Ismailov]

Интересно, а это не ответ был?
Это был ответ. Я просто предложил другой инвариант

[madik]

нет

[Vitaliy Fioktistov]

чот это уже не на uParty а скорее на uGames смахивает.... Попарное разнонаправленное действие... хм... это попахивает u_чего_в_СССР_небыло.

в смысле не юПати, а eПати? ;)