Задачи

«КВАНТ» ДЛЯ МЛАДШИХ ШК О ЛЬНИК О В

Задачи

Из трех палочек можно сложить треугольник. От каждой палочки отломили по куску и сложили из них другой треугольник. Всегда ли из оставшихся частей тоже можно сложить треугольник? Л.Емельянов числа a, при котором число a ◊ 1001 ◊ 1003 ◊ 1005 + 4 будет точным квадратом. Н.Агаханов

3. На контурную карту нанесены 10 городов (без названий) и дороги между некоторыми из них. Незнайке дали задание нанести на карту названия

Эти задачи предлагались на XIV Южном математическом турнире.

4. Прямоугольник, состоящий из кле- ток шахматной доски, назовем важным, если все его угловые клетки черные. На каждой клетке шахматной доски написано количество важных прямоугольников, содержащих эту клетку. Пусть B – сумма чисел, написанных на черных клетках, а W – сумма чисел, написанных на белых клетках. Найдите B – W. Олимпиада ЮАР

Иллюстрации Д.Гришуковой

2. Приведите пример натурального городов, но выдали лишь список пар городов, напрямую соединенных дорогой. Этого хватило, чтобы однозначно установить название каждого города. Как такое могло быть? С.Волчёнков

20

КВАН T 2019/№12

зовем это внешним набором чисел фигурки. Пример приведен на рисунке 3,а.

Упражнение 2. Существует ли фигурка с таким внешним набором чисел:

а) 0,3,3,3,3; б) 0,2,3,3; в) 0,0,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3; г) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1?

Задача 2. Как по внешнему набору чисел найти периметр фигурки? Во внешнем наборе каждый единичный отрезок периметра посчитан один раз (рис.3,б). Значит, сумма чисел внешнего набора равна периметру: $¦_{внешн} p$. Теперь используем найденные свойства внутреннего и внешнего наборов для вывода полезной формулы. Задача 3. Пусть s – это площадь фигурки, p – ее периметр, а i – количество внутренних перегородок. Найдите и докажите формулу, связывающую эти три величины. Поймем, как связаны внешний и внутренний наборы. В одном случае мы для каждой клетки считали, сколько из ее сторон лежит внутри, а в другом – сколько на границе. Таким образом, в двух наборах вместе мы посчитали все 4 стороны каждой из s клеток. Значит, ¦ внутр ¦ внешн 4s. Используя результаты предыдущих задач, получим: 2 i p 4 s.

Упражнения 4. Квадрат 5 u 5 разрезали на несколько многоугольников так, что суммарная длина разрезов равна 12. Чему может быть равен суммарный периметр всех многоугольников? 5. Доску 6 u 6 разрезали на прямоугольники 1 u 2. Какой может быть суммарная длина разрезов? 6. Квадрат 8 u 8 разрезали на тетраминошки (фигурки из четырех клеток). Суммарная длина разрезов оказалась равна 60. Сколько среди этих фигурок может быть квадратов?

Теперь обсудим следующую задачу. Задача 5 (Н.Стрелкова). Квартира 3 u 3 состоит из 9 квадратных комнат 1 u 1. Каждые две соседние комнаты соединены дверью. Какое наименьшее количество дверей должно быть открыто, чтобы кот, находящийся в одной из комнат, мог свободно гулять по всей квартире? Территорией будем называть множество комнат, между которыми можно свободно передвигаться. Если от одной комнаты нельзя дойти до другой, то они отнесены к разным территориям. (В примере на рисунке 4 территория кота состоит

Упражнение 3. Найдите все фигурки, у которых периметр больше площади а) в 5 раз; б) в 4 раза; в) в 3 раза.

Из доказанной формулы следует такое свойство. Задача 4. Докажите, что периметр клетчатой фигурки всегда является четным числом. Из формулы видно, что p является разностью четных чисел 4s и 2i, поэтому оно тоже четно. В следующих упражнениях снова помогает та идея, что при суммировании периметров частей разрезы учитываются дважды.

Рис. 4

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

21

«КВАНТ»

ДЛЯ

МЛАДШИХ

увеличится на одну комнату. Если же эта дверь ведет в комнату, до которой кот уже мог дойти иным путем, то территория не изменится. Получается, с каждой открытой дверью территория кота увеличивается не больше чем на 1. Сначала она равна 1, а в конце – 9. Значит, потребуется открыть хотя бы 8 дверей. Задача решена. Подумайте, где именно используется, что мы предлагаем выбрать дверь коту, а не открываем ее сами. Второе решение (количество территорий). Снова закроем все двери и будем открывать их по одной. Теперь будем считать общее количество территорий. Сначала каждая комната образует одну территорию, т.е. всего территорий 9. В конце все комнаты образуют одну территорию. Дверь может соединять либо две разные территории – тогда при ее открывании количество территорий уменьшится на 1, либо соединять территорию с самой собой – тогда количество территорий не уменьшится. Снова выходит, что хотя бы 8 дверей должны быть открыты. В следующем упражнении помогает тот же прием.

Упражнение 7. В квадратном лабиринте размером 6 u 6 от любой клетки можно дойти до любой другой. Какое наибольшее количество внутренних перегородок может в нем быть?

Теперь применим этот подход к клетчатым фигуркам. Задача 6. Какое наименьшее количество внутренних отрезков сетки может быть в фигурке с площадью s? Рассмотрим произвольную фигурку площади s, покрасим ее всю в белый цвет. Выберем одну из клеток фигурки, покрасим ее в черный. Далее будем закрашивать по одной белой клетке в черный цвет так, чтобы новая черная клетка примыкала по стороне к уже закрашенной части. (Такую клетку всегда получится найти: если есть и белая клетка, и черная, то на пути от одной до другой встретится пара из двух соседних разноцветных клеток.) Каждый раз количество внутренних отрезков сетки в черной фигурке будет увеличиваться хотя

ШК О ЛЬНИК О В

бы на единицу. В итоге все клетки станут черными. Значит, внутренних отрезков исходной фигурки не меньше s – 1. Заметим, что алгоритм добавления клеток здесь ровно такой же, что и в задаче про кота. Легко привести пример, в котором внутренних отрезков действительно столько: это, например, прямоугольник 1 u s. Задача 7. Какой наибольший периметр может быть у фигурки с площадью s? Нами уже доказана формула 2 i p 4 s. Из нее видно, что при фиксированном s чем больше p, тем меньше i. Значит, периметр наибольший тогда, когда количество внутренних отрезков наименьшее. Как мы уже выяснили, это достигается в случае i s 1. Подставив это в формулу 2 i p 4 s, получим, что p 2 s 2. Итак, периметр фигурки с площадью s не больше чем 2 s 2. Пример подходит прежний. Попробуйте применить ту же идею последовательного добавления клеток в следующих упражнениях.

Упражнения 8. Из фигурки, состоящей из 20 клеток, можно вырезать квадрат 3 u 3. Докажите, что ее периметр не больше 34. 9. Известно, что некоторую клеточную фигурку можно разрезать на 5 квадратов 2 u 2. Какой наибольший периметр у нее может быть? 10. Нарисуйте по 10 разных фигурок, у каждой из которых периметр равен 14, а площадь равна а) 6; б) 7. в) Почему фигурки из пункта б) содержат квадрат 2 u 2, а фигурки из пункта а) – нет?

Разберем теперь задачу, где можно применить доказанную в задаче 7 оценку периметра. Задача 8. Можно ли квадрат 5 u 5 разрезать на два клетчатых многоугольника, у каждого из которых периметр равен 28? Предположим, что можно так разрезать. Дальше можно действовать по-разному. Первое решение. Так как сумма площадей фигурок равна 25, то у одной из полученных фигурок площадь не больше 12. По предыдущей задаче, ее периметр не больше 2 ˜ 12 2 26. Противоречие.