Оценки для наборов чисел и таблиц. Принцип крайнего
Немного теории
Во многих олимпиадах встречаются задачи о сравнении по величине чисел из некоторого конечного набора, расположениях точек на прямой, оценках сумм, разностей и других функций, связанных с числовым набором или таблицей. Часто в таких задачах бывает полезным упорядочить числа набора по величине.
Решение многих задач удобно начинать с рассмотрения «граничного», «крайнего» объекта. Таким объектом может быть наибольшее число, ближайшая точка, граничный случай, наибольшая или наименьшая сторона, одним словом, элемент в котором некоторая величина принимает наибольшее или наименьшее значение. Этот метод решения задач иногда называют принципом (правилом) крайнего.
Задачи с решениями
1. Числа 1, 2, 3, . . . , 2n – 1, 2n разбиты на две группы по n чисел в каждой. Пусть a1 < a2 < . . . < an – числа первой группы записанные в возрастающем порядке, и b1 > b2 > . . . > bn – числа второй группы в убывающем порядке. Докажите, что
|a1 – b1| + |a2 – b2| + . . . + |an – bn| = n2.
Каждое слагаемое |ak – bk| (k = 1, 2, … , n) равно разности числа большего n, и числа, не превосходящего n. Поэтому
|a1 – b1| + |a2 – b2| + . . . + |an – bn| =
= (n + 1) + (n + 2) + . . . + 2n – (1 + 2 + . . . + n) =
= 0,5·((n + 1) + 2n)n – 0,5·(1 + n)n = n2,
что и требовалось доказать.
2. В классе имеется a1 учеников, получивших в течение года хотя бы одну двойку, a2 учеников, получивших не менее двух двоек, . . . , ak учеников, получивших не менее k двоек. Сколько всего двоек в этом классе? (Предполагается, что ни у кого нет более k двоек.)
I способ. Количество учеников, получивших ровно одну двойку, равно (a1–a2), ровно две двойки – (a2–a3), и так далее. Поэтому общее количество двоек равно
(a1 – a2) + 2(a2 – a3) + 3(a3 – a4) + . . . + (k – 1)(ak–1 – ak) + kak =
= a1 + (2a2 – a2) + (3a3 – 2a3) + (kak – (k–1)ak–1) = a1 + a2 + . . . + ak.
II способ. Занумеруем двойки каждого ученика в порядке их получения. Тогда a1 – количество первых двоек, a2 – количество вторых двоек, и так далее. Значит, количество всех двоек равно a1 + a2 + . . . + ak.
Ответ: a1 + a2 + . . . + ak.
3. В команде сторожей у каждого есть разряд (натуральное число). Сторож N-го разряда N суток дежурит, потом N суток спит, снова N суток дежурит, N – спит, и так далее. Известно, что разряды любых двух сторожей различаются хотя бы в три раза. Может ли такая команда осуществлять ежедневное дежурство? (Приступить к дежурству сторожа могут не одновременно, в один день могут дежурить несколько сторожей.)
Занумеруем сторожей в порядке убывания разряда. У сторожей жизнь делится на равные периоды сна и дежурства. При этом у каждого сторожа периоды, как минимум, втрое короче, чем у предыдущего; поэтому любой период предыдущего делится, как минимум, на три части периодами следующего, причем как минимум две из этих частей будут целыми периодами следующего. Следовательно, период сна предыдущего содержит целый период сна следующего. Так продолжая, найдём вложенный друг в друга набор периодов снов всех сторожей. В день, входящий в самый маленький из вложенных периодов сна, никто не дежурит.
Ответ: не может.
4. В Нью-Йорке шахматных мастеров больше, чем на всей остальной территории США. Планируется шахматный турнир с участием всех мастеров. Решено, что турнир будет проведен в месте, для которого общее расстояние переездов между городами участников турнира было бы минимальным. Нью-йоркские мастера утверждают, что этому критерию удовлетворяет их город, а мастера с Западного побережья настаивают на том, что место соревнований в городе, находящемся в центре тяжести совокупности игроков, было бы лучше.
Где должен проводится турнир?
Обозначим нью-йоркских мастеров буквами N1, N2, ... , Nk, а остальных игроков буквами O1, O2, ... , Ot. Так как в Нью-Йорке находится больше половины игроков, то k > t. Если рассмотреть пары игроков (N1, O1), (N2, O2), ... , (Nt, Ot) то нью-йоркские мастера Nt+1, Nt+2, ... , Nk не попадут ни в одну из пар.
Рассмотрим теперь пару (N1, O1). При любом выборе города проведения турнира мастера N1 и O1 должны проехать в совокупности не меньше, чем расстояние N1O1 по прямой, соединяющей эти города. Вместе же они проедут не меньше, чем
S = N1O1 + N2O2 + . . . + NtOt.
Если местом соревнований выбран Нью-Йорк, то S и будет суммой расстояний. Если же соревнования будут проводиться в другом месте, то t пар игроков проедут расстояние не меньше S, а ненулевая сумма расстояний для игроков Nt+1, Nt+2, ... , Nk увеличит общую сумму. Следовательно, Нью-Йорк – наилучшее место для проведения соревнования.
Ответ: в Нью-Йорке.
5. Докажите, что в многограннике найдутся две грани с одинаковым количеством сторон.
Рассмотрим грань с наибольшим количеством сторон n и обозначим её G. К каждой стороне грани G прилегает некоторая грань многоугольника. Всего таких граней n. Если среди них есть ещё одна грань с количеством сторон n, то утверждение задачи доказано.
Если же такой грани нет, то у граней, которые прилегают к G количество сторон заключено между 3 и (n–1), всего (n–3) возможностей. Поскольку количество возможностей меньше n, то какая-то из них повторяется. Следовательно, среди граней, прилегающих к G, найдутся две грани с одинаковым количеством сторон.
Доказательство окончено.
6. Докажите, что любой выпуклый многоугольник Ф содержит два многоугольника Ф1 и Ф2, которые не пересекаются и подобны Ф с коэффициентом подобия 1/2.
Пусть А и В – пара наиболее удаленных друг от друга точек многоугольника Ф. Тогда в качестве искомых фигур Ф1 и Ф2 можно взять многоугольники гомотетичные Ф относительно точек А и В соответственно с коэффициентом гомотетии 1/2. Действительно, Ф1 и Ф2 не пересекаются, поскольку лежат по разные стороны от серединного перпендикуляра отрезка АВ. Кроме того Фi содержится в Ф, поскольку Ф – выпуклый многоугольник.
7. Докажите, что если многоугольник имеет несколько (больше двух) осей симметрии, то все они пересекаются в одной точке.
Допустим, что у многоугольника нашлось три оси симметрии, которые не пересекаются в одной точке, то есть они образуют треугольник. Пусть Х – точка многоугольника, которая наиболее удалена от некоторой внутренней точки М этого треугольника. Точки Х и М лежат по одну сторону от одной из рассмотренных осей симметрии k. Если точка Х’ – точка, симметричная точке Х относительно прямой k, то МХ' > МХ и точка Х' более удалена от точки М чем точка Х. Получаем противоречие, поэтому все оси симметрии многоугольника пересекаются в одной точке.
8. Теорема Сильвестра. На плоскости дано конечное число точек, причем такое, что любая прямая, проходящая через две из данных точек, содержит еще одну данную точку. Тогда все данные точки лежат на одной прямой.
Предположим, что не все данные точки лежат на одной прямой. Проведем через каждую пару данных точек прямую (этих прямых конечное число) и выберем наименьшее ненулевое расстояние от данных точек до этих прямых. Пусть наименьшим будет расстояние от точки A до прямой BC, где точки B и C данные. На прямой BC лежит еще одна из данных точек – некоторая точка D. Опустим из точки A перпендикуляр AQ на прямую BC.
Две из точек B, C и D лежат по одну сторону от точки Q, например C и D. Будем считать для определённости, что CQ < DQ. Тогда расстояние от точки C до прямой AD меньше, чем расстояние от точки A до прямой BC, что противоречит выбору точки A и прямой BC. Полученное противоречие доказывает рассматриваемое утверждение.
9. Доказать, что не существует попарно различных натуральных чисел x, y, z, t, для которых было бы справедливо соотношение
xx + yy = zz + tt.
Предположим, что такие числа нашлись. Пусть z – наибольшее из этих чисел. Тогда z > 3, а значит,
xx + yy < 2 · (z – 1)z – 1 < 2 · zz – 1 < z · zz – 1 = zz < zz + tt,
что противоречит предположению. Следовательно, таких чисел не существует.
10. В клетках таблицы 10 на 10 расставлены числа 1, 2, 3, ... , 100 так, что сумма любых двух соседних чисел не превосходит S. Найдите наименьшее возможное значение S. (Числа называются соседними, если они стоят в клетках, имеющих общую сторону.)
Пример расстановки, для которой S = 106 , приведен на рисунке.
Докажем теперь, что S не меньше 106 для любой расстановки чисел в таблице. Нам понадобится следующая лемма.
Лемма. Если в прямоугольнике 2 на 10 отмечено n < 10 попарно несоседних клеток, то число (неотмеченных) клеток прямоугольника, соседних с отмеченными, больше n.
В каждом из 10 прямоугольников 1 на 2, будем называть их домино, длинные стороны которых параллельны коротким сторонам прямоугольника 2 на 10, отмечено не более одной клетки. Если одна клетка в таком домино отмечена, то другая – неотмеченная, соседняя с отмеченной. Тем самым уже имеем n таких клеток, а поскольку n < 10, то найдется, очевидно, и клетка, принадлежащая домино без отмеченных клеток, граничащая с отмеченной клеткой соседнего домино. Следовательно, общее число неотмеченных клеток, соседних с отмеченными, больше n. Лемма доказана.
Допустим, что S меньше 106 для некоторой расстановки чисел. Стерев все числа в таблице, будем вписывать их на прежние места, начиная с числа 100 в порядке убывания.
Выделим в таблице пять неперекрывающихся горизонтальных полос 10 на 2 клетки и пять неперекрывающихся вертикальных полос 2 на 10 клеток. Зафиксируем число n0, после вписывания которого впервые либо в каждой горизонтальной, либо в каждой вертикальной полосе окажется не меньше одного вписанного числа; соответствующий момент назовем критическим. Пусть уже вписаны 33 числа от 100 до 68, но есть пустые горизонтальная и вертикальная полосы. Те 64 клетки таблицы, которые не входят в эти полосы, можно разбить на 32 домино; хотя бы в одном из них окажутся два вписанных числа с суммой, не меньшей, чем 68 + 69 > 105. Отсюда следует, что n0 не меньше 68, и все числа – несоседние.
Заметим, что в критический момент в каждую из полос вписано меньше 10 чисел (если бы нашлась, например, горизонтальная полоса, в которую вписано ровно 10 чисел, то перед вписыванием числа n0 в ней было бы не меньше 9 чисел, в силу чего в каждой из вертикальных полос было бы минимум по одному числу, что противоречит определению числа n0). Поэтому к полосам того направления, в которых в критический момент оказалось хотя бы по одному числу, можно применить лемму.
Поскольку в критический момент в таблицу вписано 101 – n0 чисел, из леммы следует, что у клеток, куда они вписаны, есть не менее (101 – n0) + 5 = 106 – n0 пустых соседних. Нам предстоит, таким образом, вписать в таблицу число, которое не меньше, чем 106 – n0, причем рядом с числом, которое не меньше, чем n0. Сумма этих двух чисел будет не меньше, чем 106 – n0 + n0 = 106, что противоречит нашему предположению о том, что S меньше 106.
Ответ: 106.
Задачи без решений
1. Пусть n точек х1, х2, ... , хn лежат в указанном порядке на прямой. Где находится точка х, сумма расстояний которой до этих точек минимальна?
2. На шахматной доске расставлены числа, каждое из которых равно среднему арифметическому своих соседей (по вертикали и горизонтали). Докажите, что все числа равны.
3. Каждый из 450 депутатов парламента дал пощечину ровно одному своему коллеге. Докажите, что можно избрать парламентскую комиссию из 150 человек, среди членов которой никто никого не бил.
4. Как заполнить клетки бесконечной таблицы натуральными числами так, чтобы:
а) каждое число n встречалось n раз;
б) наибольшая из разностей чисел в соседних клетках была наименьшей? (Две клетки считаются соседними, если имеют общую сторону.)
5. Докажите, что любой выпуклый многоугольник с площадью 1 можно поместить в прямоугольник площади 2.
Создано на конструкторе сайтов Okis при поддержке Flexsmm - накрутка лайков вк