VII Всероссийский студенческий турнир математических боёв 3 тур. 19 апреля 2011 г

VII Всероссийский студенческий турнир математических боёв

3 тур. 19 апреля 2011 г.

1.  Имеются m(m – 1) карандашей m цветов, каждый цвет встречается не менее одного и не более m раз. Карандаши разложены поровну в m коробок. Докажите, что из каждой коробки можно выбрать по одному карандашу так, чтобы они были разных цветов. ()

2.  Пусть функция f(x) непрерывно дифференцируема на [0; 1] и < 2f(1). Докажите, что > 0. («Всеармейские олимпиады», №9.33)

3.  Восстановите прямоугольный треугольник АВС (ÐС = 90°) по вершинам А, С и точке на биссектрисе угла В.

(«Олимпиады имени »)

4.  Докажите, что для любого многочлена f(x) третьей степени с действительными коэффициентами существует такое число а, что многочлен f(x) – ах2 имеет три корня, образующих арифметическую прогрессию (в частности, возможно совпадающих). ()

5.  Определим на множестве нечетных натуральных чисел отображения h2 и h–2 по следующему правилу. Пусть имеем каноническое разложение числа п на простые множители: n = . Полагаем по определению
nh2 =; 1h2 = 1; nh–2 =; 1h–2 = 1. Рассмотрим композицию h = h2h–2. Назовем h-высотой числа n наименьшее натуральное m такое, что композиция nhm = 1.Докажите, что если для числа n h-высота существует, то m = 1. ()

6.  Имеются 2n шаров с числами 1, … , n, каждое число встречается по два раза. Эти шары случайным образом раскладываются по два в n урн. Из каждой урны вынимается один шар. Какова вероятность, что на вынутых шарах все числа различные? ()

7.  Прямоугольник m´n разбит на сетку единичных квадратов. Двое по очереди строят маршрут по линиям сетки, закрашивая по одному звену сетки. Очередное звено должно выходить из конца предыдущего. Запрещается проводить звено в уже пройденную ранее вершину сетки. Если ходить некуда, игра прекращается. Начинается маршрут из левого нижнего угла А прямоугольника. Задача первого игрока – добиться, чтобы маршрут дошел до правого верхнего угла В, задача второго – ему помешать. У кого есть выигрышная стратегия? ()

8.  Натуральное число n > 1 таково, что десятичная запись числа 9997п содержит только нечетные цифры. Найдите минимальное возможное значение n. (Казахстан, олимпиада 2010, 11 класс)

9.  Разрежьте равнобедренный прямоугольный треугольник на шесть попарно различных равнобедренных прямоугольных треугольников. (Московские математические олимпиады)

Решения задач

1. Каждой коробке поставим в соответствие множество цветов карандашей, содержащихся в этой коробке. В любых k коробках, где k < m, вместе содержится k(m – 1) карандашей. Значит, число различных цветов не меньше , следовательно, не меньше k. По теореме Холла построенное множество имеет систему различных представителей.

2.== f(1)> f(1)= f(1)= 0.

3. По точкам А и С восстанавливаем сторону АС и строим перпендикулярную ей прямую, на которой расположена точка В. Пусть D – точка, лежащая на биссектрисе угла В. Строим окружность с центром в D, касающуюся прямой ВС. Вторая сторона треугольника, выходящая из точки В, также должна касаться этой окружности. Восстанавливаем эту сторону, проведя касательную к окружности из точки А. Тем самым треугольник АВС будет восстановлен. При этом нам подойдет только одна из двух возможных касательных. Построение возможно, если точки А и D оказываются с одной стороны от прямой ВС и диаметр окружности меньше отрезка АС. Если они равны, то построение невозможно; если диаметр окружности больше отрезка АС, то точка D окажется не на биссектрисе, а на ее продолжении за сторону ВС. Если А и D окажутся с разных сторон от прямой ВС, то, в зависимости от взаимного расположения окружности и прямой АС точка D окажется на продолжении биссектрисы за вершину В или на биссектрисе внешнего угла В.

4. График f(x) имеет две ветви, направленные в противоположные стороны. Пусть сначала f(0) ¹ 0, например, f(0) < 0. Рассмотрим ветвь графика, направленную в –¥, и возьмем на ней точку С1. Парабола у = ах2 однозначно определяется любой своей точкой, отличной от вершины. Проведем параболу через С1. График у = f(x) круче, чем график параболы, значит, ветвь параболы, проходящая через С1, пересечется с графиком у = f(x) еще в одной точке С2 (возможно, совпадающей с С1). Можно считать, что если точки различны, то С2 ближе к началу координат, чем С1. Вторая ветвь параболы пересечется с графиком у = f(x) в точке С3.

Если двигать точку С1 к началу координат, точка С2 будет приближаться к ней, расстояние между их абсциссами будет стремиться к 0. Расстояние между абсциссами С2 и С3 будет увеличиваться. Значит, в некотором положении оно будет больше, чем расстояние между абсциссами С2 и С1. Если из этого положения двигать С1 в обратную сторону, то расстояние между абсциссами С1 и С2 будет неограниченно увеличиваться, а между абсциссами С2 и С3 уменьшаться. Значит, в некотором положении эти расстояния станут равны. Соответствующие абсциссы являются корнями многочлена f(x) – ах2.

Случай, когда f(0) = 0, мало отличается от рассмотренного. Здесь точка С1 выбирается произвольно, а С3 совпадает с началом координат. Особая ситуация – когда f(x) имеет горизонтальную касательную в начале координат, то есть двойной корень 0. В этом случае f(x) = x2(x – c) для некоторого с. Тогда можно взять а = –с, и получим f(x) – ах2 = х3.

5. Имеем (n1n2)h = (n1h)(n2h), поэтому утверждение достаточно доказать для простых п. Если ph = 1, то ph2 = p + 2 = 3k, так как для простых чисел только 3h–2 = 1. Отсюда p º 1(mod 3). Предположим, что для некоторого n h-высота m > 1. Пусть p – один из простых множителей в разложении числа nhm-2 (или числа n, если m = 2). Тогда ph2 = p + 2 = p1 … ps, ph = (p1 – 2)… (ps – 2), где хотя бы один из множителей не равен 1. Пусть p1 – 2 > 1, и p1 – 2 = q1 … qt. Так как qih = 1, для i = 1, … , t, то qi º 1(mod 3), тогда p1 – 2 = q1 … qt º 1(mod 3), и p1 º 0(mod 3). Но тогда p1 = 3, и p1 – 2 = 1. Противоречие.

6. Введем событие Аn – «все числа на вынутых шарах различные». Пусть Р(Аn) = Pn. Очевидно, Р1 = 1. Выразим Pk+1 через Pk. Выделим первую урну и рассмотрим две гипотезы:

H1 – шары в урне с одинаковыми числами;

H2 – шары в урне с разными числами.

Если выполняется Н1, то первая урна ни на что не влияет, и искомая вероятность равна Pk. Если выполняется Н2, то пусть в первой урне числа а и b, и вынут шар с числом а. Рассмотрим другую урну с числом b. Чтобы выполнялось Аk+1, требуется, чтобы из этой урны было вынуто число b, и вероятность этого равна 1/2. Если это произойдет, то ситуация будет равносильна тому, что исключили вторую урну и два шара с числом b, а в первой урне находились шары с числами а и с. Причем нет никаких ограничений на распределение шаров в оставшихся урнах: числа а и с могут быть равными. Поэтому соответствующая условная вероятность также равна Pk. Тогда по формуле полной вероятности получаем

Pk+1 = Р(Аk+1) = Р(H1) + Р(H2) = Pk + Pk =Pk.

Отсюда Pn = =.

7. У первого. Раскрасим вершины сетки в шахматном порядке. Пусть левый нижний угол окрашен в черный цвет. Тогда любой ход первого ведет из черной вершины в белую, второго – из белой в черную. Для описания стратегии удобно считать, что вокруг прямоугольника расположен другой прямоугольник на расстоянии 1 от сторон первого, и большой прямоугольник уже обойден до начала игры. Строящийся маршрут образует некую угловатую фигуру R. Стратегия первого заключается в том, что он проводит свое звено так, чтобы по ходу движения слева или справа от конца звена находилась уже пройденная вершина. Тогда второй не сможет пойти так, чтобы в вершине, из которой он вышел, образовался угол фигуры R. Значит, все углы фигуры R будут иметь черный цвет. Критическая ситуация в игре наступает, когда один из игроков своим ходом разделил еще не пройденную часть прямоугольника на две области. Тогда если ходит первый, то он проводит свое звено в ту область, где лежит точка В, и игра продолжается. Если же ходит второй, то он проводит маршрут во вторую область и выигрывает. В этих условиях первый всегда имеет возможность осуществить свою стратегию. Пусть своим очередным ходом первый игрок провел линию из А в В. Слева от В находится ранее пройденная вершина С. Второй может пойти из В в Н или D, Пусть для определенности он пошел в D (с Н ситуация симметрична). Пусть в вершине С (она черная) находится угол, как на рис.1. Если ситуация не критическая, то первый ходит в Е. Если же ситуация критическая, то либо в F или I есть угол, либо проведен отрезок FI. В любом случае первый имеет возможность ответить согласно стратегии.

Пусть теперь в С нет угла, как на рис.2. Тогда в Е нет угла, и линия продолжается в F. Если J свободна, то первый ходит туда. Если же вершина J уже пройдена, то в ней нет угла, и вершина I также пройдена. Тогда первый ходит в K.

8. Последняя цифра числа п нечетная. Далее, 9997п = (10000 – 3)п = 10000п – 3п. Последняя цифра перед четырьмя нулями в конце числа 10000п нечетная, и если 3n < 10000, то при вычитании эта цифра уменьшится на 1, и получится четная цифра. Значит, 3n ³ 10000, n > 3333. Наименьшее значение п, удовлетворяющее этому неравенству, это п = 3335. Это число подходит: 9997×3335 = .

9. См. рисунок.