Двадцать шестой Турнир Городов, 2004-2005. Предварительные решения.

     1. Ответ. В неравностороннем треугольнике подходят точка
пересечения высот, точка пересечения биссектрис и центр опи-
санной окружности (они будут различными). В равностороннем
треугольнике проведем любую высоту, тогда подойдут любые три
точки на этой высоте, из которых основание (на которое опущена
высота) видно под рациональным углом.

     2. Ответ: обязательно.
     Рассмотрим треугольники CA'A и CB'B. В этих треугольниках
A'A=B'B по условию, CB'=CA' как касательные к окружности, а
угол C - общий. Тогда углы CAA' и CBB' либо равны, либо допол-
няют друг друга до 180 град. Последнее невозможно, так как
сумма этих двух углов меньше суммы углов A и B треугольника
ABC, а значит меньше 180 град. Поэтому углы CAA' и CBB' равны,
а значит и треугольники CAA' и CBB' равны, откуда AC=BC. Ана-
логично получаем, что BC=BA, то есть треугольник ABC равнобед-
ренный.

     3. Ответ: 60.
     Пример: расставим коней во все клетки кроме четырех кле-
ток центрального квадрата 2*2. Несложно проверить, что каждый
конь будет бить не более семи из остальных.
     Докажем теперь, что большее число коней расставить не
удастся. Рассмотрим центральный квадрат 4*4. Нетрудно прове-
рить, что любая клетка доски может атаковаться одновременно
максимум четырьмя конями, расположенными внутри этого квадра-
та.
     Если в центральном квадрате 4*4 расставить 12 коней или
меньше, то всего коней будет не больше 60.
     Пусть в центральном квадрате 4*4 расставлено не меньше 13
коней. Тогда каждый из них атакует 8 клеток доски, одна из ко-
торых свободна. Тогда всего свободных клеток не меньше 13:4
(так как каждая свободная клетка атакуется не более чем че-
тырьмя конями квадрата), то есть не меньше 3,25. Значит сво-
бодных клеток минимум 4, и снова общее количество коней не
больше 60.

     4. Заметим, что среднее арифметическое чисел x-y и x+y
равно среднему геометрическому чисел x/y и xy (и равно x).
     С помощью перебора найдем на доске два числа a и b, сред-
нее арифметическое которых равно среднему геометрическому ос-
тавшихся чисел c и d, то есть (a+b)/2 = корень из cd.
     Докажем, что в паре {a, b} одно число равно x-y, а другое
равно x+y.
     Рассмотрим равенство {(x-y)+(x+y)}/2 = корень из
{(x/y)*(xy)}.
     Если мы поменяем в нем местами одно из чисел x-y, x+y с
одним из чисел x/y, xy, то равенство не изменится только в
случае совпадения меняемых чисел: иначе одна из частей равенс-
тва увеличится, а другая - уменьшится.
     Поэтому пара {a, b} - это либо пара {x-y,x+y}, либо пара
{x/y,xy}. Последнее невозможно, так как тогда среднее геомет-
рическое чисел c и d будет равно корню из {(x+y)(x-y)}, что
меньше x, а среднее арифметическое чисел x/y и xy не меньше их
среднего геометрического, то есть не меньше x - противоречие.
     Значит в паре {a,b} одно число равно x-y, а другое равно
x+y, откуда однозначно находим x (как среднее арифметическое a
и b) и y (как разность большего из чисел a, b и числа x).

     5. Проведем к окружности, вписанной в треугольник ABK,
касательную, параллельную AK (но отличную от AK), пусть она
пересечет сторону BC в точке M1. Аналогично, проведем к ок-
ружности, вписанной в треугольник ACK, касательную, параллель-
ную AK (но отличную от AK), пусть она пересечет сторону BC в
точке N1. Тогда M1M:MK = KN:NN1 (из подобия), откуда
MM1*NN1= KM*KN. Но BM>MM1, CN>NN1, и значит BM*CN>KM*KN.

     6. Пусть всего сыра 50 (фунтов). Играют I и II. R1, R2
- результаты I и II , D = R1-R2. Ясно, что после разреза ра-
ботает жадный алгоритм. Поэтому нарез N(a,b) = {10,10-a,10-b,
10+a,10+b} дает R1=30, а R2=20. Кроме того, при нарезе {a,b1
>= b2, c1 >= c2} R1 >= a+b2+c2.
     Всюду далее считаем x <= y, a <= b <= c. Покажем, как за
I получить R1 >= 30 или D >= 10.
     Ход 1: делим {30, 20}. На любой ответ I может получить
одну из двух позиций: K(a)={20, 10+a, 10, 10-a} (где a<5) или
L(a)={20+a, 10-a, 10+a, 10-a} (где a >= 5).
     Случай K. Если II делит 20, будет N(a,b). Если II делит
10-a или 10+a так, что б'ольшая часть >=10, то R1>= 20+10=30.
Если II делит 10 = x+y, то x <= 5 <= 10-a, y <= 10+a, поэтому
R1 >=20+x+y=30. Если II делит 10+a=x+y, где y<=10, то x>= a,
нарез {20, y>= x, 10+a >= 10-a}, поэтому R1> = 20 + x+10-a >=
20+a+10-a = 30.
     Случай L. II вынужден делить 20+a=x+y, нарез {y, 10+a >=
x, 10-a >= 10-a}, поэтому R1 >= y+x+10-a=20+a+10-a=30.
     Покажем, как играть за II чтобы получить R2 >= 20 или
D<= 10. Пусть первый ход был {x,y}. Если x<10 или x>20, то II
делает {a, b, b}, где a<10, и, повторяя ходы на равных кусках,
добивается D<= a<10. Иначе II делает {p,q,20}, где p и q>=10.
Если в ответ I режет кусок 20, то II делает N(a,b). Иначе пе-
ред II позиция {a, b, с, 20}, где a+b+c=30. Он ходит {a, b, с,
b, 20-b}. Ясно, что a+b<= 20, b+c>= 20, поэтому a<=20-b<= c и
R2=b+(20-b)=20.

     7. Для удобства условимся называть прямоугольники, равные
A, кирпичами. Пусть A имеет размеры a1 * a2, а B имеет раз-
меры b1 * b2. Пусть P - прямоугольник, подобный B, сложенный
из кирпичей. Тогда он имеет размеры (p*a1 + q*a2) * (r*a1+s
*a2), где p,q,r,s - некоторые целые числа.
     Предположим сначала, что отношение сторон кирпича рацио-
нально: a1/a2=m/n, где m и n - целые числа. Тогда и отноше-
ние сторон прямоугольника P рационально: (p*a1+q*a2)/(r*a1+
s*a2)= (p*(a1/a2)+q)/(r*(a1/a2)+s) (числитель и знамена-
тель последней дроби рациональны). Значит (из подобия P и B) и
отношение сторон прямоугольника B тоже рационально: b1/b2 =
k/l, где k и l - целые числа. Но тогда из k*l прямоугольников,
равных B, можно будет сложить квадрат. (Для этого располагаем
подряд l прямоугольников, равных B, чтобы получился прямоу-
гольник с вертикальной стороной b2 и горизонтальной стороной
l*b1; под ними - еще один такой же ряд из l прямоугольников,
и так далее - всего k рядов. Получаем квадрат со стороной
l*b1=k*b2). Из таких квадратов можно будет сложить прямо-
угольник, подобный A (берем m*n квадратов и укладываем рядами
по m квадратов, всего n рядов).
     Пусть теперь отношение a1/a2 сторон кирпича иррацио-
нально.
     Докажем лемму: все кирпичи, из которых сложен прямоуголь-
ник P, ориентированы одинаково (то есть все их длинные стороны
параллельны друг другу).
     Заметим сначала, что если какое-то число представимо в
виде z*a1+t*a2, где z и t - целые числа, то числа z и t оп-
ределяются однозначно (если z*a1+t*a2=z'*a1+t'*a2, где z'
и t' - целые, то (z-z')*a1=(t-t')*a2, и при z не равно z',
отношение a1/a2 будет рациональным, что противоречит предпо-
ложению, а значит z=z', но тогда и t=t').
     Пусть P имеет вершины P1, P2, P3, P4. Расположим P
так, чтобы его сторона P1P2 была вертикальной, а сторона P2
P3 - горизонтальной, причем P1 - левый нижний угол прямоу-
гольника P. Пусть к этому углу примыкает кирпич, длинная сто-
рона которого горизонтальна. Рассмотрим самый большой прямоу-
гольник вида P1UVW, который составлен из кирпичей, все
длинные стороны которых горизонтальны (U лежит на P1P2, W -
на P1P4).
     Пусть точка V лежит внутри P. Рассмотрим кирпичи, приле-
гающие к стороне UV. Их длинные стороны не могут быть все го-
ризонтальны: иначе прямоугольник PUVW не самый большой. Анало-
гично не могут быть горизонтальными все длинные стороны
кирпичей, примыкающих к стороне VW.
     Если кирпичи, примыкающие к стороне UV, не вылезают за
пределы стороны UV вправо, получим тогда, что длина стороны UV
двумя способами представляется в виде z*a1+t*a2 с целыми z и
t. Значит они вылезают вправо. Но тогда кирпичи, примыкающие к
стороне VW, не вылезают за пределы стороны VW вверх, и мы по-
лучаем, что длина стороны VW двумя способами представляется в
виде z*a1+t*a2 с целыми z и t. Противоречие.
     Случай, когда точка V лежит на границе прямоугольника P,
но не в вершине P3, приводится к противоречию аналогично.
     Значит V совпадает с P3, и лемма доказана.
     Но тогда отношение сторон прямоугольника B равно (z*a1)/
(t*a2), где z и t - целые. Пусть для определенности это b1/
b2. Тогда (t*b1)/(z*b2) =a1/a2, и мы сможем получить пря-
моугольник, подобный A, расположив прямоугольники, равные B,
рядами так, что все их стороны b1 горизонтальны, в каждом ря-
ду t прямоугольников, всего рядов z.

     1. Пусть d не равное 0 - период функции h (то есть, h(x)=
h(x+d) при любом x).
     Заметим сначала, что k не равно 0 (так как иначе
f(x)=h(x), откуда f(0)=f(d), а значит 0=g(f(0))=g(f(d))=d -
противоречие.
     Заметим теперь, что функция f принимает все значения: по
условию f(g(y)=y для любого y (значение y принимается в точке
g(y)).
     Очевидно, что g(y)=y/k + (g(y)-y/k). Функция y/k линей-
ная, поэтому достаточно доказать, что функция g(y)-y/k перио-
дическая. Обозначим эту функцию s(y) и докажем, что kd - пери-
од этой функции.
     Заметим сначала, что x=g(f(x)) и
   x+d=g(f(x+d))=g(k(x+d)+h(x+d))=g(kx+kd+h(x))=g(f(x)+kd).
     Обозначив f(x) за y получаем, что g(y)+d=g(y+kd), причем
последнее равенство верно для любого y (так как f(x) принимает
все значения). Но тогда
   s(y+kd)=g (y+kd)-(y+kd)/k=g(y)+d-(y/k+d)= g(y)-y/k=s(y),
     то есть s(y) - периодическая (с периодом kd), что и тре-
бовалось доказать.

     2. Ответ: числа m и n оба не меньше 9, причем модуль их
разности не равен 9.
     Пусть хотя бы одно из чисел m и n меньше 9 (например, m).
Тогда если взять кучу из m+1 камня, первый вынужден будет пер-
вым ходом взять 1 камень (так как m+1<10), после чего второй
берет m камней и выигрывает - противоречие с условием. Значит,
и m, и n не меньше 9.
     Пусть теперь m-n=9. Возьмем кучу, в которой m+1=n+10 кам-
ней. Если первый берет 1 камень, второй берет m и выигрывает;
если же первый берет 10 камней, второй берет n и выигрывает -
противоречие с условием. Значит, m-n не равно 9, и аналогично
n-m не равно 9.
     Докажем, что при остальных значениях m и n первый выигры-
вает. Для этого достаточно показать, что при любом количестве
камней в куче первый может сделать ход так, чтобы в куче оста-
лось число камней, отличное и от m, и от n.
     Пусть в куче k камней, и ход первого.
     Если k<=10, то первый выигрывает одним ходом (вычитая 10,
если k=10, или 1, если k<=9).
     Пусть k>10. Первый может оставить в куче либо k-1 камень,
либо k-10. Если в одном случае получится m, а в другом - n,
модуль разности между m и n будет равен 9 - противоречие. Зна-
чит, первый сможет сделать ход так, чтобы первый после этого
не выиграл одним ходом.
     Число камней в куче будет уменьшаться, и в итоге первый
выиграет.

     3. Смотрите решение задачи 4 младших классов.

     4. Ответ: окружность с центром O и радиусом
(R2-d2)/(2r), где R и r - радиусы исходных окружностей
(большой и маленькой соответственно), d - растояние между их
центрами (то есть OI).
     Пусть M - середина хорды AB, H - основание перпендикуля-
ра, опущенного из I на OM, X - центр описанной окружности тре-
угольника IAB. Тогда XB2=XM2+MB2=XM2+R2-OM2,
XI2=IK2+XK2=(d2-(OM-r)2)+(XM+r)2. Но XB=XI (как радиу-
сы), и, приравнивая полученные для XB и XI выражения, получаем
R2=d2+2r(OM+XM), то есть OX=(R2-d2)/(2r) - не зависит от
выбора хорды AB. Нетрудно проверить, что все точки окружности
с центром O и радиусом OX подходят.

     5. Смотрите решение задачи 7 младших классов.

     6. Примем угол (180 град)/n за 1, тогда сумма углов треу-
гольника равна n. Будем описывать треугольники тройками углов.
Разделим все возможные разрешенные треугольники на присутству-
ющие (в виде частей на столе) и отсутствующие. Пусть a - наи-
меньший из углов отсутствующих треугольников. Выберем все от-
сутствующие треугольники с углом a, отметим в них по одному
углу a, а остальные углы в них назовем добавочными (некоторые
добавочные тоже могут быть равны a). Выберем среди добавочных
угол b - наибольший из кратных a (если такие есть) или просто
наибольший (если кратных a нет). Итак, отсутствует треугольник
(a,b,c). Докажем, что треугольник (a, a+b, n-2a-b) присутству-
ет. Сперва заметим, что угла a+b среди добавочных нет - иначе
мы бы выбрали его вместо b. Достаточно показать что n-2a-b>0.
Поскольку по выбору a угол c>= a, то n-2a-b=(a+b+c)-2a-b=c-a>=
0. Равенство возможно, только если c=a. Но тогда среди доба-
вочных есть кратные a, значит и b кратен a, откуда и простое n
кратно a - противоречие.
     Разрежем присутствующий треугольник (a, a+b, n-2a-b) так,
чтобы угол a+b разбился на части a и b, причем часть b попала
в меньший треугольник с углом b. Получим меньшие треугольники
(b,a,...) и (a, n-2a-b,...), то есть конечно же (b,a,c) - ис-
комый отсутствовавший, и (a, n-2a-b,a+b) - одинаковый разре-
занному.

     7. Сделаем инверсию с центром в точке O такую, что первая
окружность переходит в равную второй. Вторая, соответственно,
перейдёт в равную первой. Тогда, с одной стороны, лучи OF и OE
перейдут в себя, с другой - мы имеем картинку, симметричную
исходной относительно биссектрисы угла AOD, а значит, она же
биссектриса угла EOF, откуда AOE=DOF.