Математика в кафе. S2E1.

Математика Оставить комментарий

Рассматривалась задача об обмене фотографиями (она же — задача о сплетницах).

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, по тому же адресу, что и в прошлый раз.

3 комментария к “Математика в кафе. S2E1.”

Оставить комментарий

Тема WordPress и иконки разработаны N.Design Studio
© 2024 Страница Алексея Яшунского RSS записей RSS комментариев Войти