Приемы решения нестандартных математических задач: непрерывность, принцип крайнего, раскраска, принцип Дирихле, аналогия, инвариант, минимальный контрпример.
Пример .
На бесконечном листе клетчатой бумаги играют двое, ходят по очереди. Своим ходом можно выбрать любую незакрашенную сторону клетки и покрасить ее в любой цвет (число цветов неограничено). Первый выиграет, если найдется замкнутая ломаная, где все звенья окрашены в разные цвета. Может ли второй ему помешать?
Анализ и решение. Ломаных бесконечно много, и зада- ча второго «испортить все» кажется нереальной, тем более, что любое звено можно обойти. Однако ложка дегтя портит бочку меда. Присмотримся: нет ли у всех ломаных общего свойства, которое можно было бы объявить узким местом? Ну, поворачивать они все должны, чтобы замкнуться... Ага, повороты могут быть разные, но среди них обязательно найдется поворот в виде буквы Г (речь, конечно, идет о паре соседних звеньев: одно выходит из общей вершины вправо, другое — вниз. А еще бывают L-повороты и два по- ворота, для которых букв нет, а именно, пары вверх-влево и вниз-влево). Вот вам и узкое место! Испортим все Г-повороты: разобьем все звенья на Г-пары, и как только первый закрасит одну половинку пары, второй должен покрасить вторую половинку в тот же цвет.
Пример . Какое наименьшее число коней может по- бить все поля шахматной доски? (Считаем, что поле под собою конь тоже бьет.)
Указания. Попробуйте, воспользовавшись результатом и раскраской из предыдущего примера, построить требуе- мую расстановку из 12 коней. При этом надо обязательно побить все покрашенные поля, одновременно стараясь побить максимум из еще не побитых полей. Практично расставлять коней тройками и использовать симметрию: тогда достаточно убедиться, что побиты поля одного из угловых квадратов 4 × 4. Не стоит только пытаться по- бить весь угловой квадрат стоящими в нем конями, можно и нужно принять «помощь извне».