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

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

6 тур. 22 апреля 2011 г.

1.  Найдите сумму и радиус сходимости степенного ряда , если коэффициенты ряда связаны рекуррентным соотношением an+1 = an + an–1 – 1, a0 = 1, a1 = 3. (по мотивам)

2.  (аутсайдеры) На плоскости отмечены n точек, никакие три из которых не лежат на одной прямой. При каком наименьшем n из них гарантированно можно выбрать 4 точки, лежащие в вершинах выпуклого четырехугольника? (Эрдеш)

2 (лидеры). На плоскости отмечены 9 точек, никакие три из которых не лежат на одной прямой. Докажите, что из них можно выбрать 5 точек, лежащих в вершинах выпуклого пятиугольника. Докажите, что из восьми точек такой выбор не всегда возможен. (Эрдеш)

3.  Пусть А(x) =, В(x) =. Вычислите . ()

4.  Точка K на медиане ВМ треугольника АВС такова, что ÐAKM = ÐMBC. Докажите, что AK = BC.

(Из задач минских олимпиад; МШ 7-03)

5.  Пусть p0, p1, … , pn; q0, q1, … , qn – попарно различные простые натуральные числа, n > 1. Докажите, что многочлен не имеет рациональных корней. ()

6.  Каждый из n пассажиров купил по билету на n-местный самолет. Первой зашла сумасшедшая старушка и села на случайное место. Далее, каждый вновь зашедший занимает свое место, если оно свободно; иначе занимает случайное. Какова вероятность того, что последний пассажир займет свое место? ()

7.  На доске написаны числа 1, 2, … , 10. Двое играющих по очереди стирают по два числа и записывают вместо них модуль их разности. Задача первого – добиться, чтобы последнее оставшееся число было наибольшим, второго – наименьшим. Какое наибольшее число может обеспечить себе первый игрок? ()

8.  Для действительных чисел a, b, c выполняются равенства a + b + c = 2, ab + bc + ca = 1. Найдите все значения, которые может принимать произведение abc. (от Эвнина)

9.  На вечеринку пришли 100 человек. Через 5 минут те, у кого не было знакомых среди пришедших ушли. Еще через 5 минут те, у кого был ровно один знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, … , 99 знакомых среди оставшихся к моменту их ухода. Какое наибольшее число людей могло остаться в конце? (С. Берлов, олимпиада 2003 г.)

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

1. Имеем an+1 – an – an–1 = –1. Пусть S = 1 + 3x + a2x2 + …, тогда –Sx = –x – a1x2 – …; –Sx2 = –a0x2 – … Сложив эти равенства, при всех степенях х, начиная со второй, получим коэффициент –1. Поэтому

S(1 – x – x2) = 1 + 2x – x2 – x3 – … – xn– … ==;

S =.

Радиус сходимости ряда

R = =;

== 1 + R.

Отсюда .

2(аутсайдеры). Очевидно, при п = 4 это не всегда возможно. Покажем, что это всегда возможно при п = 5. Соединим все точки попарно отрезками. Внешний контур образует выпуклый многоугольник. Если это пятиугольник или четырехугольник, то выбор ясен. Если же это треугольник, то две оставшиеся точки находятся внутри него. Проведем через них прямую. Она пересечет две стороны треугольника. По одну сторону от прямой окажется одна вершина треугольника, по другую – две. Эти две вершины вместе с двумя внутренними точками и являются искомыми.

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

Первый случай: внутренний многоугольник является треугольником АВС. Тогда внутри него не менее двух оставшихся точек М и N. Проходящая через них прямая пересекает две стороны треугольника АВС, например, АВ и АС. Проведем штрихпунктирные линии, как на рисунке а). Они разбивают область вне треугольника АВС на три части, в которых содержатся вершины внешнего многоугольника. Либо одна из этих вершин окажется в области, примыкающей к отрезку ВС, либо в какой-то из двух других областей окажутся две вершины. В каждом случае упомянутые вершины образуют искомую пятерку точек с точками, задающими границу соответствующей области.

Второй случай: внутренний многоугольник является четырехугольником ABCD, а внешний – треугольником. Тогда внутри четырехугольника находятся еще две точки М и N. Пусть прямая MN пересекает две смежные стороны четырехугольника, например, АВ и АD, см. рис. б). Тогда точки B, C, D окажутся по одну сторону от прямой MN, и пять точек M, N, B, C, D являются искомыми. Если же прямая MN пересекает две противоположные стороны четырехугольника, например, АВ и СD,то проведем штрихпунктирные линии, как на рис в). Они разбивают область вне четырехугольника на четыре части. Либо хотя бы одна вершина внешнего треугольника попадет в часть, примыкающую к стороне AD или ВС, либо две вершины попадут в часть, примыкающую к стороне АВ или CD. Как и в первом случае, это даст искомую пятерку точек.

Третий случай: и внешний, и внутренний многоугольники являются четырехугольниками. Пусть ADCD – внутренний, KLMN – внешний четырехугольник и О – последняя точка. Проведем во внутреннем четырехугольнике какую-нибудь диагональ. Она разделит четырехугольник на два треугольника. Последняя точка О окажется внутри одного из них, например, треугольника АВС. Проведем из точки О лучи через точки А, В, С. Они разделят область вне треугольника на три части. Внутри одной из них окажутся две вершины внешнего четырехугольника, которые и войдут в искомую пятерку.

Восемь точек, из которых нельзя выбрать пять, лежащих в вершинах выпуклого пятиугольника, можно расположить, как на рис г) – в вершинах внешнего и внутреннего четырехугольников.

3. Несобственный интеграл, через который определяется функция В(х), очевидно, сходится. Численно он равен площади фигуры, расположенной на рисунке выше оси абсцисс. Эта площадь положительная. Правая граница t = x.

Функция , через которую определяется А(х), обратная к . Графики этих функций симметричны относительно прямой y = t. Верхняя и правая границы, определяющие фигуры, задаваемые интегралами, также симметричны. Поэтому интегралы, определяющие функции А(x) и В(x), равны по модулю и противоположны по знаку. Причем это верно не только для отрицательных, но и для всех х. Поэтому А(x) = –В(x). А так в искомом интеграле подынтегральная функция нечетная, то этот интеграл равен 0.

4. Пусть ÐAKM = ÐMBC = a. По теореме синусов из треугольника АВМ имеем ; из треугольника СВМ имеем . А так как АМ = СМ и sinÐAMB = sinÐCMB, то AK = BC.

5. Умножим многочлен на произведение q0q1…qn. Получим многочлен с целыми коэффициентами. Для простого числа qn выполняются условия критерия Эйзенштейна, поэтому многочлен неприводим над полем рациональных чисел и не имеет рациональных корней.

6. Пусть событие An означает, что последний пассажир занял свое место. Докажем индукцией по n, что при n > 1 P(An) = 0,5. Очевидно, P(A2) = 0,5: старушка может занять свое или чужое место с равной вероятностью. Делаем индуктивное предположение, что при n < k P(An) = 0,5, и доказываем, что P(Ak) = 0,5. Возможны три гипотезы:

H1 – старушка села на свое место;

H2 – старушка села на место последнего пассажира;

H3 – старушка села на любое другое место.

Имеем P(H1) = P(H2) = 1/n; P(H3) = (n – 2)/n. Соответствующие условные вероятности: = 1, = 0. В третьем случае пассажир, место которого заняла сумасшедшая старушка, сам будет играть ее роль: своим для него будет считаться ее место. Поэтому по индуктивному предположению = 0,5. Тогда по формуле полной вероятности P(Ak) = .

7. Сумма исходных чисел нечетная, при каждой операции четность суммы не меняется. Значит, последнее оставшееся число будет нечетным. Второй игрок может обеспечить, чтобы это число было не больше 3. Для этого разбивает числа на пары в порядке возрастания. В начале разность между числами в паре равна 1. Если первый игрок задействует числа из одной пары, то второй в ответ задействует другую пару (максимальную на данный момент, но это не существенно). Получившиеся разности образуют новую пару, разность в которой равна 0, то есть не превышает 1. Если первый задействует два меньших или два больших числа из двух пар, то второй задействует два других числа из этих же пар, и возникнет та же ситуация. Если первый будет продолжать в том же плане, то второй добьется того, что последнее число будет равно 1. Поэтому первому следует на своем ходу задействовать большее число из одной пары и меньшее из другой. Тогда если второй задействует два других числа из этих же пар, то получившиеся разности будут отличаться уже на 2. На следующем ходу первый действует таким же образом с получившейся парой и одной из прежних, и получившиеся разности будут отличаться уже на 3. Продолжая таким же образом, за четыре двойных хода первый добьется получения двух чисел, отличающихся на 5, и последнее число будет равно 5. Но дело в том, что после первого хода первого игрока второй может добиться, чтобы получились четыре пары с разностями, не превышающими 1. Например, пусть первый стер числа а и b, где a < b, и получившаяся их разность с оставшимися числами образовала три промежутка, в каждом из которых нечетное количество чисел. Эти промежутки будут разделены числами а и b. Но тогда второй стирает числа b – 1 и b + 1. Их разность равна 2, она в любом случае подсоединится к первому промежутку. Аналогично разбираются другие ситуации, возникшие после первого хода. В каждом случае своим ходом второй игрок может добиться, чтобы образовались промежутки, в каждом из которых будет четное количество чисел. Возможно, в этих промежутках некоторые числа будут повторяться. В итоге все числа разбиваются на новые пары, отличающиеся не более чем на 1. Тогда за следующие три хода первый не сможет добиться разности, большей 4, а тогда в силу нечетности последняя разность не превысит 3.

Первый игрок может добиться, чтобы последнее число было не меньше 3. Первым ходом он стирает 2 и 3, записав вместо них 1. В результате получаются два промежутка: в нижнем два числа 1, в верхнем семь чисел, которые больше 3. Если второй своим ходом стирает два числа из верхнего промежутка и разность присоединяется к нижнему промежутку, то первый стирает два меньших из оставшихся чисел верхнего промежутка. В результате в верхнем промежутке останутся три числа, не меньших 6, и дальнейшая стратегия первого – оставлять их количество нечетным.

Пусть теперь второй своим первым ходом оставляет числа разбитыми на пары соседних или равных. Например, 10 и 4 заменяет на 6, или 10 и 7 заменяет на 3. Тогда первый действует, как в начале доказательства.

8. По теореме Виета многочлен третьей степени, корнями которого являются числа a, b, c, имеет вид x3 – 2x2 + x – d, где d – значение выражения abc. У этого многочлена существуют три корня (возможно, кратных), когда его график имеет две или три общие точки с осью абсцисс. Найдем экстремумы графика f(x) = x3 – 2x2 + x. Точки экстремумов х = 1/3 и х = 1; fmax = f(1/3) = 4/27; fmin = f(1) = 0. График можно сдвигать вдоль оси ординат на d так, чтобы ось абсцисс оставалась между максимумом и минимумом, – тогда трехчлен будет иметь три корня. Поэтому возможные значения d принадлежат отрезку [0; 4/27].

9. Все остаться, очевидно, не могли. Предположим, что ушел всего один человек А, у которого было k знакомых. Так как остальные остались, то у каждого из них было изначально k + 1 знакомых, а когда ушел А, осталось k знакомых среди оставшихся. Значит, все они были знакомы с А, то есть у А было 99 знакомых. Тогда у остальных было по 100 знакомых, – перебор.

98 человек могли остаться, если все были знакомы со всеми, кроме двух человек А и В, не знакомых друг с другом. Тогда А и В ушли, когда настал момент ухода тех, у кого было ровно 97 знакомых среди оставшихся. После этого у всех оставшихся осталось по 97 знакомых, и они момент ухода пропустили и остались на вечеринке.