№21. Логические задачи и оценка: границы, противоречие, двойной подсчёт

Логическая задача — это задача, где важно не подставить числа в формулу, а понять, что из чего следует. Работает такой порядок: переписываешь условие короткими фактами, потом ищешь, что можно оценить сверху («не больше 16») или снизу («не меньше 24»), и наконец совмещаешь оценку с известным общим количеством. Очень часто уже этого хватает, чтобы получить точный ответ, а не диапазон.

Второй по частоте приём — метод от противного. Нужно показать, что груздей не больше 16? Предположи обратное: пусть их 17 — и посмотри, что тогда нарушается в условии. Так же проверяют слова «наименьшее возможное» и «наибольшее возможное»: предполагаешь, что бывает чуть меньше (или чуть больше), и приходишь к противоречию с условием.

Третий приём — считать связи с двух сторон. Каждый договор подписывают две страны; каждую линию на палке распиливают один раз, но она принадлежит сразу двум кускам; в каждой встрече участвуют двое. Поэтому сумма всех «подписей» вдвое больше числа договоров, и складывать договоры по странам подряд нельзя — один и тот же договор попадёт в счёт дважды.

Иногда в условии прямо просят найти наименьшее или наибольшее возможное число, и тогда рассуждение идёт в два хода: сначала оценка («больше быть не может»), потом пример, который эту оценку достигает. Без примера оценка ничего не доказывает: она показывает лишь, что вариантов не больше, но не что такой вариант существует. Так же устроен вопрос «сколько значений может принимать величина»: сначала находишь все ограничения, потом получаешь промежуток допустимых значений и считаешь, сколько целых значений в него попадает.

двойной подсчёт: Σ по всем участникам = 2 · число парных связей границы: «среди любых N есть хотя бы один A» ⇒ других объектов не больше N − 1 границы + общее количество: если одна часть не больше A, вторая не больше B и всего ровно N = A + B, то обе границы достигаются наименьшее и наибольшее: сначала оценка «не больше A», затем пример, в котором A действительно достигается

• Сравнение с границами: сначала найди, сколько объектов может быть максимум (или минимум), и только потом используй общее количество.
• Метод от противного: предположи, что условие нарушено, и покажи, что это противоречит тексту задачи.
• Отделяй «полные сутки» от «последнего шага»: последний день или последняя операция часто устроены иначе, потому что процесс обрывается раньше.
• Двойной подсчёт: считай не связи, а их концы, и делить на два в самом конце.
• Проверяй крайние случаи: «не менее одного и не более трёх» — это ровно 1 и ровно 3, а не «в среднем 2».
• После ответа обязательно подставь его обратно в условие и проговори каждую фразу: «среди любых 17 грибов есть рыжик» должна стать верной.
• Если спрашивают «сколько значений может принимать величина», сначала собери все ограничения на неё, потом посчитай целые значения в получившемся промежутке — и отдельно проверь, входят ли в него концы.

Типичные ошибки. 1) Делить всю высоту на суточное смещение: в задаче про улитку 10 : (3 − 2) даёт 10, но это неверно — последний подъём заканчивается на вершине, и спуска после него не происходит. 2) Складывать связи по каждой стороне отдельно: 4 · 5 + 6 · 3 = 38 — это двойной счёт, каждый договор учтён двумя странами. 3) Забывать крайние случаи и считать, что все объекты одинаковые. 4) Останавливаться на первом подходящем варианте, когда спрашивают «наибольшее» или «сколько значений» — нужны все варианты. 5) Считать, что ответ обязательно выводится формулой: в №21 ответ получается рассуждением, и обоснование входит в решение.

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

Проверь себя

1. Как фразу «среди любых 17 грибов есть хотя бы один рыжик» перевести в ограничение на число груздей?
2. Почему сумму связей, посчитанных по всем участникам, делят на два?
3. Почему в задаче про улитку нельзя делить высоту дерева на суточное смещение?
4. Зачем в логической задаче проверять ответ обратной подстановкой в условие?

Показательные решения