|
|
 |
Условие
а) Есть 2n + 1 батарейка (n > 2). Известно, что хороших среди них на одну больше, чем плохих, но какие именно батарейки хорошие, а какие плохие, неизвестно. В фонарик вставляются две батарейки, при этом он светит, только если обе они хорошие. За какое наименьшее число таких попыток можно гарантированно добиться, чтобы фонарик светил?
б) Та же задача, но батареек 2n (n > 2), причём хороших и плохих поровну.
Решение
а) Оценка. Пусть была n + 1 попытка. В каких-то двух попытках использовалась одна и та же батарейка, сделаем её плохой. В остальных n – 1 попытках выберем по батарейке и сделаем их плохими. Всего не более n плохих батареек, а фонарик точно светить не будет.
Пример. Разобьём батарейки на n кучек: в одной – три батарейки, в остальных – по две. В какой-то кучке окажется хотя бы две хороших батарейки. В каждой кучке проверим все возможные пары – всего n + 2, и фонарик загорится.
б) Оценка. Пусть было n + 2 попытки. В каких-то попытках использовалась одна и та же батарейка, сделаем её плохой. Если осталось менее n попыток, то в каждой из них выберем по плохой батарейке. Если же осталось n попыток, то в них использовались только оставшиеся 2n – 1 батареек. Поэтому опять в каких-то двух попытках использовалась одна и та же батарейка, сделаем её плохой. В остальных n – 2 попытках выберем по плохой батарейке. Всего не более n плохих батареек, а фонарик точно светить не будет.
Пример. Разобьём батарейки на n – 1 кучку: в двух – по три батарейки, в остальных – по две. В какой-то кучке окажется хотя бы две хороших батарейки. В каждой кучке проверим все возможные пары – всего n + 3, и фонарик загорится.
Ответ
а) За n + 2 попытки; б) за n + 3 попытки.
Замечания
1. При n = 2 в задаче б) нужно 6 попыток.
2. Для знатоков. Решим задачу в общем случае, когда из m батареек k + 1 хорошая, где 1 ≤ k < m. Считая батарейки вершинами, а попытки рёбрами, переформулируем: в каком m-графе без (k+1)-антиклик наименьшее количество рёбер? На этот вопрос, если рассмотреть дополнение графа отвечает теорема Турана: в m-графе из k компонент связности почти равного размера, каждая из которых – клика.
3. Баллы – 5 + 5.
