9. Имеется 100 фишек, на которых написаны номера 1, 2,...100. Фишки поставили в вершинах правильного 100-угольника так, что они оказались упорядочены в порядке возрастания при обходе вершин по часовой стрелке. За один ход можно обменять местами некоторые две фишки, расположенные в соседних вершинах, при том условии, что номера этих фишек различаются между собой не более чем на k. При каком наименьшем k серией таких ходов можно добиться расположения, в котором каждая фишка переместится на одну позицию по часовой стрелке (по отношению к своему начальному положению)?
У меня получилось k=50, но даже если это верно, надо бы устроить конкурс на лучшее доказательство
из Сириуса-22
из Сириуса-22
Да, вроде лучше 50 не выходит.
В любом случае, хотя бы одна фишка должна пройти весь круг против часовой и обменятся со всеми другими (которые движутся по часовой). Минимум будет для 50 или 51, для которых максимальная разница будет 50 (при обмене с 1 или 100).
В любом случае, хотя бы одна фишка должна пройти весь круг против часовой и обменятся со всеми другими (которые движутся по часовой). Минимум будет для 50 или 51, для которых максимальная разница будет 50 (при обмене с 1 или 100).
из Сириуса-22
Можно рассмотреть величину сдвига фишки, от начального положения (плюс по часовой).
Если [math] - сумма таких сдвигов по всем фишкам, то она не меняется при обмене.
Изначально это 0, так 0 и останется.
В конечном положении они все должны сдвинутся на 1. А сумма не может из 0 в 100 перейти.
Но вообще говоря кроме 1 может быть любой сдвиг на [math], где k - целое.
Например работает сдвиг на 1 для 99 фишек и сдвиг на -99 для одной фишки.
Вобщем не могут быть все сдвиги положительные или все отрицательные (т.к. сумма 0). А если одна фишка имеет положительный сдвиг, а другая отрицательный, то они обязаны были где-то подвергнутся обмену.
Как не разбивай на два класса, всегда будет минимум 50 разници между какими-то двумя из разных классов.
Если [math] - сумма таких сдвигов по всем фишкам, то она не меняется при обмене.
Изначально это 0, так 0 и останется.
В конечном положении они все должны сдвинутся на 1. А сумма не может из 0 в 100 перейти.
Но вообще говоря кроме 1 может быть любой сдвиг на [math], где k - целое.
Например работает сдвиг на 1 для 99 фишек и сдвиг на -99 для одной фишки.
Вобщем не могут быть все сдвиги положительные или все отрицательные (т.к. сумма 0). А если одна фишка имеет положительный сдвиг, а другая отрицательный, то они обязаны были где-то подвергнутся обмену.
Как не разбивай на два класса, всегда будет минимум 50 разници между какими-то двумя из разных классов.
из Сириуса-22
Например, если 1 в первом классе, а 100 во втором классе, то расстояние между ними 99.zykov писал(а):Source of the post Как не разбивай на два класса, всегда будет минимум 50 разници между какими-то двумя из разных классов.
Если 1 и 100 в первом классе, то любое число из второго класса будет иметь минимум 50 расстояние до 1 или до 100.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 9 гостей