Двойной подсчёт начинается с выбора одного и того же множества, которое удобно посчитать двумя способами. Равенство результатов затем связывает известные и неизвестные величины. Рассмотрим самостоятельно составленную задачу о списках кружков; она не описывает реальную школу и не является подтверждённым заданием официальной олимпиады.
Сначала уточним, что дано
Есть четыре кружка. В списке каждого — ровно три разных участника. Каждый школьник из этих списков записан ровно в два кружка. Сколько различных школьников участвует? Мы считаем только тех, кто встречается хотя бы в одном из четырёх списков; одна и та же запись внутри списка не дублируется.
При сложении 3 + 3 + 3 + 3 получаем 12. Но это число записей об участии, а не число различных людей: каждый школьник встречается дважды. Чтобы обосновать дальнейшее действие, назовём единицу подсчёта точнее.
Что именно считаем дважды
Рассмотрим пары «школьник — кружок, в который он записан». У одного человека будет две такие пары с разными кружками. Разобьём все пары сначала по кружкам. У каждого кружка их три, всего 4 × 3 = 12.
Теперь сгруппируем те же пары по школьникам. Если людей n, каждый даёт ровно две пары, значит, всего получается 2n. Мы не добавляем новый набор и не меняем смысл записи. Поэтому 2n = 12 и n = 6.
Общая идея подсчёта одного множества двумя способами разобрана в лекции MIT «More Counting», раздел 3. В нашем примере роль множества выполняют именно пары участия. Это объясняет деление на два, а не оставляет его арифметической догадкой.
Покажем, что условия совместимы
Назовём кружки А, Б, В и Г. Возьмём шесть школьников и обозначим их выбранными парами кружков: АБ, АВ, АГ, БВ, БГ, ВГ. Например, участник АБ записан в А и Б, а участник ВГ — в В и Г.
У кружка А окажутся участники АБ, АВ и АГ — трое. У Б — АБ, БВ и БГ; у В — АВ, БВ и ВГ; у Г — АГ, БГ и ВГ. Каждый человек присутствует ровно в двух списках. Таким образом, шесть не только следует из подсчёта, но и допускает конкретное распределение.
Изменим одно слово в условии
Пусть теперь каждый школьник записан не менее чем в два кружка. Пар участия по-прежнему 12, однако человек может дать и три, и четыре пары. Получаем только 2n ≤ 12, то есть n ≤ 6. Равенство больше не обязательно.
Например, можно взять трёх школьников и записать каждого во все четыре кружка. Тогда в каждом списке по три участника, каждый посещает не менее двух кружков, но людей всего три. Поэтому точный ответ требует условия «ровно в два».
В собственной задаче можно нарисовать таблицу: строки — школьники, столбцы — кружки, отметка — одна пара участия. Подсчёт по столбцам и по строкам должен учитывать одни и те же отметки. Проверка единицы подсчёта помогает понять, какое равенство действительно следует из условий.
