Найменша кількість пар мишей для вгадування

Умова задачі

Є $2008$ мишей. Бівіс та Батхед грають у загадування пар. Спочатку Бівіс послідовно називає деякі $m$ пар мишей $(P_1,Q_1)$ ,..., $(P_m,Q_m)$ . У кожній названій парі миші мають бути різними, але кожна миша може зустрічатися в будь-якій кількості пар, порядок мишей у парах не має значення. Після цього Батхед загадує деяку пару різних мишей $(P,Q)$ і проголошує таку характеристику пари $(P,Q)$ : для кожної названої Бівісом пари $(P_i,Q_i)$ Батхед каже, скільки спільних мишей має $(P_i,Q_i)$ з його парою $(P,Q)$ . Наприклад, якщо миші пронумеровані від $1$ до $2008$ , і Бівіс назвав пари $(1,2)$ , $(2,4)$ , $(2,5)$ , $(5,6)$ , а Батхед загадав $(1,5)$ , то характеристика матиме вигляд $(1,0,1,1)$ – саме в такому порядку, в якому були названі пари $(1,2)$ , $(2,4)$ , $(2,5)$ , $(5,6)$ . Потім Бівіс має з першого разу вгадати, яку пару мишей загадано в якості $(P,Q)$ . Батхед може схитрувати: якщо Бівіс вгадає пару $(P,Q)$ , але деяка інша пара різних мишей має таку ж саму характеристику щодо кількостей спільних мишей з $(P_1,Q_1)$ ,..., $(P_m,Q_m)$ , він скаже, що Бівіс не вгадав. Яку найменшу кількість пар має назвати Бівіс, щоб потім гарантовано вгадати пару $(P,Q)$ ?

Пов’язані теми

Оптимальна конструкція (оцінка і приклад)Зв’язність

Олімпіадні задачі з математики

Задачі дня

Найменша кількість пар мишей для вгадування

Умова задачі

Пов’язані теми

Рекомендації щодо вивчення олімпіадної математики

Гурток за п’ять хвилин

П’ять років програми

Шість правил, підтверджених дослідженнями

Ритм олімпіадного року

Як зібрати задачі тут

Про проєкт

Автори задач

Що в архіві

Українські олімпіади й турніри

Міжнародні олімпіади

Змагання інших країн

Що є в кожної задачі

З чого почати

Хто це робить

Помилки та пропозиції

Автори задач

Богдан Рубльов

Українські олімпіади й турніри

Міжнародні й закордонні змагання

Дякуємо