На острове живут 2023 человека. Некоторые из них дружат между собой (если А дружит с Б, то и Б дружит с А), причём у каждого не более 10 друзей. На остров едет бригада врачей, которые собираются привить часть жителей. Требуется, чтобы у каждого, кто останется не привит, все друзья были привиты. Какое минимальное количество доз вакцины врачи должны взять с собой, чтобы их гарантированно хватило?
1 Ответ
Для решения этой задачи нам нужно понять, сколько людей могут быть не привиты, учитывая ограничение на количество друзей каждого. Если у каждого будет не более 10 друзей, и они все будут привиты, тогда каждый непривитый человек должен иметь не менее 11 друзей. Это значит, что мы можем представить общество как множество групп по 11 человек, где каждый человек в группе дружит со всеми остальными.
Теперь давайте посчитаем, сколько всего людей может быть в одной такой группе. Так как 11 — это простое число, мы не можем разделить его нацело на 2023. Это значит, что максимальное количество людей, которых мы можем включить в одну группу, равно 2022 (так как всего на острове 2023 жителя).
Таким образом, минимальное количество людей, которое может быть непривито, равно:
2022 / 11 = 184
Это означает, что минимальное количество вакцин, которое врачи должны взять с собой, равно 185 (одна дополнительная вакцина для случайного непривитого человека, который может появиться).
Ответ: 185