Примеры и контрпримеры

23

«КВАНТ»

Д ЛЯ

М Л АД Ш И Х

Ш К О ЛЬ НИК О В

Примеры и контрпримеры

А.КАНУННИКОВ

Об одном признаке делимости Начнем с такого примера. Хорошо известен признак делимости на 3: число делится на 3, если сумма его цифр делится на 3. Верен аналогичный признак делимости на 9. Например, 145287 кратно 9, так как $1 + 4 + 5 +^{2} + 8 + 7 = ( 1 + 8 ) + ( 4 + 5 ) + (^{2} + 7 ) = = 3 \cdot 9$ кратно 9. Справедлив ли аналогичный признак делимости на 27? Возьмем, к примеру, наименьшее число с суммой цифр 27: 999. Легко видеть, что оно кратно 27 (достаточно разделить его на 9 и получить число 111, кратное 3). Возьмем другой пример: 11…11 (27 единиц). Разделив его на 3, получим число из 9 блоков 037:

111 111 … 111: 3 = 37 037 … 037.

Сумма цифр полученного частного равна $( 3 + 7 ) \cdot 9$ и кратна 9, значит, само частное делится на 9, а тогда исходное число из 27 единиц делится на 27. Мы разобрали два примера, но даже если бы нашли миллион подтверждающих примеров, мы бы не доказали признак. Напротив, число 9981 показывает, что наш признак неверен: хотя 9 + 9 + 8 + 1 = 27, но 9981 не кратно 27, так как 9981: 9 = 112 не кратно 3. Число 9981 опровергает неверный признак делимости на 27. Вообще, пример, который опровергает какое-то утверждение, называется контрпримером. Приведем шуточную «теорему»: в математике нет терминов, в названии которых пять согласных идут подряд. Само слово «контрпример» является контрпримером к этой «теореме».

2*. Признак делимости на 27 с суммой цифр неверен в десятичной системе счисления. Подумайте, почему в ней верны признаки делимости на 3 и 9, и попробуйте понять, в каких системах счисления верен аналогичный признак делимости на 27.

Об одном признаке равенства треугольников Перейдем к геометрии. Вполне очевидно, что если две стороны и угол между ними одного треугольника соответственно равны двум сторонам и углу между ними другого треугольника, то такие треугольники равны (рис.1). Это утверждение называется первым признаком равенства треугольников. Коротко говорят так: треугольники равны по двум сторонам и углу между ними. Давайте подумаем, а будет ли верен аналогичный признак, если слова «между ними» заменить словами «не между ними» (рис.2.) В подтверждение этой гипотезы говорит известный факт, что прямоугольные треугольники равны по катету и гипотенузе: прямой угол лежит

Рис. 1

Упражнения 1. Найдите самый маленький контрпример к «признаку делимости на 27», т.е. такое наименьшее натуральное число, не кратное 27, сумма цифр которого кратна 27.

DOI: https://doi.org/10.4213/kvant20200403

Рис. 2

25

«КВАНТ»

Д ЛЯ

М Л АД Ш И Х

по очереди, делится ли оно на 2; на 3;… на 9. На все восемь вопросов Дима ответил верно, причем ответов «да» и «нет» было поровну. а) Можете ли вы теперь ответить верно хотя бы на один из вопросов учительницы, не зная самого числа? б) А хотя бы на два вопроса? Конечно, если мы можем ответить на два вопроса, то и на один тем более. Поэтому, «по законам жанра», скорее всего, ответ в пункте а) – да, а в пункте б) – нет. Разумеется, это не гарантированно. Но согласитесь, было бы странным задавать два вопроса, если даже на один мы однозначно ответить не можем. Начнем с того, что попробуем придумать пример к пункту а). Напрашивается проверить ответ на первый вопрос учительницы – про делимость написанного (и неизвестного нам) числа N на 2. Если ответ «нет», то число нечетно и поэтому не делится также ни на 4, ни на 6, ни на 8. Поскольку ответов «делится» и «не делится» поровну, значит, на оставшиеся четыре числа 3, 5, 7, 9 число N должно делиться. Но тогда оно делится на $3 \cdot 5 \cdot 7 = 105$ и никак не двузначное. Полученное противоречие показывает, что число N точно делится на 2, так что ответ в пункте а) утвердительный. Перейдем к пункту б). Интуиция нам подсказывает, что ответ «нет», но мы этого точно не знаем. Назовем двузначное число хорошим, если учительница могла его написать на доске, т.е. если оно делится ровно на четыре числа от 2 до 9. В пункте а) мы доказали, что всякое хорошее число четное. Будем пытаться доказать ответ «да» в пункте б), т.е. найти число от 3 до 9, на которое точно делится или точно не делится каждое хорошее число. Найдется ли, к примеру, хорошее число, кратное 9? Если да, то оно также кратно 3, а еще 2, а тогда и 6. Уже 4 делителя: 2, 3, 6, 9. Наименьшее такое число 18 – оно и вправду хорошее. Попробуем теперь найти хорошее число, кратное 8. Оно автоматически делится на 2 и 4 – уже три делителя. Если оно делится на 3, то тогда и на 6 – уже пять делителей. Но оно может делиться на 5: 40 – хорошее число с делителями 2, 4, 5, 8.

Ш К О ЛЬ НИК О В

Примеры чисел 18 и 40 показывают, что нельзя однозначно ответить, делится ли хорошее число на 3, 4, 5, 6, 8, 9 или нет: всякий раз ответы для чисел 18 и 40 разные. Нам осталось определиться с семеркой: 18 и 40 на 7 не делятся. Существует ли хорошее число, кратное 7? Да, легко привести пример, взяв вместо числа $40 = 8 \cdot 5$ число $56 = 8 \cdot 7$. Вот мы и доказали, что ответ к пункту б) – «нет». Задача 3. а) Может ли работа фирмы за любые пять месяцев быть прибыльной, а за весь год – убыточной? б) Может ли такое положение продолжаться в течение шести лет? (Иными словами, по итогам любых пяти подряд идущих месяцев фирма получает прибыль, а по итогам каждого из шести лет – терпит убыток.) На первый взгляд, такого быть не может, но давайте не спешить с выводами. В пункте б) отрезок в шесть лет указан «для отвода глаз». На самом деле, описанная ситуация невозможна даже в течение пяти лет – ведь такой отрезок времени делится на 12 отрезков по пять месяцев и все они прибыльные по условию. Итак, в пункте б) ответ «нет». Перейдем к пункту а), еще не зная, приведут ли наши размышления к примеру или к опровержению. Переформулируем вопрос на математическом языке: может ли сумма 12 чисел быть отрицательной, в то время как сумма 5 любых подряд идущих из них положительна? Если да, то сумма первых десяти чисел положительна, а тогда сумма двух последних отрицательна. С другой стороны, верно симметричное заключение: сумма первых двух чисел отрицательна, а десяти остальных – положительна. Наконец, рассмотрев крайние пятерки чисел, получим, что сумма двух чисел в середине отрицательна. Для приведения примера учтем еще, что 1-е и 12-е числа участвуют каждое только в одной пятерке, так что переложим на них «основную ответственность за убыток». Из этих соображений уже несложно придумать пример:

$- 5, 0,^{2,} 2,^{2,} - 1, -^{2,} 2,^{2,} 2, 0, - 5$.

26

КВАН T 2020/№4

Вся сумма равна $- 2$. Аккуратно проверьте каждую пятерку подряд идущих чисел.

Кто больше, или «Оценка + пример»

Очень часто в задачах нужно не только привести пример, но и доказать его оптимальность в каком-то смысле (наибольшее число, наименьшее время работы и т. д.). Соответственно, решения таких задач состоят из двух частей. Когда мы приводим пример, нам нужно только показать, что он удовлетворяет условию. При доказательстве же оптимальности недостаточно привести несколько контрпримеров, мол, у нас лучше не получилось. Необходимо доказать, что ни у кого лучше не получится! Задача 4. В пять горшочков, стоящих в ряд, Кролик налил три килограмма меда (не обязательно в каждый и не обязательно поровну). Винни-Пух может взять любые два горшочка, стоящие рядом. Какое наибольшее количество меда сможет гарантированно съесть Винни-Пух? Если Кролик разольет мед поровну, то Пуху достанется 6 5 кг. Но Кролик может поступить хитрее: разлить по килограмму в горшочки 1, 3 и 5, и тогда Пух возьмет 1 кг. Может ли экономный Кролик спасти еще больше меда? Перебрав варианты, приходим к гипотезе, что нет. Докажем это и заодно покажем, как можно прийти к ответу 1 кг, если мы сразу не догадались до хитроумного способа Кролика. Пусть Пух может гарантированно забрать только x кг и не больше. Это значит, что как бы ни разливал Кролик мед, в каждой паре горшочков $( 1,^{2} ), (^{2,} 3 ), ( 3, 4 ), ( 4, 5 )$ не более x кг, причем в какой-то паре ровно x кг. Сложив содержимое пар ( 1, 2 ), ( 3, 4 ) и добавив 5-й горшочек (в котором тоже не более x кг), получим, что общая масса не более 3x кг (рис.5). Но по

Рис. 5

условию она равна 3 кг. Итак, $3 \le 3x$, т.е. $x \ge 1$. Значит, Кролик может не надеяться спасти больше двух килограммов меда. Кстати, из этого рассуждения получается и выше приведенный пример, и его единственность. Именно, чтобы x был равен 1, необходимо, чтобы в 5-м горшочке меду было ровно 1 кг. Но тогда, симметрично, и в 1-м горшочке ровно 1 кг. Теперь ясно, что во 2-м и 4-м горшочках должно быть пусто, а в 3-м – 1 кг.

Упражнение 5. Семья ночью подошла к мосту. Папа может перейти его за 1 минуту, мама – за 2, сын – за 5, а бабушка – за 10 минут. У них есть один фонарик. Мост выдерживает только двоих. Если переходят двое, то они идут с меньшей из их скоростей. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя. За какое наименьшее время семья сможет перейти мост?