VIII Всероссийский студенческий турнир математических боёв
1 тур, 6 апреля 2013 г.
1. Прямоугольная таблица заполнена числами 0 и 1. Для каждой клетки сумма чисел в этой и соседних по сторонам клетках четна. Докажите, что количество единиц в таблице четно.
2. Найдите все действительные x, для которых xn + x –n целое при любом n.
3. O – центр окружности, описанной около остроугольного треугольника ABC, AD – биссектриса. Перпендикуляр, опущенный из точки D на прямую AO, пересекает прямую AC в точке P, принадлежащей отрезку AC. Докажите, что AB = AP.
4. Вычислите интеграл 
.
5. Двое играют за шахматной доской. Первый отмечает любое поле, а далее тот, чья очередь хода, отмечает любое неотмеченное поле, в которое из предыдущего поля, отмеченного соперником, можно перейти ходом шахматного коня. Выигрывает сделавший последний ход. У кого из игроков есть выигрышная стратегия?
6. Все стенки и дно картонной коробки (без крышки) представляют собой квадраты площадью 1. Разрежьте коробку на три куска так, чтобы из них можно было сложить квадрат площадью 5.
7. На n фишках записаны числа 1, … , n. Фишки расположены в ряд в порядке возрастания. Разрешается переставить любую фишку на две позиции вправо или влево. Требуется с помощью нескольких таких перестановок расположить фишки в обратном порядке? При каких n это можно сделать?
8. В однокруговом футбольном турнире участвовало n команд. По окончании турнира оказалось, что каждая команда в своей k-ой игре забила ровно k мячей. Какое наименьшее количество ничьих могло быть в турнире? Расписание игр может составляться произвольным образом.
9. Имеются n юношей n и девушек. Каждый юноша знаком не менее, чем с половиной девушек, а каждая девушка не менее, чем с половиной юношей. Докажите, что всех юношей можно женить на знакомых девушках.
1 тур, 6 апреля 2013 г.
Решения задач
1. () Клеткам таблицы, в которых стоит 1, поставим в соответствие вершины графа. Вершины, соответствующие соседним клеткам, соединим ребром. Степень каждой вершины окажется нечетной. А так как количество нечетных вершин в любом графе четно, то количество единиц четно.
2. (Математические соревнования северных стран, 1996) Рассмотрим сначала n = 1. Решаем уравнение 
с целым k. Его решения x =
, они существуют при k ≥ 2. При k = 2 и k = –2 получаем соответственно x = 1 и x = –1. При других значениях k получаем пары чисел 
и 
, которые являются взаимно обратными. Покажем, что если целым является число , то целым будет и любое число вида 
, которое обозначим через an. Имеем
an k =
=
= an+1 + an–1,
откуда получаем рекуррентное соотношение an+1 = an k – an–1. Так как a1 и a0 = 2 являются целыми, то целыми будут и все последующие значения an.
3. (Итальянская математическая олимпиада. 1995) Пусть ÐEAC = a, тогда дуга ЕС равна 2a, дуга АС 180° – 2a
и ÐAВC = 90° – a. Из прямоугольного треугольника AFP также имеем ÐAPF = 90° – a = ÐAВC. Отсюда DABD = DAPD, и АВ = АР.
4. Пусть f(x) – подынтегральная функция. Имеем
f(–x) = 
=
=
= –f(x),
то есть функция нечетная. А так как промежуток интегрирования симметричен относительно начала координат, то искомый интеграл равен 0. (Заметим еще, что функция определена в промежутке интегрирования).
5. () У второго. Он разбивает все поля шахматной доски на пары полей, связанных ходом коня. Это можно сделать, например, разбив доску сначала на прямоугольники 2´4: в каждом таком прямоугольнике пары определяются однозначно. Стратегия второго игрока заключается в том, что на любой ход первого он отвечает ходом на парную клетку с той, которую выбрал первый игрок. Тогда на любой ход первого у второго найдется ответ.
6. () Используем развертку коробки, показанную на рисунке сплошной линией. Разрезы и сложенный квадрат показаны штриховой линией.
7. () Фишку с номером n переставляем влево, сколько возможно. Она либо окажется с краю, либо перед ней останется одна фишка, которую в этом случае переставляем вправо на два места. В результате фишка n окажется на своем месте. Затем так же ставим на свое место фишку n – 1, и так далее, пока не останутся две фишки. Они будут расположены либо в нужном порядке, либо в обратном. Покажем, как этот порядок зависит от n.
Каждая операция задает подстановку на n элементах. Эта подстановка является циклической и переставляет три элемента, значит, является четной. Значит, любая подстановка, которую можно получить несколькими операциями, будет четной. Подстановка, которую требуется получить, является произведением транспозиций, меняющих местами элементы, симметричные относительно середины ряда. Число таких транспозиций равно 
. Если это число четное, то есть n = 4k или n = 4k +1, то в результате работы алгоритма получим нужную расстановку фишек. В противном случае нужную расстановку получить невозможно.
8. (А. Чеботарев, Турниры им. ) Первая и последняя игры турнира должны быть ничейными. Покажем индукцией по n, что можно составить расписание турнира так, что остальные игры окажутся результативными. Для n = 3 утверждение тривиально. Пусть для n = k составлено нужное расписание турнира. Покажем, как составить такое расписание для n = k + 1. Сначала первые n команд сыграют все свои игры из предыдущего турнира, кроме последней. Для определенности считаем, что последняя игра этого турнира была между 1-ой и k-ой командами. Следующая игра пусть будет между (k + 1)-ой и k-ой командами, затем между 1-ой и k-ой, а далее между (k + 1)-ой и всеми остальными в любом порядке.
9. () Применим теорему Холла. Требуется доказать, что любые k юношей знакомы в совокупности не менее, чем с k девушками. При k £ n/2 это верно, так как уже у одного юноши не менее n/2 знакомых девушек. Пусть k > n/2. Тогда у любой девушки есть знакомый среди данных k юношей, значит, у этих юношей в совокупности n знакомых девушек. По теореме Холла существует паросочетание из n пар юношей с девушками.
