из Сириуса-22

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

из Сириуса-22

Сообщение Ian » 05 фев 2022, 18:01

9. Имеется 100 фишек, на которых написаны номера 1, 2,...100. Фишки поставили в вершинах правильного 100-угольника так, что они оказались упорядочены в порядке возрастания при обходе вершин по часовой стрелке. За один ход можно обменять местами некоторые две фишки, расположенные в соседних вершинах, при том условии, что номера этих фишек различаются между собой не более чем на k. При каком наименьшем k серией таких ходов можно добиться расположения, в котором каждая фишка переместится на одну позицию по часовой стрелке (по отношению к своему начальному положению)?

У меня получилось k=50, но даже если это верно, надо бы устроить конкурс на лучшее доказательство

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

из Сириуса-22

Сообщение zykov » 05 фев 2022, 21:36

Да, вроде лучше 50 не выходит.
В любом случае, хотя бы одна фишка должна пройти весь круг против часовой и обменятся со всеми другими (которые движутся по часовой). Минимум будет для 50 или 51, для которых максимальная разница будет 50 (при обмене с 1 или 100).

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

из Сириуса-22

Сообщение zykov » 06 фев 2022, 11:28

Можно рассмотреть величину сдвига фишки, от начального положения (плюс по часовой).
Если [math] - сумма таких сдвигов по всем фишкам, то она не меняется при обмене.
Изначально это 0, так 0 и останется.

В конечном положении они все должны сдвинутся на 1. А сумма не может из 0 в 100 перейти.
Но вообще говоря кроме 1 может быть любой сдвиг на [math], где k - целое.
Например работает сдвиг на 1 для 99 фишек и сдвиг на -99 для одной фишки.

Вобщем не могут быть все сдвиги положительные или все отрицательные (т.к. сумма 0). А если одна фишка имеет положительный сдвиг, а другая отрицательный, то они обязаны были где-то подвергнутся обмену.
Как не разбивай на два класса, всегда будет минимум 50 разници между какими-то двумя из разных классов.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

из Сириуса-22

Сообщение zykov » 07 фев 2022, 11:28

zykov писал(а):Source of the post Как не разбивай на два класса, всегда будет минимум 50 разници между какими-то двумя из разных классов.
Например, если 1 в первом классе, а 100 во втором классе, то расстояние между ними 99.
Если 1 и 100 в первом классе, то любое число из второго класса будет иметь минимум 50 расстояние до 1 или до 100.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 9 гостей