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