тема 2 из 7

Доказательство невозможности

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

Главная тема в задании20На карте навыков

Доказательство невозможности
—В аналитике

Ответ «нет» — доказательство для всех случаев

Несколько неудачных попыток невозможность не доказывают. Нужно рассуждение, которое отбрасывает сразу все варианты.

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

Чётность суммы

Сумма целых чисел чётна тогда и только тогда, когда нечётных слагаемых в ней чётное число (чётность). Если условие ограничивает количество чётных или нечётных чисел, чётность суммы известна заранее. Когда нужная сумма другой чётности, ответ «нет».

Часто условие оставляет несколько случаев: например, «чётное число одно» и «чётных нет». Чётность отбрасывает один случай, а другой отбрасывают оценкой.

Пример

Восемь различных натуральных чисел таковы, что никакие два не имеют общего делителя, большего 1. Может ли сумма всех восьми чисел быть равна 62?

1.Два чётных числа имеют общий делитель 2, поэтому чётных чисел не больше одного.
2.Чётное число одно: нечётных семь, их сумма нечётна, и вся сумма нечётна. 62 — чётное число, этот случай не подходит.
3.Чётных чисел нет. Числа больше 1 попарно не имеют общих делителей, поэтому их наименьшие простые делители различны и нечётны. Каждое число не меньше своего наименьшего простого делителя.
4.Значит, сумма не меньше $1 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 76 > 62$ (если единицы среди чисел нет, сумма ещё больше).
5.В обоих случаях сумма не равна 62.

Ответ: нет

Остатки: две части равенства дают разные остатки

Если два числа равны, они дают одинаковые остатки при делении на любое число. Найдите делитель, при котором остатки двух частей разные, — это и есть доказательство. Остаток суммы, произведения и квадрата находят по остаткам слагаемых и множителей (остатки).

Делитель выбирают по условию. Если в равенстве есть квадраты, берут 3 или 4: квадрат даёт при делении на них только остатки 0 и 1. Если коэффициент делится на число, берут это число: слагаемое с ним даёт остаток 0.

Пример

Может ли число 2027 быть суммой квадратов двух натуральных чисел?

1.Предположим, что $2027 = a^2 + b^2$ .
2.Квадрат натурального числа при делении на 4 даёт остаток 0 или 1. Поэтому $a^2 + b^2$ даёт остаток 0, 1 или 2.
3. $2027 = 4 \cdot 506 + 3$ : остаток 3. Остатки частей равенства разные — противоречие.

Ответ: нет

Уравнение без подходящих целых решений

Обозначьте неизвестные количества буквами и запишите условие уравнением (сумма через количество). Количества — целые числа в известных границах: от 0 до числа всех предметов. Если уравнение не имеет решений в этих границах, ситуация невозможна. Выразите одну неизвестную через другую и сравните получившиеся границы.

Пример

На доске было написано 20 натуральных чисел, каждое из которых больше 10, но не превосходит 50. Вместо некоторых чисел (возможно, одного) написали числа, большие первоначальных на единицу. Числа, которые после этого оказались равными 51, стёрли, но на доске осталось хотя бы одно число. Среднее арифметическое первоначальных чисел равнялось 24. Могло ли среднее арифметическое оставшихся чисел оказаться равным 17?

1.Сумма первоначальных чисел $20 \cdot 24 = 480$ . Пусть стёрли $n$ чисел (они были равны 50), а ещё $m$ оставшихся чисел увеличили на 1; $0 \le m \le 20 - n$ .
2.Осталось $20 - n$ чисел с суммой $480 - 50n + m$ .
3.Если их среднее равно 17, то $480 - 50n + m = 17(20 - n)$ , то есть $33n = 140 + m$ .
4.Из $m \ge 0$ : $33n \ge 140$ , $n \ge 5$ . Из $m \le 20 - n$ : $33n \le 160 - n$ , $n \le 4$ . Противоречие.

Ответ: нет

Оценка: нужное значение вне возможных границ

Найдите наименьшее или наибольшее значение, которое может принимать величина при любом выборе. Если нужное значение лежит за этой границей, ответ «нет». Типичные оценки: сумма $n$ различных натуральных чисел не меньше $1 + 2 + \ldots + n$ ; если за ход каждый кусок режут на две части, после $k$ ходов кусков не больше $2^k$ ; среди $m$ подряд идущих натуральных чисел ровно одно делится на $m$ (кратные среди чисел подряд).

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

Пример

На доске записано $k$ последовательных натуральных чисел. Оказалось, что среди них чисел, делящихся на 20, меньше, чем чисел, делящихся на 23. Могло ли среди записанных чисел быть ровно десять чисел, делящихся на 20?

1.Пусть чисел, делящихся на 20, ровно 10. Тогда чисел, делящихся на 23, не меньше 11.
2.Оценка снизу: между первым и одиннадцатым числами, кратными 23, десять промежутков по 23, поэтому $k \ge 23 \cdot 10 + 1 = 231$ .
3.Оценка сверху: если $k \ge 220$ , первые 220 чисел разбиваются на 11 групп по 20 подряд идущих чисел, и в каждой группе есть число, кратное 20. Тогда таких чисел не меньше 11. Значит, $k \le 219$ .
4. $231 \le k \le 219$ — противоречие.

Ответ: нет

Величина, которая не меняется при ходах

Если в задаче выполняют ходы, найдите величину, которую ход не меняет: остаток от деления, чётность суммы. Тогда из начального положения получаются только положения с тем же значением этой величины. Если у нужного положения значение другое, его получить нельзя.

Пример

Дано натуральное число. Можно либо вычесть из него утроенную сумму его цифр, либо прибавить к нему утроенную сумму его цифр. Полученное число должно быть натуральным. Можно ли с помощью таких операций из числа 128 получить число 31?

1.При каждом ходе к числу прибавляют или из него вычитают $3S$ , где $S$ — сумма цифр. $3S$ делится на 3, поэтому остаток числа при делении на 3 не меняется.
2. $128 = 3 \cdot 42 + 2$ : остаток 2. Все числа, полученные из 128, дают остаток 2.
3. $31 = 3 \cdot 10 + 1$ : остаток 1.

Ответ: нет

Несколько ходов подряд

Когда один ход не даёт закономерности, выпишите результат двух-трёх ходов подряд в буквах. Для хода $(a; b) \to (a + b; a - b)$ два хода дают $(a; b) \to (a + b; a - b) \to (2a; 2b)$ : пара удваивается. Поэтому из пары $(100; 1)$ получаются только пары $2^k \cdot (100; 1)$ и $2^k \cdot (101; 99)$ .

Что не меняется при ходах

128остаток 2

0остаток 0

S(128) = 11

: ход меняет число на

3 \cdot 11 = 33

, а это число делится на 3.

У 128 остаток 2 при делении на 3. У 31 остаток 1, поэтому 31 не получить.

(100; 1)

ход 0

(101; 99)

ход 1

(200; 2)

ход 2

(202; 198)

ход 3

(400; 4)

ход 4

(404; 396)

ход 5

(800; 8)

ход 6

(808; 792)

ход 7

(1600; 16)

ход 8

Начальная пара

(100; 1)

Первые числа пар —

2^k \cdot 100

или

2^k \cdot 101

. 806 среди них нет: пару

(806; 788)

не получить.

Делайте ходы кнопками. В первом режиме ход меняет число на утроенную сумму цифр, во втором пара

(a; b)

переходит в

(a + b; a - b)

Как записать доказательство невозможности

Начните с предположения: «Пусть это возможно». Обозначьте неизвестные буквами и выведите из условия свойства: чётность, остаток, границы. Найдите противоречие с условием и закончите выводом «значит, это невозможно». Разбор нескольких попыток («пробовали 3 и 5, не получилось») доказательством не является: ответ «нет» без доказательства баллов не даёт.

Пример задания

Открытый банк ФИПИ

Из пары натуральных чисел $( a ; b ) ,$ где $a > b ,$ за один ход получают пару $( a + b ; a - b ) .$
а) Можно ли за несколько таких ходов получить из пары $( 100 ; 1 )$ пару, большее число в которой равно 400?
б) Можно ли за несколько таких ходов получить из пары $( 100 ; 1 )$ пару $( 806 ; 788 )$ ?
в) Какое наименьшее a может быть в паре $( a ; b ) ,$ из которой за несколько ходов можно получить пару $( 806 ; 788 )$ ?

Решение

а) Да. Цепочка ходов: $(100; 1) \to (101; 99) \to (200; 2) \to (202; 198) \to (400; 4)$ . В последней паре большее число равно 400.
б) Нет. Два хода подряд: $(a; b) \to (a + b; a - b) \to (2a; 2b)$ . Поэтому из $(100; 1)$ после чётного числа ходов получается пара $(2^k \cdot 100; 2^k)$ , после нечётного — $(2^k \cdot 101; 2^k \cdot 99)$ .
Число 806 не равно ни $2^k \cdot 100$ (это 100, 200, 400, 800, 1600, …), ни $2^k \cdot 101$ (это 101, 202, 404, 808, …). Значит, пару $(806; 788)$ из $(100; 1)$ получить нельзя.
в) Ход назад: пара $(c; d)$ получается за один ход только из пары $\left(\frac{c + d}{2}; \frac{c - d}{2}\right)$ и только если $c$ и $d$ одной чётности.
$(806; 788)$ получается только из $(797; 9)$ , а $(797; 9)$ — только из $(403; 394)$ . Числа 403 и 394 разной чётности, поэтому $(403; 394)$ ни из какой пары не получается.
Значит, $(806; 788)$ получается за несколько ходов только из пар $(797; 9)$ и $(403; 394)$ : это оценка $a \ge 403$ . Пример: $(403; 394) \to (797; 9) \to (806; 788)$ . Наименьшее $a$ равно 403.
Ответ: а) да; б) нет; в) 403.

Проверьте себя

Все задания на этот навык

Решать