niktoinikak (niktoinikak) wrote,
niktoinikak
niktoinikak

Category:

Хорошая задача

на круглом 12-местном столе разложены карточки с именами приглашённых. Гости пришли и сели, не обратив внимания на карточки. Докажите, что можно повернуть стол так, чтобы не менее 2-х гостей оказались на своих местах.
И замечательное, имхо, решение.
Предварительные замечания.
1. Все числа рассматриваем по модулю 12.
Это значит, что числа различающиеся на число, кратное 12, считаем одинаковыми. Т е например
-3 = 9, 0 = 12 = 60
2. Гостей обозначим числами 0, 1, 2, ... 11 Карточки с номерами считаем последовательно размещёнными по кругу по часовой стрeлке- 0, 1, 2, ...11
Место(обозначенное карточкой) на которое сел i-ый гость обозначим А(i)
Решение.
[Spoiler (click to open)]предположим, что утверждение задачи неверно - есть такое расположение А, что нельзя повернуть стол так, чтобы 2 человека оказались на своих местах.
Это означает, что для всех i числа А(i)-i различны( в самом деле, это число показывает, насколько надо повернуть стол по часовой стрелке, что бы i-ый гость оказался на месте изначально для него предназначенным). Эта разность очевидно может принимать значения от нуля до 11. Т к всего гостей 12 - все значения встречаются по одному разу.
Теперь рассмотрим сумму
(А(0) - 0) + (А(1) - 1) + (А(2) - 2) + ... + (А(11) -11)
В силу предыдущего замечания она равна
0 + 1 + 2 + ... + 11 = 66 = 6(напоминаню, мы рассматриваем числа по модулю 12)

Но, с другой стороны, она д б равна нулю т k числа А(i) - те же числа 0, 1, 2, ... , 11 - но в другом порядке.
Т е наше исходное предложение неверно - не все числа A(i) - i различны, среди них есть совпадающие.

Это решение имхо замечательно и неожиданно. Когда я пришёл к нему, я не мог поверить, что тут нет ошибки. Долго проверял, потом посмотрел в книжку - там решение видимо такое же(я кинул беглый взгляд).

Я искал решение основанное на другой идее. Именно, раз есть все разности, кто-то сидит на своём месте. И это должно как-то сузить возможности для других. Я по прежнему почти уверен, что такое решение должно существовать - но мне его найти не удалось. А хотелось бы - я не люблю чудеса, а изложенное выше решение - чудо. Мне по крайней мере совершенно непонятно, как так получилось :-)
Tags: Математика
Subscribe

promo niktoinikak december 8, 2016 21:29 1
Buy for 10 tokens
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment