Доказательство невозможности
Ответ «нет» в задании 19 требует строгого доказательства, которое исключает сразу все возможные случаи. Обычно рассуждают от противного: предполагают, что ситуация возможна, и ловят противоречие через чётность, остатки, оценку границ или инвариант.
Доказывайте от противного для всех случаев сразу
Несколько неудачных попыток не доказывают ответ «нет». Нужно общее рассуждение, которое показывает, почему не подходит ни один допустимый набор.
- Предположите, что требуемая ситуация возможна, и введите обозначения.
- Найдите свойство, которое нарушается: чётность, остаток, целочисленность, границы суммы или инвариант.
- Если задача распадается на случаи, разберите каждый (или проведите полный перебор).
- Явно зафиксируйте противоречие и запишите вывод: «Значит, это невозможно».
Четыре классических способа доказать «нет»
Если пример никак не складывается, проверьте эти четыре приёма — один из них почти наверняка даст противоречие.
Чётность
Посчитайте число нечётных слагаемых: если чётность суммы расходится с заданным числом, равенство невозможно.
Остатки (mod 3, 4, 9)
Сравните остатки частей равенства. Для квадратов берите деление на 3 или 4, для суммы цифр — на 3 или 9.
Оценка суммы и границ
Оцените величину снизу и сверху. Если нижняя граница больше верхней или цель лежит за границей, решений нет.
Противоречие с условием
Количество вышло дробным, числа перестали быть различными или нарушился инвариант операции — ситуация невозможна.
Чётность суммы
Сумма целых чисел чётна тогда и только тогда, когда в ней чётное число нечётных слагаемых (чётность). Если задано количество нечётных чисел, чётность суммы известна заранее.
Часто чётность закрывает один случай, а оставшийся добивает простая оценка снизу.
Пример
Восемь различных натуральных чисел таковы, что никакие два не имеют общего делителя, большего 1. Может ли сумма всех восьми чисел быть равна 62?
- 1.Любые два чётных числа делятся на 2, поэтому чётное число в наборе максимум одно.
- 2.Случай 1: чётное число ровно одно. Тогда нечётных чисел семь, значит, вся сумма нечётна и не может равняться 62.
- 3.Случай 2: чётных чисел нет. У чисел больше 1 наименьшие простые делители различны и нечётны, а каждое число не меньше своего делителя.
- 4.Тогда сумма восьми чисел не меньше (без единицы — ещё больше). Оба случая невозможны.
Ответ: нет
Разные остатки частей равенства
Равные числа всегда дают одинаковые остатки при делении на любой выбранный делитель (арифметика остатков). Если остатки левой и правой частей не совпали — равенство невозможно.
Делитель выбирают под задачу: для квадратов — 3 или 4 (квадрат даёт только остатки 0 и 1), для суммы цифр — 3 или 9, для линейных уравнений — один из коэффициентов.
Пример
Может ли число 2027 быть суммой квадратов двух натуральных чисел?
- 1.Предположим, что для натуральных и .
- 2.Каждый квадрат даёт на 4 остаток 0 или 1, поэтому сумма даёт на 4 только остаток 0, 1 или 2.
- 3.Но даёт остаток 3. Остатки не совпадают — равенство невозможно.
Ответ: нет
Уравнение без целых решений в границах
Обозначьте неизвестные количества буквами и составьте уравнение через сумму. Количество предметов — целое число в границах условия: выразите одну переменную через другую и проверьте, остаются ли допустимые целые значения.
Пример
На доске было написано 20 натуральных чисел, каждое из которых больше 10, но не превосходит 50. Вместо некоторых чисел (возможно, одного) написали числа, большие первоначальных на единицу. Числа, которые после этого оказались равными 51, стёрли, но на доске осталось хотя бы одно число. Среднее арифметическое первоначальных чисел равнялось 24. Могло ли среднее арифметическое оставшихся чисел оказаться равным 17?
- 1.Начальная сумма равна . Пусть стёрли чисел (все они были равны 50), а ещё оставшихся чисел увеличили на 1 ().
- 2.Осталось чисел с суммой . При среднем 17 получаем , то есть .
- 3.Из следует . Из следует . Целого , удовлетворяющего обоим условиям, нет.
Ответ: нет
Противоречие в оценках
Оцените одну и ту же величину снизу и сверху. Если нижняя граница оказывается больше верхней (или нужное значение выходит за допустимый предел), ситуация невозможна.
Частые заготовки: сумма различных натуральных не меньше ; при делении каждого куска пополам после ходов их не больше ; кратные среди подряд идущих чисел сжимают длину ряда с двух сторон.
Пример
На доске записано последовательных натуральных чисел. Оказалось, что среди них чисел, делящихся на 20, меньше, чем чисел, делящихся на 23. Могло ли среди записанных чисел быть ровно десять чисел, делящихся на 20?
- 1.Пусть кратных 20 ровно 10. Тогда кратных 23 должно быть хотя бы 11.
- 2.Оценка снизу: между первым и 11-м кратными 23 лежит 10 промежутков по 23, поэтому .
- 3.Оценка сверху: если бы , то в 11 полных двадцатках нашлось бы минимум 11 кратных 20. Значит, .
- 4.Неравенство невозможно.
Ответ: нет
Инвариант — неизменная величина при ходах
Инвариант — это свойство (обычно остаток или чётность), которое не меняется ни после одного разрешённого хода. Если у стартового и целевого состояний значения инварианта разные, добраться до цели невозможно.
Пример
Дано натуральное число. Можно либо вычесть из него утроенную сумму его цифр, либо прибавить к нему утроенную сумму его цифр. Полученное число должно быть натуральным. Можно ли с помощью таких операций из числа 128 получить число 31?
- 1.При каждом ходе число меняется на , что кратно 3, поэтому остаток числа при делении на 3 не меняется.
- 2.У старта остаток равен 2, а у цели остаток равен 1. Получить 31 невозможно.
Ответ: нет
Несколько ходов подряд в общем виде
Если один ход выглядит запутанно, выпишите в буквах два или три хода подряд — часто структура резко упрощается. Для операции второй ход даёт : каждые два хода пара просто удваивается.
Инвариант при операциях
Как оформить доказательство «нет»
Пишите коротко и строго: «Предположим, что это возможно» → вводите буквы → выводите противоречие (по чётности, остатку или границам) → завершайте фразой «Противоречие, следовательно, ответ — нет».
Частая ошибка. Проверить три-четыре варианта и написать «значит, подобрать нельзя» — верный способ получить 0 баллов. Всегда доказывайте невозможность для всех вариантов сразу.
Пример задания
Открытый банк ФИПИ
Из пары натуральных чисел где за один ход получают пару
а) Можно ли за несколько таких ходов получить из пары пару, большее число в которой равно 400?
б) Можно ли за несколько таких ходов получить из пары пару ?
в) Какое наименьшее a может быть в паре из которой за несколько ходов можно получить пару ?
Проверьте себя
00