Задание 19: сюжетные задачи про кино, театр и мотки верёвки

О чём эта подтема

В задании 19 регулярно встречаются два родственных по методу типа сюжетных задач.

Первый тип — задачи про группы людей (учащиеся, зрители кино и театра, куски верёвки, детали и т. п.), в которых заданы ограничения вида «доля определённой категории не превышает такую-то дробь от общего числа». Нужно ответить на три вопроса: а) возможна ли конкретная ситуация; б) какое наибольшее/наименьшее значение возможно при дополнительном условии; в) какое наибольшее/наименьшее значение возможно вообще, без этого условия. Все три пункта решаются одним и тем же аппаратом — целочисленными неравенствами.

Второй тип — задачи-игры, где два игрока по очереди совершают ходы по строгим правилам, и нужно определить, кто из них выигрывает при любой игре соперника (задачи про горошины, фишки, числа на доске). Здесь работает не алгебра долей, а анализ инварианта и построение явной стратегии.

Оба типа объединяет общий принцип задания 19: сначала получить точную оценку (доказать, что лучше определённого значения быть не может), а затем подтвердить её конкретным примером или стратегией.

Что нужно знать

• Как переводить фразу «не более $\dfrac{p}{q}$ от общего числа» в неравенство: если из группы численностью $T$ выделена подгруппа численностью $x$, то $x \le \dfrac{p}{q}T$, откуда $T \ge \dfrac{q}{p}x$, то есть «остальных» (например, девочек) должно быть не меньше $\left(\dfrac{q}{p}-1\right)x$.
• Все величины — целые неотрицательные числа, поэтому конечный ответ нужно проверять на целочисленность (округление вниз через $\lfloor \cdot \rfloor$, если оценка получилась дробной).
• Принцип разбиения объединения на непересекающиеся части: если каждый объект принадлежит хотя бы одному из двух множеств (например, «был в театре» или «был в кино»), удобно ввести три непересекающиеся категории: «только первое», «только второе», «оба».
• Идея «двойной пользы»: элемент, попавший сразу в обе категории (например, зритель, посетивший и театр, и кино), одновременно «работает» на оба ограничения, поэтому экономнее использовать именно такие элементы для выполнения условий, а не дублировать ресурс отдельно под каждое ограничение.
• Метод «оценка + пример»: для пунктов б) и в) сначала доказывается неравенство, верное для любой допустимой ситуации, а затем строится конкретный набор чисел, на котором это неравенство превращается в равенство.
• Для игр: понятие инварианта (величина, которая сохраняется или меняется предсказуемо в течение игры — например, сумма горошин у обоих игроков постоянна), понятие чётности числа ходов и явное построение стратегии («что делает игрок в ответ на любой ход соперника»).

Как решать: метод и алгоритм

Для задач о долях (тип «кино — театр»):

1. Ввести переменные для непересекающихся категорий: например, $x$ — мальчики, посетившие только театр, $y$ — мальчики, посетившие только кино, $c$ — мальчики, посетившие и то, и другое.
2. Перевести условия задачи в неравенства на количество девочек (или другой недостающей категории), избавившись от дробей умножением на знаменатель.
3. Понять, что для максимизации искомой величины (числа мальчиков) выгодно не создавать пересечение среди мальчиков (не тратить одного и того же мальчика на оба ограничения), но зато выгодно, чтобы «лишние» девочки посещали сразу обе категории — тогда они одновременно закрывают оба условия.
4. Найти оптимальное соотношение частей, приравняв «стоимость» одного ограничения к «стоимости» другого (балансировка), и получить общую формулу зависимости искомой доли от общего числа участников.
5. Для пункта а) — подставить конкретные числа и либо построить пример, либо показать противоречие.
6. Для пункта б) — применить общую оценку к заданному общему числу и округлить до целого.
7. Для пункта в) — использовать полученную предельную долю без округления (она не зависит от конкретного $n$).

Для задач-игр:

1. Разобрать вручную самые маленькие случаи (обычно это подпункты а) и б) задачи), полностью прописав дерево возможных ходов.
2. Найти закономерность: кто побеждает и почему — какая величина (инвариант) определяет исход.
3. Оценить максимально возможную длину партии, используя ограниченность ресурса (например, число горошин, максимально доступный ход).
4. Сформулировать стратегию победителя как чёткое правило «на каждый ход соперника отвечать так-то».
5. Доказать через чётность общего числа ходов, что при этой стратегии именно нужный игрок делает последний допустимый ход, а соперник остаётся без хода.
6. Обобщить вывод на произвольное $N$, опираясь на инвариант, а не на полный перебор.

Разбор примера

Пример 1. Каждый учащийся группы посетил кино или театр (возможно, и то, и другое). Среди зрителей театра мальчиков не более $\dfrac{4}{13}$, среди зрителей кино — не более $\dfrac{2}{5}$.

Введём: $x$ — мальчики, посетившие только театр, $y$ — мальчики, посетившие только кино. Пересечение среди мальчиков не выгодно создавать (оно «тратит» мальчика сразу на оба ограничения, снижая их суммарное число), поэтому в оптимальной конструкции его не делаем: всего мальчиков $m = x+y$.

Из условия на театр: если в театре $x$ мальчиков, а всего там $T$ человек, то $x \le \dfrac{4}{13}T$, откуда девочек в театре нужно не меньше $\dfrac{9}{4}x$. Аналогично из условия на кино: девочек в кино нужно не меньше $\dfrac{3}{2}y$.

Ключевая идея: пусть одни и те же девочки посещают и театр, и кино — тогда их количество одновременно засчитывается в оба ограничения. Значит, минимальное число различных девочек равно не сумме, а максимуму: $$\text{девочек} \ge \max\left(\frac{9}{4}x,\ \frac{3}{2}y\right).$$

Это выражение минимально, когда оба слагаемых равны: $\dfrac{9}{4}x = \dfrac{3}{2}y \Rightarrow y = \dfrac{3}{2}x$. Тогда $m = x+y = \dfrac{5}{2}x$, девочек $= \dfrac{9}{4}x$, а всего: $$n = m + \text{девочек} = \frac{5}{2}x + \frac{9}{4}x = \frac{19}{4}x.$$

Отсюда $x = \dfrac{4n}{19}$, и доля мальчиков: $$\frac{m}{n} = \frac{\frac{5}{2}x}{\frac{19}{4}x} = \frac{10}{19}, \qquad \frac{\text{девочек}}{n} = \frac{9}{19}.$$

Пункт в) решён: наименьшая доля девочек равна $\dfrac{9}{19}$ — она не зависит от общего числа учащихся.

Пункт б) при $n=20$: $m \le \dfrac{10}{19}\cdot 20 = \dfrac{200}{19} \approx 10{,}53$, а так как $m$ целое, $m \le 10$. Значит, наибольшее возможное число мальчиков — $10$.

Проверим достижимость конкретным примером (заодно закрывает и пункт а). Возьмём $x=4$ (мальчики только в театре), $y=6$ (мальчики только в кино), $9$ девочек, которые ходят и в театр, и в кино. Тогда театр: $4$ мальчика и $9$ девочек — всего $13$, доля мальчиков $\dfrac{4}{13}$ — ровно на границе. Кино: $6$ мальчиков и те же $9$ девочек — всего $15$, доля мальчиков $\dfrac{6}{15}=\dfrac{2}{5}$ — тоже на границе. Всего различных людей: $4+6+9=19$ человек, из них $10$ мальчиков.

Чтобы получить ровно $20$ учащихся, добавим ещё одну девочку, которая ходит только в кино: кино становится $6$ мальчиков и $10$ девочек (доля мальчиков $\dfrac{6}{16}=0{,}375 \le 0{,}4$ — условие не нарушено), а всего в группе $20$ человек, из них $10$ мальчиков. Это доказывает пункт а) — да, и одновременно подтверждает, что оценка $10$ из пункта б) достижима.

Пример 2. Игра с горошинами: у каждого игрока по $N$ горошин, ходом передают сопернику любое ещё не встречавшееся в партии число горошин (ноль запрещён), проигрывает тот, кто не может сделать ход.

Главный инвариант: сумма горошин у обоих игроков постоянна и равна $2N$ на протяжении всей партии (горошины только переходят от одного к другому). Так как передаваемое число не может превышать имеющегося запаса, а запас у любого игрока никогда не превышает $2N$, то за всю партию может быть использовано не более $2N$ различных чисел — партия обязана закончиться не более чем за $2N$ ходов.

Небольшой перебор при $N=2$ показывает: если первый передаёт $1$, второй отвечает $2$ — тогда у первого остаётся ровно $3$ горошины, и единственное незанятое число, не превышающее его запас, это $3$, ход вынужден; второй отвечает $4$ (тоже вынужденно) — и первому передавать больше нечего, все числа $1,2,3,4$ уже использованы, а его запас не даёт нового варианта. Если первый вместо этого сразу отдаёт $2$, второй отвечает $1$ — и у первого остаётся запас $1$, но число $1$ уже использовано, ходить нечем сразу же. В обоих случаях побеждает второй игрок. Аналогичная прямая проверка для $N=3$ также даёт победу второму.

Общий вывод: второй игрок может строить ответы так, чтобы использованные числа шли по возрастанию и в сумме исчерпали все значения от $1$ до $2N$ ровно за $2N$ ходов — по $N$ ходов у каждого. Поскольку $2N$ — чётное число, последний (то есть $2N$-й) ход в такой партии всегда делает второй игрок, а следующий ход должен был бы делать первый — но допустимых чисел уже не осталось. Значит, при верной игре второго побеждает именно он — это верно и для $N=2$, и для $N=3$, и для произвольного $N$.

Типичные ошибки

• Забывают, что все величины (число мальчиков, число девочек, число зрителей) — целые, и оставляют дробный ответ там, где нужно округление.
• При работе с двумя пересекающимися группами считают сумму долей напрямую, забывая, что элемент, попавший в пересечение, засчитывается в обе группы сразу, и это можно использовать для экономии, а не для лишнего сложения.
• В пункте в) пытаются подставить конкретное $n$ вместо того, чтобы получить универсальную долю, не зависящую от общего числа участников.
• Доказывают только оценку (неравенство), забывая привести конкретный числовой пример, подтверждающий её достижимость — без примера решение неполное.
• В играх ищут «симметричный» ответ (просто повторить ход соперника), не проверяя, что такое число уже могло быть использовано или не соответствует правилам.
• Не проверяют ограничение «нельзя передать больше, чем есть», из-за чего стратегия оказывается физически неосуществимой на некоторых ходах.
• Разбирают только маленький случай ($N=2$ или $N=3$) и сразу считают его доказательством для общего $N$, не указывая, как обобщается инвариант и подсчёт числа ходов.

На что обратить внимание на экзамене

В задачах про доли всегда явно вводите обозначения для каждой непересекающейся категории — это защищает от ошибок двойного счёта и делает решение проверяемым экспертом. Пункты а), б), в) оформляйте отдельно и полностью: для «да/нет» — с явным примером или коротким доказательством невозможности, для «наибольшее/наименьшее» — с оценкой и примером на равенство.

В задачах-играх для баллов за пункт с общим $N$ важно не только сказать «второй побеждает», но и явно описать стратегию словами (что именно передаёт игрок на каждом шаге) и обосновать, почему соперник не может её нарушить или обойти. Ключевая связка «инвариант плюс чётность» — стандартный способ доказать выигрыш без полного перебора всех партий, и именно её ожидают увидеть в решении.

Если не получается сходу решить пункт с общим $N$ или общей долей, обязательно доведите до конца пункты а) и б) — они оцениваются отдельно и дают гарантированные баллы даже без общего решения.