Малый Мехмат                9 класс    
  
    
            Занятие 24                21 апреля 2001 года    
  

Процессы

Во многих задачах этого листка построение нужного объекта осуществляется поэтапно. Вначале берется объект, не обладающий требуемыми свойствами, а затем он постепенно приводится к нужному виду. Задача в том, чтобы придумать тот процесс, который приведет нас к желаемому результату. Другими словами, мы должны сыграть роль папы Карло, который из бревна выстругал Буратино.

{ Пример 1.} В парламенте у каждого не более трех врагов. Докажите, что парламент можно разделить на две палаты так, что у каждого парламентария в своей палате будет не более 1 врага.

{ Решение.} Нужное разбиение парламента будем формировать постепенно, с каждым шагом все "ближе приближаясь к идеалу". Самое простое, что может придти в голову --- пересаживать парламентариев по одному. Так и будем действовать. Возьмем произвольное разбиение нашего парламента на две палаты и улучшим его: парламентария, в одной палате с которым оказалось два или три его врага, пересадим в другую палату. Тем самым общее количество пар врагов, сидящих в одной палате, уменьшилось. И так далее, шаг за шагом будем уменьшать число "недовольных" пар. Поскольку всего таких пар конечное число, то рано или поздно процесс остановится, т.е. не останется ни одного парламентария, враждующего больше чем с одним человеком из своей палаты.

{ Пример 2.} В некоторой стране из каждого города выходит нечетное число дорог. На центральной площади каждого города поднят черный или белый флаг. Каждое утро в каком-то одном из городов, у которого число соседей с флагами другого цвета больше половины, меняют цвет флага. Может ли этот процесс продолжаться бесконечно?

{ Решение.} Пусть P --- это число дорог с концами в городах с различным цветом флагов. Каждое утро это число уменьшается. Поскольку P --- это целое неотрицательное число, процесс остановится.

На заседании каждый член парламента дал пощечину ровно одному своему коллеге. Доказать, что парламент можно разбить на три фракции так, что члены одной фракции пощечин друг другу не давали.

Докажите, что если последняя цифра числа n не нуль, то можно найти такое целое число k, что в десятичной записи числа kn нет нулей.

В клетки таблицы m x n вписаны некоторые числа. Разрешается одновременно менять знак у всех чисел одного столбца или одной строки. Докажите, что несколькими такими операциями можно добиться того, чтобы суммы чисел, стоящих в любой строке и любом столбце, были неотрицательны.

Постройте правильный треугольник, все вершины которого лежат на сторонах данного (произвольного) треугольника ABC.

Запись числа состоит из нулей и единиц. Любой фрагмент "10" числа заменяют на "0001". Докажите, что рано или поздно заменять будет нечего.

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

По кругу написаны несколько целых чисел, при этом каждые два соседа отличаюся на 1. Назовем число пиком, если оно больше обоих своих соседей, и впадиной --- если оно меньше обоих соседей. Известно, что сумма всех пиков равна A, а сумма всех впадин B. Сколько чисел выписано?