Олимпиада Туймаада по математике. Младшая лига. 2018 год

На столе лежат 99 одинаковых с виду шаров, 50 из них — медные, и 49 — цинковые. Лаборант пронумеровал шары. За одну проверку на спектрометре можно выяснить, сделаны ли положенные в него два шара одного и того же металла. Но результаты выдаются только на следующий день. За какое минимальное число проверок можно узнать, из какого металла сделал каждый шар, если надо все проверки провести сегодня? ( С. Берлов, Н. Власова )

Комментарий/решение

Ответ: 98 проверок

Оценка: Допустим, лаборант провел менее 98 проверок. Тогда граф, в котором вершины - шары, а ребра - проведенные проверки, будет несвязным.

Пример: Сравним 98 шаров с оставшимся шаром. После получения результатов шары можно разбить на две группы: шары ,сделанные из одного материала с оставшимся шаром и шары, сделанные из другого материала.

Группа из 49 шаров - цинковая, а из 50 - медная.