Олимпиадные задачи по математике

Условие

В игре "Десант" две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.) 

Решение

Ответ: да, найдётся. Рассмотрим страну, карта которой изображена на рисунке (точки - города, отрезки - дороги). 

Покажем, что второй армии всегда удастся захватить хотя бы две точки A_i. Действительно, если первая армия первым ходом занимает точку на "ветке" из k точек, вторая армия должна занять соответствующую этой "ветке" точку A_i; если первая занимает A_i, то вторая - B_i; если первая выбирает точку B_i, то вторая - одну из точек A_j, соединенную отрезком с B_i. Дальнейшие действия очевидны.

Так как после прекращения боевых действий вторая армия занимает хотя бы две точки A_i, первая занимает не более k+3 точек. Поэтому доля городов, захваченных второй армией, не менее (2k+3)/(3k+6). Уже при k=1 это число больше 1/2. Заметим, что в условии задачи вместо 1/2 можно взять любое число ak число (2k+3)/(3k+6) будет больше a.

Условие

За круглым столом сидят несколько гостей. Некоторые из них знакомы между собой; знакомство взаимно. Все знакомые любого гостя (считая его самого) сидят вокруг стола через равные промежутки. (Для другого человека эти промежутки могут быть другими.) Известно, что любые двое имеют хотя бы одного общего знакомого. Докажите, что все гости знакомы друг с другом.

Решение

  Заметим, что если у человека есть знакомые, сидящие рядом друг с другом (в частности, если он знаком со своим соседом), то этот человек знаком со всеми. Докажем, что такой гость найдется. Пусть A и B — двое соседей. Если они не знакомы между собой, то их общий знакомый C знаком со всеми, так как его знакомые сидят без промежутков. В противном случае со всеми знаком человек A (по той же причине).

Итак, пусть X — гость, знакомый со всеми. Тогда его соседи тоже знакомы со всеми, так как они знакомы с X (являющимся для них соседом). Соседи этих соседей также знакомы со всеми, и так далее по кругу.

Условие

n точек соединены отрезками так, что каждая точка с чем-нибудь соединена и нет таких двух точек, которые соединялись бы двумя разными путями. Доказать, что общее число отрезков равно n - 1.

Решение

Докажем это утверждение индукцией по n. При n = 1, n = 2 утверждение очевидно. Допустим, что оно верно при n = k, тогда докажем, что оно верно и для n = k + 1. Если в графе G есть висячая вершина (т. е. вершина, из которой выходит ровно одно ребро), тогда выбросим эту вершину вместе с выходящим из неё ребром. При этом в графе останется k вершин, а также он будет удовлетворять условию, а значит, по предположению индукции в нём k - 1 ребро. Тем самым получили, что в исходном графе k рёбер. Итак, осталось доказать, что в любом графе, удовлетворяющем условию задачи, найдётся висячая вершина. Рассмотрим какой-нибудь путь в графе и будем его продолжать. Во-первых, заметим, что путь не может содержать никакую вершину более одного раза, поскольку в графе нет циклов. А во-вторых, в графе конечное число вершин, поэтому в нём найдётся вершина, из которой путь продолжить нельзя, но тогда это — висячая вершина.

Условие

На листе бумаги проведено 11 горизонтальных и 11 вертикальных прямых, точки пересечения которых называются ``узлами"", ``звеном"" мы будем называть отрезок прямой, соединяющий два соседних узла одной прямой. Какое наименьшее число звеньев надо стереть, чтобы после этого в каждом узле сходилось не более трёх звеньев?

Решение

Докажем, что необходимо стереть не менее 41 звеньев. Назовем узел внутренним, если изначально он принадлежит четырем звеньям. Внутренние звенья образуют квадрат 9×9, поэтому их количество равно 81. Для каждого внутреннего узла мы должны стереть хотя бы одно содержащее его звено, при этом каждое из таких звеньев мы посчитаем не более двух раз. Следовательно, количество стертых звеньев не менее 81/2. А поскольку это число - целое, то это количество не менее 41. Нетрудно привести пример, показывающий, что можно стереть требуемым образом ровно 41 звено. Например, можно стереть все звенья на горизонтальных прямых с номерами 2, 3, ..10 , расположенные между вертикальными прямыми с номерами 2 и 3, 4 и 5, 6 и 7, 8 и 9, а также все звенья на вертикальной прямой с номером 10, расположенные между горизонтальными прямыми с номерами 2 и 3, 4 и 5, 6 и 7, 8 и 9, 9 и 10.

Ответ

41

Условие

Сеть метро имеет на каждой линии не менее 4 станций, из них не более трёх пересадочных. Ни на какой пересадочной станции не скрещиваются более двух линий. Какое наибольшее число линий может иметь такая сеть, если с любой станции на любую можно попасть, сделав не больше двух пересадок?

Решение

По условию задачи у каждой линии есть непересадочная станция, следовательно, с любой линии метро можно попасть на любую, сделав не более двух пересадок. Фиксируем какую-нибудь линию. Заметим, что с неё можно попасть не более, чем на три линии, а с каждой из них — ещё не более, чем на две. Следовательно, всего линий не более, чем 1 + 3 + 2 ^. 3 = 10. На рисунке показана схема пересадок для десяти линий, удовлетворяющая условию (для удобства беспересадочные станции не отмечены).

Условие

Из первых k простых чисел 2, 3, 5, ..., p_k (k  5) составлены всевозможные произведения, в которые каждое из чисел входит не более одного раза (например, 3 ^. 5, 3 ^. 7 ^. ... ^. p_k, 11 и т.д.). Обозначим сумму всех таких чисел через S. Доказать, что S + 1 разлагается в произведение более 2k простых сомножителей.

Решение

Ясно, что S + 1 = (2 + 1)(3 + 1)...(p_k + 1). При k  1 каждое выражение в скобках является чётным числом, поэтому оно разлагается по крайней мере на два простых множителя. Несложные вычисления показывают, что при k = 5 число S + 1 разлагается в произведение 11 простых множителей.

Условие

Берутся всевозможные непустые подмножества из множества чисел 1, 2, 3, ..., N. Для каждого подмножества берётся величина, обратная к произведению всех его чисел. 
Найти сумму всех таких обратных величин.  

Решение

Ясно, что рассматриваемая сумма равна

(достаточно раскрыть скобки). Поэтому она равна

Ответ

n.

Условие

Для каждого трёхзначного числа берём произведение его цифр, а затем эти произведения, вычисленные для всех трёхзначных чисел, складываем. 
Сколько получится? (Пояснение: берётся произведение всех цифр трёхзначного числа, так что если хотя бы одна из цифр - ноль, то и произведение - ноль).

Решение

а) Раскроем скобки в произведении
(1 + ... + 8 + 9)(0 + 1 + ... + 8 + 9)(0 + 1 + ... + 8 + 9)
и получим искомую сумму.
б) Аналогично пункту а), достаточно раскрыть скобки в произведении
(1 + ... + 9)(0 + 1 + ... + 9)(0 + 1 + ... + 9)(0 + 1 + ... + 9).

Ответ

а) 45³; б) 45⁴.

Условие

Найти корни уравнения

1 -  +  - ... + (- 1)ⁿ = 0.

Решение

Ответ: 1, 2, ..., n. Равенство

1 -  +  - ... + (- 1)^k = (1 - 1)^k = 0

показывает, что числа k = 1, 2, ..., n являются корнями данного уравнения. Больше n корней это уравнение иметь не может, поскольку его степень равна n.