Рассматривалась задача об обмене фотографиями (она же — задача о сплетницах).
n человек съездили вместе в Калининград, каждый со своим фотоаппаратом. После этого они решили обменяться фотографиями. Когда два человека обмениваются, каждый переписывает себе все фотографии, которые к этому моменту есть у другого. Вопрос: сколько обменов данными надо осуществить, чтобы у всех были все фотографии?
Участвовали: Володя, Лёша, Катя, Саша, Оля, Кирилл, я.
Собственно, ещё до начала решения задачи я сообщил то, что знал заранее:
если f(n) — необходимое число обменов, то
n-1 ≤ f(n) ≤ 2n - 3
Первое следует из того, что если сделать менее n-1 обмена, то найдутся две группы людей, такие, что между этими группами информация вообще не передавалась. Верхняя оценка следует из того, что обмен можно организовать по цепочке (если занумеровать участников от 1 до n):
1—2, 2—3, 3—4, ..., (n-2)—(n-1), (n-1)—n, (n-1)—(n-2), (n-2)—(n-3), ... 4—3, 3—2, 2—1
После этого у всех будет всё, а операций потребуется n-1 + n-2 = 2n-3.
При n = 4 эта оценка оказывается "плохой", потому что обмен 1—2, 3—4, 1—3, 2—4 позволяет достичь желаемого результата за 4 шага (вместо даваемых 2n-3 пяти шагов).
Первый вопрос, который оказался решённым, касался случая n=5: можно ли уменьшить оценку в 7 шагов.
Оказалось, что можно. После нескольких попыток, Лёша предложил такое решение:
1—2, 2—3, 4—5, 3—5, 2—4, 2—1
Дальше "звездой вечера" был Саша: он заметил, что эта конструкция обобщается на произвольное n≥4:
1—2, 2—3, 3—4, ... (n-4)—(n-3), (n-3)—(n-2), (n-1)—n, (n-1)—(n-2), n—(n-3), (n-3)—(n-4),...,2—1
То есть, мы сначала передаём все фотографии "по цепочке", пока не останутся 4 человека, один из которых — "представитель" всех, кроме этой четвёрки. Потом они внутри четвёрки обмениваются, как это описано выше для n=4, и далее "представитель" передаёт все фотографии назад.
Это даёт верхнюю оценку 2n-4. Саша же предложил и способ повысить нижнюю оценку, заметив, что после n-1 обмена всеми фотографиями владеют в лучшем случае 2 человека. Следовательно, из оставшихся n-2 каждый должен ещё хотя бы раз поучаствовать в обмене. А значит после n-1 обмена должно последовать ещё, как минимум ](n-2)/2[ обменов. Таким образом:
n + ]n/2[ - 2 ≤ f(n)
Однако, это всё ещё далековато от верхней оценки (асимптотически нижняя даёт 1.5n, а верхняя — 2n).
К сожалению, попытки ещё сблизить эти оценки успехом не увенчались. Как показывают "официальные" решения ниже, "правильной" является всё-таки верхняя оценка, и она точнá. Если будет время, попробую — то ли сам дорешать, то ли разобраться в чужих доказательствах.
Благодаря очень внимательной и хорошо информированной Оле, мы знаем, что настоящие решения лежат здесь.
Следующая Математика в кафе состоится в воскресенье 7 марта 2010 года в 19:00, по тому же адресу, что и в прошлый раз.
Календарь событий
http://www.google.com/calendar/embed?src=39p365h7h1091piv6j1ap54es4@group.calendar.google.com&ctz=Europe/Moscow
Забыл поблагодарить за приглашение)) Мне очень понравилось... правда, у меня сложилось ощущение, что меня цинично изнасиловали в левое полушарие мозга... но хоть оно напряглось)
Пожалуйста 🙂 Заходи ещё 🙂