Основные идеи, используемые в поиске решения

Основные идеи, используемые в поиске решения

В поиске решения задачи можно попытаться  использовать следующие соображения:

решить аналогичную задачу с более простыми значениями данных и попытаться обобщить идею решения или непосредственно применить полученный результат к рассматриваемой задаче; в задаче общего характера рассмотреть частные случаи, начиная с более простых, и попытаться обобщить идею решения; разбить задачу на подзадачи; свести задачу к более простой; обобщить задачу.

Пример 1.1. В угловой клетке таблицы 5×5 стоит плюс, в остальных клетках – минусы. Разрешается в любой строке или любом столбце поменять все знаки на противоположные. Можно ли за несколько таких операций сделать все знаки плюсами?

Решение. После нескольких попыток убеждаемся, что ничего не получается. Но это, конечно, не является доказательством: может быть, мы просто не нашли подходящий способ. Доказательство перебором здесь не годится ввиду большого числа вариантов. Решим аналогичную задачу для таблицы 2×2. Здесь нетрудно убедиться, что ответ отрицательный, так как в таблице всегда будет либо один, либо три минуса. В то же время замечаем, что провести аналогичные рассуждения для исходной таблицы не удается. Но для исходной таблицы можно непосредственно использовать полученный результат. Выделим в исходной таблице угловой квадратик 2×2, в котором стоит плюс. При любом преобразовании исходной таблицы с выделенным квадратиком либо ничего не происходит, либо также меняются знаки в строке или столбце. Если бы мы сделали все знаки плюсами в большой таблице, то одновременно сделали бы это и в выделенном квадратике, что невозможно. Значит, это невозможно и для исходной таблицы.

Пример 1.2. Куб с ребром 3 легко распилить на 27 единичных кубиков шестью распилами. Можно ли уменьшить число распилов, если разрешается перекладывать части перед очередным распилом?

Решение. В процессе распилов придется, в частности, выпилить центральный кубик. Так как у него шесть граней, обойтись числом распилов, меньшим шести, не удастся.

Пример 1.3. Найти 10 различных натуральных чисел, сумма которых делится на каждое из них.

Решение. Решим задачу для меньшего количества чисел. Нетрудно убедиться, что для двух чисел решения нет. Для трех чисел легко найти решение 1, 2, 3. Далее легко сообразить, как можно увеличивать количество найденных чисел: нужно к найденной совокупности добавить сумму всех чисел этой совокупности. Тем самым задача решена в общем виде. Соответственно получаем следующий набор из 10 чисел: 1, 2, 3, 6, 12, 24, 48, 96, 192, 384.

Пример 1.4. В кладовой лежат 300 сапог: 100 хромовых, 100 кирзовых и 100 яловых, причем левых и правых поровну – по 150. Докажите, что из имеющихся сапог можно составить по крайней мере 50 пар.

Решение. Составим таблицу, в которой укажем количество сапог каждого вида.

Сапоги	Количество
Левых	правых	Всего
Хромовые	Хл	Хп	100
Кирзовые	Кл	Кп	100
Яловые	Ял	Яп	100
Всего	150	150	300

В каждой строке количество возможных пар равно меньшему из чисел, обозначающих количество левых и правых сапог в этой строке. Эти числа неизвестны. Преобразуем условие задачи, сделав его более определенным, но не увеличив при этом количество возможных пар. Найдем наименьшее число в таблице. Пусть это Хл. Уменьшим это число до 0. Тогда Хп станет равно 100. Восстановим баланс в таблице, уменьшив на Хл, например, Кп и увеличив Кл. Это можно сделать, так как Хл не превосходит Кп. Количество возможных пар в первой строке уменьшается на Хл в первой строке, а во второй может увеличиться, но не более, чем на Хл. Значит, во всей таблице количество возможных пар не может увеличиться, может только уменьшиться.

Проделаем то же самое с оставшимися четырьмя неопределенными числами. Теперь наименьшее число берем в другом столбце, так как в нем сумма оставшихся чисел равна 50, а в первом столбце – 150. Пусть наименьшее число – это Кп. Тогда оно уменьшится до 0, а Кл увеличится до 100, а число возможных пар не увеличится. Но теперь однозначно определятся Ял = Яп = 50, и эти сапоги образуют 50 пар. Тогда и в исходной таблице количество пар не меньше 50.

Упражнения

Из бумажного треугольника вырезали параллелограмм. Докажите, что его площадь не превосходит половины площади треугольника. Дан выпуклый многоугольник площади 9. Его пересекают 10 параллельных прямых на расстоянии 1 друг от друга. Докажите, что сумма длин отрезков, высеченных многоугольником на этих прямых, не более 10. Каждый ученик класса ходил хотя бы в один из двух походов. В каждом походе мальчиков было не больше 2/5. Докажите, что во всем классе мальчиков не больше 4/7. Каждую грань кубика разбили на четыре равных квадрата и раскрасили эти квадраты в три цвета так, чтобы квадраты, имеющие общую сторону, были покрашены в разные цвета. Докажите, что в каждый цвет покрашено 8 квадратов. Докажите, что число является целым. Подсчет двумя способами

Часто при решении задач бывает полезно подсчитать некоторую величину двумя способами и сравнить результат, – это может быть источником противоречия. Этим же способом составляют уравнение в текстовой задаче.

Пример 2.1. Можно ли расставить в прямоугольной таблице числа так, чтобы суммы по строкам были положительными, а по столбцам – отрицательными?

Решение. Предположим, что таблицу удалось заполнить. Посчитаем сумму всех чисел в таблице по строкам и по столбцам: по строкам она будет положительной, по столбцам – отрицательной. Противоречие.

Пример 2.2. Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и черных пятиугольников. Каждый черный лоскут граничит только с белыми, а каждый белый – с тремя белыми и тремя черными. Сколько лоскутов каждого цвета?

Решение. Пусть использовано b белых и с черных лоскутов. Имеем уравнение b + c = 32. Чтобы получить второе уравнение, посчитаем число границ между черными и белыми лоскутами. Черные лоскуты имеют 5с таких границ, белые – 3b. Отсюда 5с = 3b. Решив систему, находим, что черных лоскутов 12, а белых – 20.

Упражнения

В каждой клетке прямоугольной таблицы размером m×п записано число. Сумма чисел в каждой строке и каждом столбце равна 1. Докажите, что т = п. В классе 27 человек. Каждый мальчик дружит с четырьмя девочками, а каждая девочка – с пятью мальчиками. Сколько в классе мальчиков и сколько девочек? Существует ли выпуклый 2007-угольник, все углы которого выражаются целым числом градусов? Треугольник разрезали на выпуклые четырехугольники. Докажите, что хотя бы у одного четырехугольника есть угол не меньше 120°. Можно ли покрыть квадрат 3×3 уголками из трех клеток в несколько слоев? (все клетки покрываются одинаковым числом слоев).

Указание: заполните квадрат числами, чтобы общая сумма была положительной, а в каждом уголке – отрицательной.

Обратный ход

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

Пример 3.1. У трех девочек было 120 фантиков. Сначала Аня дала Вале и Гале столько, сколько у них было. Затем Валя дала Ане и Гале столько, сколько у них стало. И наконец Галя дала Ане и Вале столько, сколько у них к этому моменту имелось. В результате у всех стало поровну. Сколько фантиков было у каждой вначале?

Решение. В конце у всех оказалось по 40 фантиков. Перед этим Аня и Валя получили столько, сколько имели, то есть удвоили количество имевшихся у них фантиков. Значит, они имели по 20 фантиков, а Галя – 80. Продолжая рассуждения аналогичным образом, придем к исходному распределению. Решение удобно оформить в виде таблицы, в которой показано количество фантиков у каждой девочки после каждого этапа обмена.

Идея обратного хода нередко используется в геометрических задачах.

Пример 3.2. В квадрате ABCD на стороне АВ внутри квадрата построили равнобедренный треугольник АВЕ с углами при основании АВ, равными 15°. Докажите, что треугольник CDE правильный.

Решение. Решаем обратную задачу, Строим правильный треугольник CDE1. Легко определяем, что у треугольника АВЕ1 углы А и В равны по 15°. Тогда ΔАВЕ1 = ΔАВЕ, точки Е и Е1 совпадают, и треугольник CDE совпадает с правильным треугольником CDE1.

Упражнения

На озере одна лилия. Каждый день число цветков удваивалось, и на двадцатый день все озеро покрылось цветами. На который день покрылась цветами половина озера? Трем братьям дали 24 бублика так, что каждый получил на три буьлика меньше, чем ему лет. Меньший брат был сообразительный и предложил поменять часть бубликов. «Я, – сказал он, – оставлю половину бубликов, а другую разделю между вами поровну; после этого средний брат также оставит половину бубликов, а другую разделит поровну между мной и старшим братом. В конце старший брат поделит так же». Так и сделали. В результате все получили поровну. Сколько лет каждому брату? Учитель раздавал школьникам открытки. Первому он дал одну открытку и 1/10 оставшихся. Второму он дал 2 открытки и 1/10 оставшихся, и т. д. Девятому он дал 9 открыток и 1/10 оставшихся. Оказалось, что все получили поровну и все открытки были розданы. Сколько было открыток? Принцип Дирихле

Принцип Дирихле обычно иллюстрируют следующим примером: если посадить 10 кроликов в 9 клеток, то найдется клетка, в которой окажется не менее двух кроликов. В общем виде он формулируется так: если n элементов распределены по k множествам, то найдется множество, в котором окажется не менее n/k элементов, и найдется множество, в котором окажется не более n/k элементов. Несмотря на свою простоту, он является очень эффективным средством при решении многих задач.

Пример 4.1. В квадрате со стороной 1 расположены 51 точка. Докажите, что какие-то три из них можно накрыть кругом радиуса 1/7.

Решение. Разобьем квадрат на 25 маленьких квадратиков со стороной 1/5. По принципу Дирихле в одном из них окажется не менее трех точек. А так как диагональ этого квадратика меньше 2/7, то он помещается в круг радиуса 1/7.

Пример 4.2. Докажите, что среди любых пяти человек найдутся двое с одинаковым числом знакомых среди этих пяти человек (возможно, эти двое ни с кем не знакомы).

Решение. Число знакомых у каждого может быть от 0 до 4, то есть количество различных значений этого числа равно числу людей. Но если есть человек, у которого 0 знакомых, то есть он ни с кем не знаком, то не может быть человека с 4 знакомыми, то есть знакомого со всеми. Значит, число различных значений знакомств меньше числа людей, и по принципу Дирихле найдутся два человека с одинаковым числом знакомых.

Принцип Дирихле можно отнести и к непрерывному случаю.

Пример 4.3. На планете Земля океан занимает больше половины площади поверхности. Докажите, что есть две диаметрально противоположные точки, принадлежащие мировому океану.

Решение. Отрази океан симметрично относительно центра Земли. Так как сумма площадей океана и его образа превышает площадь земной поверхности, то найдется точка, принадлежащая и океану, и его образу. Эта точка и симметричная к ней и являются искомыми.

Упражнения

В клетках таблицы n×n расставлены числа от 1 до n2. Докажите, что найдутся две такие соседние клетки (имеющие общую вершину или общую сторону), что стоящие в них числа отличаются не меньше, чем на n + 1. Кот Базилио обещал Буратино открыть великую тайну, если он составит чудесный квадрат 6×6 из чисел –1, 0, 1 так, чтобы суммы по всем строкам, столбцам и большим диагоналям были различны. Помогите Буратино. На карьере добыли 36 камней. Их веса составляют 490 кг, 495 кг, 500 кг, … … , 665 кг (арифметическая прогрессия). Можно ли увезти эти камни на семи трехтонных грузовиках? В равностороннем треугольнике со стороной 2 поставили 5 точек. Докажите, что найдутся две из них, расстояние между которыми не превышает 1. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100. В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей. Каждая из 9 прямых разбивает квадрат на два четырехугольника, площади которых относятся как 2:3. Докажите, что по крайней мере три из этих прямых проходят через одну точку. В некотором королевстве было 32 рыцаря. Некоторые из них были вассалами других (вассал может иметь только одного сюзерена, причем сюзерен всегда богаче своего вассала). Рыцарь, имевший не менее четырех вассалов, носил титул барона. Какое наибольшее число баронов могло быть при этих условиях? (В королевстве действовал закон: вассал моего вассала – не мой вассал). Ограниченная фигура на плоскости имеет площадь S > 1. Докажите, что ее можно сдвинуть на целочисленный вектор так, чтобы исходная фигура и ее образ пересекались.