Выбрано 7 задач 
Убрать все задачи
В треугольнике ABC проведены высоты BB1 и CC1. Докажите, что если ∠A = 45°, то B1C1 – диаметр окружности девяти точек треугольника ABC.
На сторонах квадрата, как на основаниях, построены во внешнюю сторону равные равнобедренные треугольники с острым углом при вершине. Доказать, что получившуюся фигуру нельзя разбить на параллелограммы.
Дано n целых чисел a1 = 1, a2, a3, ..., an, причём ai ≤ ai+1 ≤ 2ai (i = 1, 2,..., n – 1) и сумма всех чисел чётна. Можно ли эти числа разбить на две группы так, чтобы суммы чисел в этих группах были равны?
Внутри треугольника ABC взята произвольная точка O и построены точки A1, B1 и C1, симметричные O относительно середин сторон BC, CA и AB. Докажите, что треугольники ABC и A1B1C1 равны и прямые AA1, BB1 и CC1 пересекаются в одной точке.
Числа 1, 2, ..., k² расположены в квадратную таблицу
На плоскости P стоит прямой круговой конус. Радиус основания r, высота — h. На расстоянии H от плоскости и l от высоты конуса находится источник света. Какую часть окружности радиуса R, лежащей в плоскости P и концентрической с окружностью, лежащей в основании конуса, осветит этот источник?
В турнире собираются принять участие 25 шахматистов. Все они играют в разную
силу, и при встрече всегда побеждает сильнейший.
Какое наименьшее число партий требуется, чтобы определить двух сильнейших игроков?
|
|
 |
Условие
В турнире собираются принять участие 25 шахматистов. Все они играют в разную
силу, и при встрече всегда побеждает сильнейший.
Какое наименьшее число партий требуется, чтобы определить двух сильнейших игроков?
Решение
Пример. Устроим турнир по олимпийской системе в пять туров: сначала сыграют 12 пар, потом 6, потом 3. Останется четыре человека, сыграют две пары, а потом победители между собой. Тем самым определится сильнейший. Он сыграл не более пяти партий.
Так как выбыло 24 человека, было сыграно ровно 24 партии. Из пяти (или менее) участников, проигравших сильнейшему, снова по олимпийской системе выделим сильнейшего. На это потребуется не более четырёх партий. Итак, 28 партий достаточно.
Оценка. Проведём турнир по какой-то схеме, позволяющей определить двух сильнейших. Ясно, что все участники, кроме самого сильного, проиграли хотя бы по одной партии (иначе сильнейшего определить нельзя).
Можно считать, что все партии играются последовательно. На каждом шаге работы алгоритма будем называть лидером участника, который пока никому не проиграл. Пусть выполнены условия:
(1) при игре лидера с не лидером всегда выигрывает лидер;
(2) при сравнении двух лидеров выигрывает тот, у кого было больше выигрышей (если выигрышей было поровну, то результат произвольный.
Такие исходы партий возможны потому, что на лидера нет никаких ограничений сверху: если его силу увеличить, то результаты предыдущих партий не изменятся.
Введём понятие подчинения лидеру. Первоначально все участники подчинены только самим себе. После партии типа (2) проигравший и все его подчинённые переподчиняются новому лидеру.
Покажем индукцией по k, что если лидер выиграл k партий, то ему подчинено (вместе с ним самим) не более 2k участников. При k = 0 лидеру подчинён только он сам.
Пусть лидер, выигравший k партий, выигрывает у кого-то в очередной раз. Тот, у кого он выиграл, выиграл не более k партий. Поэтому как выигравшему, так и проигравшему, подчинено не более 2k участников; при объединении этих двух групп получается не более 2k+1 шахматистов.
Итак, при таком течении турнира сильнейший участник выиграл не менее пяти партий, поскольку ему в итоге будут подчинены 25 > 24 участников. Среди пяти шахматистов, проигравших сильнейшему, есть только один, который больше никому не проиграл (иначе мы не будем знать второго по силе участника). Каждый из четырёх остальных проиграл не менее двух партий. Следовательно, всего было не менее 24 + 4 = 28 проигрышей, а значит, было сыграно не менее 28 партий.
Ответ
28 партий.
Замечания
Аналогично можно доказать, что для определения двух сильнейших из n участников надо провести n + m – 2 партии, где целое число m определяется неравенствами m – 1 < log2n ≤ m.
