Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
 Скачать 3.42 Mb.
|
|
) + n, где транспонированная матрица? б) Верно ли, что L(m, n) + m = L(n, m) + в) Найдите L(B m ). 17 (нерешенная. Рассмотрим набор переменных x α 1 ,...,α n , занумерованных вершинами мерного единичного куба Z n 2 . Требуется найти суммы во всех гранях, содержащих вершину (0, . . . , 0). Другими словами, для каждого набора (α 1 , . . . , α n ) ∈ требуется найти x β 1 ...β n . За какое наименьшее число суммирований (mod 2) это можно сделать. Попробуйте получить аналогичные результаты для переменных изв следующих случаях: а) требуется найти набор сумм, есть только сумматоры; б) требуется найти набор сумм, есть два вида элементов сумматоры и разности; в) требуется найти набор линейных комбинаций с целыми коэффициентами. Есть два вида элементов сумматоры и умножатели на целую константу (быть может, разную для разных умножателей). Зачетные задачи 8–11, Решения. а) Ответ 98. Очевидно, что сумму x 1 + . . . + можно найти за суммирований. Допустим, у насесть схема из a сумматоров, реализующая нашу сумму. Рассмотрим граф, в котором 99 вершин P 1 , . . . , и Сложность суммирования 357 для каждого сумматора с суммой на первом входе x i 1 + . . . + x i p и суммой на втором входе x j 1 + . . . + x j q проводится ребро из вершины в вершину P j 1 . Ясно, что в каждый момент вершины, соответствующие переменным, входящим в одну из уже вычисленных сумм, лежат водной компоненте связности. Следовательно, конечный граф связен, а значит, в нем не менее 98 ребер, те б) Ответ 98. Доказательство аналогично па. Решение дословно повторяет решение задачи 1. 3. Подходит, например, следующий набор+ x 2 , x 1 + x 2 + x 3 , x 1 + x 2 + x 3 + x 4 , x 2 + x 3 + Действительно, в случае мы можем вычислить эти суммы в указанном порядке без вычисления вспомогательных сумма в случае R нам придется вычислять хотя бы одну вспомогательную сумму. а) Обозначим через S(A) сумму всех переменных, индексированных элементами множества A. Пусть S(A 1 ) и S(A 2 ) — искомые суммы. Если все множества B 1 := A 1 \ A 2 , B 2 := A 1 ∩ и B 3 := A 2 \ A 1 непу- сты, то вычислим сумму в каждом из этих множеств, потратив на это не более − 1 + |B 2 | − 1 + |B 3 | − 1 = |A 1 ∪ A 2 | − 3 6 n − 3 суммирований. Осталось найти) = S(B 1 ) + S(B 2 ) и S 2 = S(B 2 ) + Для этого достаточно двух суммирований. Можно несложно (например, перебором) убедиться, что в случае когда одно из множеств пусто, требуется не больше суммирований, чем в этом случае. б) Аналогично па. Несложно видеть, что 2 n − (n + 1) — это число всех сумм от n переменных, имеющих хотя бы два слагаемых. Эти суммы мы можем последовательно вычислять сначала суммы с двумя слагаемыми, потом суммы стремя слагаемыми . . . потом сумму с n слагаемыми. В результате этого процесса мы вычислим все суммы от переменных x 1 , . . . , x n 6. а) Набор из km сумм можно воспринимать как k наборов из m сумм. Реализуя каждый такой набор по отдельности, получаем требуемую оценку. б) Разрежем вертикальными разрезами матрицу, соответствующую нашему набору из m сумм от kn переменных на k матриц размера Гл. 13. Алгоритмы, конструкции, инварианты m × n. Сначала при помощи kl сумматоров реализуем все полученные матрицы m × n. Тогда каждая искомая сумма является суммой небо- лее чем k − 1 уже найденных сумм. Следовательно, искомый набор сумм можно реализовать не более чем за kl + m(k − 1) < k(l + m) суммиро- ваний. 7. а) Из задачи 5 при n = 500 получим, что любой набор из m сумм от 500 переменных можно вычислить не более чем за l = 2 500 суммиро- ваний. Следовательно, по задаче 6 б, любой набор из m сумм от 500k переменных можно вычислить не более чем за k(l + m) сложений. Таким образом, любой набор из m сумм от n переменных можно вычислить не более чем за l n 500 m (l + m) суммирований. Ясно, что при достаточно больших m и n это меньше, чем б) Из задачи 5 получим, что любой набор из m сумм от [log 2 m] переменных можно вычислить не более чем за l = 2 [log 2 m] 6 m суммирова- ний. Следовательно, по задаче 6 б, любой набор из m сумм от [log 2 m]k переменных можно вычислить не более чем за k(l + m) 6 2km сложений. Таким образом, любой набор из m сумм от n переменных можно вычислить не более чем за l n [log 2 m] m суммирований. 9. Рассмотрим произвольную матрицу A размера m × n. Если в этой матрице все столбцы различны, то сложность этой матрицы не превосходит L(B m ). Если же есть два совпадающих столбца, то, вычислив сначала сумму соответствующих этим столбцам переменных, мы сводим задачу к реализации матрицы m × (n − 1). Следовательно, n) 6 L(B m ) + n < n + 2 m+1 10. При достаточно больших n выполнена цепочка неравенств, n) < l n [0,95 log 2 n] m L([0,95 log 2 n], n) < n 0,94 log 2 n L([0,95 log 2 n], n) < < n 0,94 log 2 n (n + 2 · 2 [0,95 log 2 n] ) < n 0,94 log 2 n (n + 2n 0,95 ) < n 0,9 log 2 n 11. а) Назовем началами проводов входы схемы и выходы сумматоров (всего n + k), концами проводов выходы схемы и входы сумматоров (всего m + 2k). Пронумеруем все начала и концы проводов. Сопоставим каждой схеме информацию о том, какие начала проводов подсоединены Сложность суммирования 359 к каким концам проводов. Понятно, что эта информация однозначно определяет схему. Поэтому искомое число схем не больше, чем число различных вариантов подсоединить к каждому из m + 2k концов проводов какое-то из n + k начал проводов, которое равно (n + k) m+2k б) Так как число различных схем из L(m, n) элементов с n входами и m выходами не меньше числа матриц размера m × n с коэффициентами из Z 2 , то 2 mn 6 (n + k) m+2k . Логарифмируя это неравенство, получаем утверждение задачи. в) Если k = L(n, n) < n 2 5 log 2 n , то n 2 6 n + 2n 2 5 log 2 n log 2 n + n 2 5 Докажем, что это неравенство неверно при достаточно больших n. Действительно Осталось воспользоваться определением предела. Указание. Если k = L(n, n) < n 2 5 log 2 n , то n 2 6 n + 2n 2 5 log 2 n log 2 n + n 2 5 что неверно при достаточно больших г) Этот пункт полностью аналогичен предыдущему. а) Заметим, что если a n < b n √ 1 + ε и b n < c n √ 1 + ε, то a n < < (1 + ε)c n . Осталось воспользоваться определением. б) Утверждение задачи сразу следует из определения символов и «.». 13. Будем обозначать m = f(n). Если k = L(m, n) < mn (2 + ε) то mn 6 m + 2mn (2 + ε) log 2 (mn) log 2 n + mn 2 Докажем, что это неравенство неверно при достаточно больших n. Действительно 2 + ε · 2 = 4 2 + ε Гл. 13. Алгоритмы, конструкции, инварианты Осталось воспользоваться определением предела. Разобьем реализуемую матрицу A на подматрицы ширины h log 2 m k i . Каждую подматрицу можно реализовать за m k суммирова- ний. Следовательно, все подматрицы вместе можно реализовать за k · m сложений, а саму матрицу A — за k · m k + m n log 2 m k k + 1 k nm Поэтому для любого k выполнено асимптотическое неравенство, n) . k + 1 k mn Следовательно, L(m, n) . mn log 2 m , что и требовалось доказать. Аналогично задаче 10 можно доказать, что для любого ε ∈ (0, при достаточно больших n выполнено неравенство, n) 6 mn α что и требуется в задаче. а) Представим схему в виде ориентированного графа, у которого есть вершины четырех видов входы схемы (у них нет входов, один выход сумматоры (у них два входа, один выход размножатели (у них один вход, два выхода выходы схемы (у них один вход, нет выходов). Как несложно видеть, элемент a ij равен числу путей из го входа в й выход (по модулю 2). Рассмотрим новый граф, в котором все ребра направлены в противоположную сторону, и соответствующую ему схему. Несложно видеть, что эта схема реализует матрицу A t . Обозначим сложность первой схемы, а l 2 — второй. Найдем число ребер нашего графа двумя способами как число начал ребер первого графа и как число начал ребер второго графа. В первом случае получим n + l 1 + а во втором случае получим m + l 2 + 2l 1 . Следовательно, n + l 2 = m + Так как l 1 = L(A), то L(A t ) 6 m − n + L(A). Осталось воспользоваться тем, чтоб) Следует из а). в) Выбросим из матрицы B m нулевой столбец и обозначим полученную матрицу B ′ m . Тогда (B ′ m ) t — это матрица, соответствующая набору всех сумм от m переменных. Сложность этого набора сумм мы уже знаем. Используя пункта, получаем L(B m ) = 2 m+1 − 2m − 2. Комбинаторная разминка 361 Комбинаторная разминка (И. Н. Шнурников 1. Дан правильный треугольник ABC со стороной 3. Треугольник называется большим, если длины всех его сторон больше а) Докажите, что из треугольника ABC можно вырезать 100 больших треугольников. б) Докажите, что треугольник ABC можно целиком разрезать на не менее чем 100 больших треугольников. Хамелеон по очереди спит и ловит мух. Перед первой мухой он спит 1 минуту. Перед поимкой мухи номер 2n он спит столько же, сколько и перед поимкой мухи номер n. А перед поимкой мухи номер 2n + спит на одну минуту больше, чем перед поимкой мухи номера) Сколько мух хамелеон поймает перед своим первым сном в 9 минут б) Сколько минут хамелеон проспит перед поимкой мухи номер 98? 3. На плоскости задано несколько непересекающихся отрезков, никакие два из которых не лежат на одной прямой. Мы хотим провести еще несколько отрезков, соединяющих концы данных отрезков так, чтобы все отрезки вместе образовали одну несамопересекающуюся ломаную. Всегда ли это можно сделать. Множество A состоит из натуральных чисел, его наименьший элемент равен 1, а наибольший равен 100. Каждый элемент A, кроме равен сумме двух (возможно равных) чисел, принадлежащих A. Укажите среди всех множеств A, удовлетворяющих этим условиям, множество с минимальным числом элементов. В правильном угольнике требуется покрасить каждую сторону и каждую диагональ каким-либо цветом так, чтобы любые два из этих отрезков, имеющие общую точку, были покрашены различно. Какое наименьшее количество цветов для этого необходимо. На бесконечном клетчатом листе со стороной клетки 1 разрешается делать разрезы только по линиям сетки. Докажите, что при любом целом m > 12 можно вырезать такой прямоугольник площади, большей m, из которого нельзя вырезать прямоугольник площади ровно m. 7. Можно ли разместить 2006 точек в единичном квадрате так, чтобы любой прямоугольник площади со сторонами, параллельными сторонам квадрата, содержал внутри себя хотя бы одну из этих точек Гл. 13. Алгоритмы, конструкции, инварианты. Докажите, что существует такая бесконечная ограниченная последовательность чисел x n , что для любых различных m и k выполнено неравенство m − x k | · |m − k| > 1. 9. Рассмотрим деталь из 5 клеток в виде буквы мягкий знак (т. е. квадрат 2 × 2 и еще одна клетка. Прямоугольник 5 × n замощен n такими деталями. а) Докажите, что число n четно. б) Докажите, что прямоугольник 5 × 2n можно замостить не менее · способами. Дан полный граф на 10 вершинах. а) Покрасьте его ребра в 5 цветов так, чтобы в любом его полном подграфе на 5 вершинах встретились бы ребра всех 5 цветов. б) Докажите, что ребра графа нельзя покрасить в 4 цвета так, чтобы в любом его подграфе на 4 вершинах встретились бы ребра всех 4 цветов. Указания 2. Удобнее использовать двоичную систему счисления. Расположим сначала серию из 200 точек я точка имеет координаты, где i = 1, 2, . . . , 200. Теперь любой прямоугольник площади, не содержащий точек этой серии, имеет высоту не более Вторая серия состоит из 100 точек с ординатой и 100 точек с ординатой, и их абсциссы равны i 101 , где i = 1, 2, . . . , 100. Аналогично строим третью и четвертую серии. Теперь любой прямоугольник площади параллельный сторонам квадрата, не содержащий точек наших серий, имеет высоту не более 16 . Расположим теперь еще 800 точек (4 серии) параллельно другой стороне квадрата и получим нужное расположение точек. Покрасьте клетки таблицы счетными абсциссами и четными ординатами (те. всего 2 n − 1 клеток. Множество ребер одного цвета есть 4 попарно непересекающих- ся полных подграфа на 3, 3, 3, 1 вершинах соответственно (или на 4, 2, 2, 2). Немного индукции и перебора 363 Немного индукции и перебора (И. Н. Шнурников 1. Последовательность целых чисел a 0 = 0, a 1 , a 2 , . . . , a называется квадратной, если a 0 | = 1 2 , |a 2 − a 1 | = 2 2 , . . . , |a n − a n−1 | = а) Докажите, что для каждого натурального k существует квадратная последовательность, содержащая число б) Найдите минимальное n, такое что существует квадратная последовательность с a n = 2007. 2. В Дубне имеется n принимающих задачи и 2n − 1 школьник, причем принимающий номер i знает только школьников 1, 2, . . . , 2i − а остальных не знает. Докажите, что одновременный прием r задач, такой что каждый принимающий слушал бы только знакомого школьника, можно организовать C r n · n! (n − способами. В связном графе есть n вершин, степень каждой не превосходит, количество ребер не меньше 4 n. Докажите, что существует такая не висячая вершина, что после ее удаления граф остается связным. В обществе из 2005 человек есть представители шести стран. Все люди занумерованы числами от 1 до 2005. Докажите, что найдутся люди из одной страны с номерами a, b и c, такие что a = b + c, или с номерами и b, такие что a = 2b. 5. Пусть бесконечная арифметическая прогрессия натуральных чисел содержит квадрат и куб натуральных чисел. Докажите, что она содержит и шестую степень натурального числа. Постройте для каждого натурального n > 2 такое множество из 2 n−1 точек плоскости, что никакие три из них не лежат на одной прямой и никакие 2n не образуют выпуклый угольник. В конечном графе любые два треугольника имеют общую вершину и нет полного подграфа с 5 вершинами. Докажите, что можно удалить из графа 2 вершины вместе с выходящими из них ребрами так, что полученный граф не будет содержать треугольников. В некоторой стране каждый город соединен дорогами не более чем стремя другими. Из каждого города можно добраться до любого другого, проехав по не более чем двум дорогам. Для какого максимального числа городов это возможно Гл. 13. Алгоритмы, конструкции, инварианты. В стране 25 городов. Из каждого города выходит не более дороги между любыми двумя городами существует путь, проходящий не более чем по 2 дорогам. а) Докажите, что дорог хотя бы б) Найдите минимально возможное число дорог. Фундаменты нескольких башен расположены вряд. На первом фундаменте стоит башня из n кирпичей, остальные фундаменты пока без кирпичей. Если некоторая башня содержит хотя бы на 2 кирпича больше, чем следующая, то один кирпич перекладывается (из большей в меньшую. Если есть несколько вариантов перекладки (несколько пар башен, то выбирается любой из них. Найдите конечное распределение кирпичей по башням. Указания 1. Заметьте, что m 2 − (m − 1) 2 − (m − 2) 2 + (m − 3) 2 = 4. 2. Обозначим требуемое число способов за a(n, r) и найдем рекуррентную зависимость. В приеме задач принимающий номер n может участвовать, а может и нет. Количество первых вариантов равно, так как остальные принимающие дают a(n − 1, r − 1) способов, а после них остается еще 2n − r школьник. Число вторых вариантов равно a(n − 1, r). Итак a(n, r) = a(n − 1, r) + (2n − r)a(n − 1, r − 1). 3. Сведите утверждение задачи для исходного графа к аналогичному утверждению для его подграфа. 4. Сведите утверждение задачи к аналогичному утверждению для меньшего числа стран. Воспользуемся индукцией по разности прогрессии. Рассмотрите максимальный элемент. Разные задачи (И. Н. Шнурников Подсчет числа пар. Комиссия собиралась 40 раз. На каждом заседании было ровно человек, любые два небыли вместе больше 1 раза. Докажите, что в комиссии хотя бы 60 человек Разные задачи 2. На планете Марс 100 государств объединены в блоки, в каждом из которых не больше 50 государств. Известно, что любые два государства состоят вместе хотя бы водном блоке. Найдите минимально возможное число блоков. Подсчет двумя способами. В компании у любых двух знакомых друг с другом человек есть ровно 5 общих знакомых (исключая их самих. Докажите, что суммарное количество пар знакомых между собой людей в этой компании делится на 3. 4. Даны натуральные числа n > k и множество S из n точек на плоскости. Известно, что любые три точки из множества S не лежат на одной прямой и для любой точки P ∈ S существуют хотя бы k различных точек из множества S, равноудаленных от P . Докажите неравенство < 1 2 + √ 2n. 5. Пусть P n (k) — число перестановок множества натуральных чисел от 1 до n, оставляющих ровно k чисел на своем месте. Докажите равенство · P n (k) = n!. 6. Дан правильный угольник. Ровно m его вершин покрашено в белый цвет, остальные вершины покрашены в черный. Рассматриваются одноцветные равнобедренные треугольники с вершинами в вершинах угольника. (Треугольник одноцветный, если все его вершины или белые, или черные) Докажите, что при фиксированном m число равнобедренных одноцветных треугольников не зависит от способа рас- краски. Принцип Дирихле. В системе из p уравнений с q = 2p неизвестными+ a 12 x 2 + . . . + a 1q x q = 0, a 21 x 1 + a 22 x 2 + . . . + a 2q x q = 0, a p1 x 1 + a p2 x 2 + . . . + a pq x q = все коэффициенты a ij ∈ {−1, 0, 1}. Докажите, что существует решение, x 2 , . . . , x q ) этой системы в целых числах, такое что найдется x j 6= и все |x j | 6 q, где 1 6 j 6 q. 8. Даны n чисел x 1 , x 2 , . . . , x n , такие что x 2 1 + x 2 2 + . . . + x 2 n = Докажите, что для любого целого k > 2 существуют целые числа Гл. 13. Алгоритмы, конструкции, инварианты a 1 , a 2 , . . . , a n , не все равные 0, такие что |a i | 6 k − 1, i = 1, 2, . . . , n и+ a 2 x 2 + . . . + a n x n | 6 k √ n k n − Винегрет (задачи 9–28) 9. На плоскости дан выпуклый угольник. Известно, что все углы многоугольника меньше и никакие четыре его вершины не лежат на одной окружности. Через всевозможные тройки вершин многоугольника провели окружности. Для каждой вершины посчитали количество проведенных окружностей, внутрь которых попала данная вершина. Найдите сумму полученных n чисел. Пусть A есть набор из n остатков по модулю n 2 . Докажите, что найдется такой набор B из n остатков, что попарные суммы из наборов и B содержат не менее половины от всех остатков по модулю n 2 11. Найдите все конечные последовательности a 0 , a 1 , a 2 , . . . , a n , a m ∈ Z, в которых каждое число m встречается ровно a раз, где m = = 0, 1, . . . , n. 12. Дан связный граф с n вершинами, возможно, имеющий петли и кратные ребра. Степень каждой вершины графа равна 4. В данном графе выбрано несколько циклов, то есть замкнутых путей, возможно, имеющих самопересечения. Оказалось, что выполняются следующие свойства) циклы не поворачивают вспять нив одной точке графа) каждое ребро графа принадлежит ровно трем циклам с учетом кратности (по определению, кратность вхождения ребра в данный цикл равна m, если цикл проходит через ребро ровно m раз) для каждой вершины графа и каждой из 6 пар ребер, содержащих эту вершину, найдется единственный цикл, в котором эта пара ребер встретится подряд. Докажите, что количество циклов не превосходит 2n + 1 при n > и не превосходит 2n + 2 при n = 1, Постройте графы, для которых эти оценки достигаются. Даны два прямоугольника со сторонами a, b и c, d, причем a < < c 6 d < b и ab < cd. Докажите, что первый можно поместить во второй тогда и только тогда, когда (b 2 − a 2 ) 2 6 (bc − ad) 2 + (bd − ac) 2 14. Дано семейство элементных множеств натуральных чисел. Для любого набора из (m + числа все множества семейства, состоящие из чисел этого набора, имеют общий элемент (число. Докажите, что у всех множеств семейства есть общий элемент (число Разные задачи 15. В связном графе 1000 вершин, из каждой выходит не более ребер. Докажите, что можно выбрать 220 вершин так, чтобы между ними не было цикла нечетной длины. Все целые числа покрашены в 4 цвета. Даны различные нечетные числа m, n, такие что m + n 6= 0. Докажите, что найдутся два числа одного цвета с разницей, равной какому-то из чисел m, n, m + n, m − n. 17. Пусть a и b — взаимно простые натуральные числа. Назовем подмножество натуральных чисел хорошим, если оно содержит 1 и вместе с числом k содержит также числа k + a и k + b. Найдите количество хороших подмножеств. На плоскости нарисованы n прямоугольников со сторонами, параллельными координатным осям. Плоскость разбилась на области, ограниченные многоугольниками. Выберем те из них, которые содержат хотя бы одну из вершин исходных прямоугольников. Для каждого выбранного многоугольника посчитаем количество его вершин и сложим. Докажите, что полученное число меньше 40n. 19. Найдите минимально возможное количество ладей, поставленных на доске n × n так, что на любой полоске из k идущих подряд по горизонтали или по вертикали клеток доски стоит хотя бы одна ладья. Считаем n 2 < k 6 2n 3 20. Докажите, что существует множество из + последовательностей из 2n цифр, n нулей и n единиц, такое что любая последовательность из n нулей и n единиц может быть получена из элемента этого множества сдвигом одной цифры. Сдвиг одной цифры вытаскивает цифру из последовательности и вставляет ее в любое другое место. Вершины связного графа покрашены в синий и красный цвета (есть хотя бы одна вершина красного цвета. Каждой вершине приписано положительное вещественное число. Известно, что каждой синей вершине приписано число, равное среднему арифметическому чисел, написанных в ее соседях. Известны числа в красных вершинах. Докажите, что и числа в синих вершинах можно найти. Дано натуральное число k. Докажите, что существует бесконечно много точных квадратов вида 2 k n − 7. 23. Граф имеет 12k вершин, степень каждой равна 3k + 6. Для каждой пары различных вершин есть ровно n вершин графа, соединенных с обеими вершинами пары. Найдите всевозможные значения числа для которых при каком-нибудь n такой граф существует Гл. 13. Алгоритмы, конструкции, инварианты. На плоскости дано семейство из n векторов. Набор нескольких векторов семейства называется максимальным, если длина суммы векторов набора максимальна среди всех наборов из векторов семейства. а) Докажите, что количество максимальных наборов не превосходит 2n. б) Постройте примеры семейств с n = 4, n = 5 векторами и си максимальными наборами соответственно. Теорема Кэли. Докажите, что число различных деревьев с n занумерованными вершинами равно n n−2 26. Пусть A — это перестановка чисел 1, 2, . . . , n и B — это подмножество. Скажем, что A расщепляет B, если в перестановке числа из множества B идут не подряд (порядок следования не важен). Докажите, что для любого набора из n − 2 подмножеств, в каждом из которых не менее двух и не более n − 1 элементов, найдется перестановка чисел 1, 2, . . . , n, расщепляющая их всех. а) Докажите, что для любого натурального n существует натуральное число g(n) такое, что полный турнир с g(n) участниками содержит транзитивный 4) подтурнир с n участниками. В полном турнире каждые два участника борются друг с другом ровно один рази ничьих не бывает. б) Докажите, что для некоторого α > 1 минимальное число g(n) с указанным свойством удовлетворяет неравенству α n < g(n) < 2 n 28. Дано простое число p > 3. Обозначим за M количество состоящих из чисел 0, 1 и 2 последовательностей a 1 , a 2 , . . . , a p−1 , таких что a 1 + 2a 2 + . . . + (p − 1)a делится на p. Обозначим за N число аналогичных последовательностей из 0, 1 и 3. Докажите, что M 6 Следующая задача пока не решена. Придумайте соединение некоторых концов жестких стержней между собой и закрепление остальных концов на плоскости так, чтобы выполнялись два условия: а) при любых малых изменениях длин стержней весь механизм можно расположить на плоскости, сохранив длины стержней, но возможно с пересечениями и совмещениями концов стержней; б) для данных длин и закрепленных точек существует ровно одно расположение механизма в плоскости. Считайте, что стержней конечное число и их длины могут разли- чаться. 4) Такой, что если A выиграл у B и B выиграл у C, то A выиграл у C. Разные задачи 369 Указания 3. Выразим количество N троек попарно знакомых людей через количество пар знакомых людей. Каждая пара знакомых людей входит ровно в 5 троек, и каждая тройка оказывается посчитанной 3 раза, откуда. Каждую пару точек из множества S соединим отрезком, проведем к нему срединный перпендикуляр. Посчитаем количество точек из, лежащих на этом перпендикуляре и сложим по всем перпендикулярам. На каждой прямой лежит не более двух точек множества S, поэтому сумма будет не больше n(n − 1). С другой стороны, каждая точка множества S лежит на хотя бы k(k − перпендикулярах, проведенных к парам точек, равноудаленных от нее. Отсюда n k(k − 1) 2 6 n(n − 1). 5. Занумеруем перестановки числами от 1 до n!. Рассмотрим таблицу размера n × n!, состоящую из нулей и единиц. В таблице n! строки столбцов, нам месте стоит единица, если и только если я перестановка оставляет число i на месте. Сумма чисел в й строке таблицы это количество чисел, остающихся на месте при й перестановке, поэтому сумма чисел во всей таблице равна n P k=0 k · P n (k). А сумма чисел в м столбце равна (n − 1)! — это количество перестановок множества из n − 1 числа, значит, сумма всех чисел в таблице равна n!. 6. Обозначим количество равнобедренных одноцветных треугольников за od, а разноцветных за ra. Тогда всего равнобедренных треугольников. Для каждой пары одноцветных вершин 2005-угольника отметим три равнобедренных треугольника, в которые они входят, при этом одноцветные треугольники будут посчитаны три раза, а разноцветные — один раз. То есть m(m − 1) 2 + (2005 − m)(2004 − m) 2 = 3 · od + значит od зависит только от m. 7. Подставим в матрицу вместо x всевозможные целые числа 6 y i 6 q. Получим (q + 1) 2p наборов правых частей. Каждая правая часть может принимать не более чем q 2 + 1 значение, поэтому существует не более чем (q 2 + 1) p < (q + 1) 2p наборов правых частей, значит для двух разных наборов y ′ i и y ′′ i , где i = 1, 2, . . . , q, все p правых частей совпадут, тогда искомое решение x i = y ′ i − y ′′ i , где i = 1, 2, . . . , q. Гл. 13. Алгоритмы, конструкции, инварианты. Для каждой четверки точек ровно две точки попадут внутрь кругов, построенных по оставшимся трем точкам, поэтому искомая сумма равна 2C 4 n 10. Переберем все такие множества B, в среднем среди всевозможных сумм остатков из множеств A и B будет не менее n 2 /2 различных. Остается выбрать такое B, для которого это количество максимально. Всего в последовательности n + 1 число, из них нулей, единиц, . . . , a чисел n, поэтому a 0 + a 1 + . . . + a n = n + 1. Рассмотрим сумму всех чисел в последовательности, она равна 0 · a 0 + 1 · a 1 + . . . . . . + n · a n = a 0 + a 1 + . . . + a n . Из этих двух равенств находим ответ. Получим оценку. Рассмотрим остовное дерево графа, пересечем с оставшимся n + 1 ребром все циклы нашего семейства и получим набор из 3n + 3 отрезков (разбитый на n + 1 группу, покрасим отрезки набора. Назовем цикл одиноким, если он содержит только один покрашенный отрезок. В каждой группе только один покрашенный отрезок может образовать одинокий цикл, поэтому количество одиноких циклов. Остальные циклы содержат хотя бы два покрашенных отрезка, поэтому их количество l 6 3n + 3 − k 2 . Значит, всего циклов k + l 6 3n + 3 − k 2 + k = 3n + 3 + k 2 6 2n + Для n > 2 осталось перебрать несколько случаев и убедиться, что найдется цикл, содержащий хотя бы три покрашенных отрезка. Пример графа правильный угольник с петлей в каждой вершине. Один цикл — это сам угольник, n циклов — это все петли, а оставшиеся n циклов состоят из двух соседних петель и стороны угольника, их соединяющей (с кратностью 2). 13. Введем угол ϕ между прямоугольниками. Тогда помещаемость первого прямоугольника эквивалентна системе двух уравнений cos(ϕ) + a sin(ϕ) 6 c, b sin(ϕ) + a cos(ϕ) 6 Обозначим cos(ϕ) за x, аза. Нарисуем на координатной плоскости) окружность x 2 + y 2 = 1. Существование решения системы эквивалентна тому, что прямые bx + ay = c, by + ax = d пересекаются внутри окружности, что дает требуемую оценку. Воспользуйтесь теоремой Брукса из раздела Раскраски графов, задача 6 в Разные задачи 16. Сопоставим каждой паре целых чисел (x, y) (точке решетки) целое число mx + ny и покрасим так точки решетки. Угол при вершине прямоугольника может быть и и 270 ◦ , а при точке пересечения сторон — только 90 ◦ 19. Вырежем из квадрата размера n × n центральный квадрат размера) и разобьем оставшееся на 4 прямоугольника k × (n − k). В каждом прямоугольнике должны стоять хотя бы n − k ладей, поэтому всего их хотя бы 4(n − k). Пример также симметричен относительно вращений квадрата. Для каждой последовательности из n нулей и n единиц рассмотрим сумму номеров тех позиций, где стоят единицы и рассмотрим эту сумму по модулю n + 1. Все множество последовательностей разобьется на n + 1 класс (с одинаковым остатком по модулю n + 1), в каком-то классе элементов будет не больше, чем нужно, и из каждого класса сдвигами одной цифры можно получить все множество последовательностей. Воспользуйтесь методом производящих функций и интерпретацией корней й степени из 1. ГЛАВА КОМБИНАТОРНАЯ ГЕОМЕТРИЯ Принцип Дирихле и его применения в геометрии (10–11) И. В. Аржанцев Площадь фигуры Будем называть плоскую фигуру простой, если ее можно разбить наконечное число треугольников. Для такой фигуры A ее площадь определяется как сумма площадей соответствующих треугольников. Напомним, что точка (x 0 , y 0 ), принадлежащая фигуре A, называется внутренней точкой фигуры A, если найдется круг с центром (x 0 , целиком лежащий в Несложно проверить, что функция площадь на множестве простых фигур обладает следующими свойствами если фигура A имеет внутренние точки, то S(A) > 0; — если фигура A сложена из простых фигур и A 2 , не имеющих общих внутренних точек, то S(A) = S(A 1 ) + S(A 2 ); — равные фигуры, те. фигуры, которые можно совместить наложением, имеют одинаковые площади площадь квадрата со стороной единица равна единице. Более общо фигура B называется квадрируемой, если для любого > 0 существуют такие простые фигуры и A 2 , что A 1 ⊆ B ⊆ и) − S(A 1 ) < ε (см. рис. 1). Для квадрируемых фигур также можно A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 A 2 Рис. 1 Принцип Дирихле и его применения в геометрии 373 определить понятие площади и доказать, что площадь — это единственная функция на множестве квадрируемых фигур, обладающая перечисленными выше четырьмя свойствами. Отметим, что не каждая плоская фигура квадрируема (см, например, задачу 2). Желающим более детально познакомиться с понятием площади и его обобщениями можно рекомендовать книгу [1]. 1. Докажите, что фигура, ограниченная конечным числом отрезков и дуг окружностей, является квадрируемой. 2. Напомним, что фигура называется ограниченной, если она содержится в некотором круге. Докажите, что любая квадрируемая фигура ограниченна. Принцип Дирихле для площадей Следующее геометрическое утверждение напоминает известный «принцип ящиков Дирихле (P. Dirichlet), и поэтому обычно называется геометрическим принципом Дирихле или принципом Дирихле для площадей. Теорема 1. Пусть A — квадрируемая фигура, и A 1 , . . . , A m — квад- рируемые фигуры, содержащиеся в A. Предположим, что) < S(A 1 ) + S(A 2 ) + . . . + Тогда как минимум две из фигур A 1 , . . . , A m имеют общую внутреннюю точку. Доказательство. Предположим противное. Тогда A 2 ∪ . . . ∪ A m ) = S(A 1 ) + S(A 2 ) + . . . + Условия A 1 , . . . , A m ⊆ A влекут A 2 ∪ . . . ∪ A m ) 6 Полученное противоречие с условием завершает доказательство. По аналогии с обобщенным принципом ящиков можно рассмотреть следующее обобщение теоремы Теорема 2. Пусть A — квадрируемая фигура, и A 1 , . . . , A m — квад- рируемые фигуры, содержащиеся в A. Предположим, что nS(A) < S(A 1 ) + S(A 2 ) + . . . + для некоторого натурального n < m. Тогда как минимум n + 1 из фигур, . . . , A m имеют общую внутреннюю точку Гл. 14. Комбинаторная геометрия Доказательство. Если никакие n + 1 из наших фигур не имеют общей внутренней точки, то открытая часть множества A 1 ∪ . . . ∪ A m учитывается в сумме) + S(A 2 ) + . . . + не более n рази поэтому) + S(A 2 ) + . . . + S(A m ) 6 nS(A). 3. Внутри квадрата со стороной 1 помещена фигура, площадь которой больше 2 . Докажите, что эта фигура содержит две точки, симметричные относительно центра квадрата. На сфере имеется пятно, площадь которого больше половины площади сферы. Докажите, что это пятно покрывает пару диаметрально противоположных точек сферы. В квадрат со стороной 1 поместили несколько окружностей, сумма радиусов которых равна 0,51. Докажите, что существует прямая, параллельная одной из сторон квадрата и пересекающая не менее двух окружностей. В квадрат со стороной 1 поместили несколько окружностей, сумма длин которых равна 10. Докажите, что существует прямая, пересекающая не менее четырех окружностей. Теоремы Блихфельдта и Минковского Зафиксируем на плоскости прямоугольную декартову систему координат и через каждую точку с целыми координатами проведем две прямые, параллельные координатным осям. Полученная система прямых называется целочисленной решеткой, а точки с целыми координатами узлами целочисленной решетки. Целочисленная решетка разбивает плоскость на квадраты со стороной Рассмотрим целочисленную решетку и некоторую квадрируемую плоскую фигуру. Число покрытых фигурой узлов зависит не только от формы фигуры, но и от ее расположения. Например, имеются фигуры сколь угодно большой площади, не покрывающие ни одного узла (приведите пример!). Теорема Блихфельдта. Пусть A — квадрируемая фигура на координатной плоскости, площадь которой больше n. Тогда фигуру можно параллельно перенести таким образом, что она покроет не менее n + 1 узла целочисленной решетки. Доказательство. Целочисленная решетка разрезает фигуру A наконечное число кусков (A ограничена. Условие S(A) > n показывает Принцип Дирихле и его применения в геометрии 375 Рис. что число кусков > n + 1. Сложим все квадратики, которые пересекает наша фигура, в колоду (см. рис. 2). Мы получим > n + 1 фигур внутри квадрата со стороной 1, суммарная площадь которых > Согласно теореме 2, примененной к единичному квадрату, найдется точка P , которая принадлежит не менее чем n + 1 куску нашей фигуры. Остается применить к A параллельный перенос на вектор, соединяющий с некоторым узлом целочисленной решетки. При n = 1 теорему Блихфельдта можно переформулировать так. Теорема 3. Пусть A — квадрируемая фигура на координатной плоскости, площадь которой больше 1. Тогда в A можно найти две несовпадающие точки (x 1 , y 1 ) и (x 2 , y 2 ), такие что x 2 − и y 2 − целые числа. Плоская фигура A называется выпуклой, если вместе с любыми двумя своими точками она содержит отрезок, их соединяющий. Следующая теорема, принадлежащая немецкому математику Мин- ковскому (Н. Minkowski), возникла в рамках геометрической теории чи- сел. Теорема Минковского. Пусть A — симметричная относительно начала координат выпуклая квадрируемая фигура площади > 4. Тогда содержит точку с целыми координатами, отличную от начала ко- ординат. Доказательство. Применив к A гомотетию с центром вначале координат и коэффициентом 2 , мы получим фигуру B площади > 1. По теореме 3 фигура B содержит несовпадающие точки (x 1 , y 1 ) и (x 2 , для которых числа x 2 − и y 2 − целые. В силу симметричности точ- Гл. 14. Комбинаторная геометрия ка (−x 1 , −y 1 ) лежит в B, а в силу выпуклости в B лежит и середина отрезка, соединяющего (−x 1 , −y 1 ) и (x 2 , y 2 ). Точка O имеет координаты. Значит, точка с координатами (x 2 − x 1 , y 2 − лежит в A. 7. Покажите на примере, что в теореме Минковского условие) > 4 нельзя заменить на условие S(A) > 4. 8. Пусть A — квадрируемая фигура на координатной плоскости, площадь которой < n. Докажите, что A можно параллельно перенести так, что она покроет не более n − 1 узла целочисленной решетки. Пусть A — симметричная относительно начала координат выпуклая квадрируемая фигура площади > 4n. Докажите, что A содержит не менее 2n + 1 точек с целыми координатами. Теорема Дирихле об аппроксимации иррациональных чисел Рассмотрим иррациональное число α, натуральное число s и множество Это множество есть параллелограмм, площадь которого равна 2 s + 1 2 = 4 1 + 1 2s > Эта фигура выпукла и симметрична относительно начала координат (см. рис. 3). Теорема Минковского утверждает, что весть точка с целыми координатами, отличная от (0, 0). Можно считать, что первая координата этой точки положительна (объясните это. Тем самым доказана следующая теорема − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = −− αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − αx − y = − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s + − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − x = s − − 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111111111111111111111111111111111111 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2222222222222222222222222222222222222 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111111111111111111111111111111111111 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2222222222222222222222222222222222222 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111111111111111111111111111111111111 1 ssssssssss sssss ssss sssss sssssssssssssssssssssssssssssssssssssssssssssssss s 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111111111111111111111111111111111111 1 ssssssssss sssss ssss sssss sssssssssssssssssssssssssssssssssssssssssssssssss Рис. 3 Принцип Дирихле и его применения в геометрии 377 Теорема Дирихле. Для произвольных иррационального числа и натурального числа s найдутся такие целые числа x и y, что 0 < < x 6 s и − y| < 1 s 10. Докажите, что для произвольных иррационального числа и натурального числа s существует такое рациональное число m n , что < n 6 s и |α − m n | < 1 ns 11. Докажите, что для произвольного иррационального числа α существует бесконечно много таких рациональных чисел m n , что − m n Зачетные задачи Указания. Прежде всего заметим, что разность площадей двух правильных угольников, один из которых вписан в данную окружность, а другой описан около нее, можно сделать сколь угодно малой, выбрав достаточно большое n. Следовательно, круг — квадрируемая фигура. Тогда квадрируемой фигурой является и любой сегмент круга, а значит, и фигура, удовлетворяющая условию задачи. Любая простая фигура, очевидно, ограниченна. Так как квадри- руемая фигура содержится в некоторой простой, она также ограниченна. Пусть F — данная фигура, F ′ — фигура, симметричная ей относительно центра квадрата. Тогда S(F ) + S(F ′ ) > 1 и по теореме 1 существует точка X ∈ F ∩ F ′ . Очевидно, что X и симметричная ей точка образуют искомую пару. Рассмотрим фигуру, симметричную данной относительно центра сферы, и повторим рассуждение предыдущей задачи. Длина проекции любой окружности на любую прямую равна диаметру окружности. Следовательно, сумма длин проекций всех окружностей на любую сторону квадрата равна 1,02, те превышает длину этой стороны. По теореме 1 найдется точка X, принадлежащая проекциям хотя бы двух окружностей. Прямая, проходящая через X и перпендикулярная соответствующей стороне, — искомая. Сумма диаметров окружностей равна 10/π > 3. Поэтому, применив рассуждение предыдущей задачи и теорему 2, найдем искомую прямую Гл. 14. Комбинаторная геометрия. Рассмотрите открытый квадрат {(x, y): |x| < 1, |y| < 1}. 8. Заметим, что полуоткрытый квадрат −k 6 x, y < k при переносе на любой вектор покрывает ровно узлов. Выберем k достаточно большим, чтобы данная фигура содержалась в некотором таком квадрате. По теореме Блихфельдта существует перенос, при котором фигура покроет не менее 4k 2 − n + 1 узлов. Поскольку все эти узлы лежат в образе K, образ A покроет не более n − 1 узла. Применив к A гомотетию с центром вначале координат и коэффициентом, мы получим фигуру B площади > n. Из теоремы Блих- фельдта следует, что B содержит попарно не совпадающие точки, y 0 ), . . . , (x n , y n ), для которых все разности x i − x и y i − y являются целыми. Можно считать, что x 0 > x 1 > . . . > x и что среди точек (x i , y i ), у которых x i = x 0 , максимальное значение второй координаты равно y 0 . Тогда, как ив доказательстве теоремы Минков- ского, можно показать, что A содержит точки (0, 0), (x 0 − x i , y 0 − y i ), (x i − x 0 , y i − y 0 ), и что эти точки попарно различны. Достаточно в теореме Дирихле разделить обе части неравенства на x. Можно решить эту задачу и не используя геометрические соображения рассмотрим дробные части чисел α, 2α, . . . , sα и разделим отрезок [0, 1] на s равных частей. Возможны два случая. В каждом из s отрезков лежит ровно одно из чисел α, 2α, . . . , sα. Тогда для некоторого n выполнено неравенство n 6 s {nα} < и число m/n, где m = [nα], — искомое. Дробные части чисел n 1 α и n 2 α попали в один отрезок. Тогда искомым будет число m/n, где m = |[n 1 α] − [n 2 α]|, n = |n 1 − Литература Лебег А. Об измерении величин. М Учпедгиз, 1960. [2] Ядренко М. Й. Принцип Дiрiхле та його застосування. Киев Вища школа, Теорема Хелли (А. В. Акопян Все системы, о которых идет речь ниже, считаются конечными. Пусть каждые два отрезка, принадлежащие некоторой системе отрезков, расположенных на одной прямой имеют по крайней мере одну общую точку. Докажите, что тогда все отрезки из этой системы имеют по крайней мере одну общую точку Теорема Хелли 379 2. Пусть каждые два прямоугольника из некоторой системы прямоугольников с параллельными сторонами имеют по крайней мере одну общую точку. Докажите, что тогда все прямоугольники системы имеют по крайней мере одну общую точку. Пусть на прямой дана система из 2n + 1 отрезков, такая что каждый отрезок пересекается хотя бы с n отрезками из этой системы. Докажите, что тогда найдется отрезок, пересекающий все отрезки из этой системы. Теорема Хана—Банаха. а) На плоскости даны два непересе- кающихся выпуклых многоугольника. Докажите, что существует такая не пересекающая их прямая, что многоугольники лежат по разные стороны от нее. б) Обобщите эту теорему на случай мерного пространства. Теорема Хелли. а) Пусть каждые три многоугольника из системы выпуклых многоугольников имеют по крайней мере одну общую точку. Докажите, что тогда все многоугольники из этой системы имеют общую точку. б) Обобщите эту теорему на случай мерного пространства. а) Пусть некоторая система дуг, принадлежащих одной окружности и имеющих длину, меньшую длины полуокружности, обладает тем свойством, что каждые три дуги этой системы имеют по крайней мере одну общую точку. Докажите, что тогда все дуги этой системы имеют по крайней мере одну общую точку. б) Каков критерий на длины дуг, чтобы условие попарного пересечения дуг было достаточным для существования общей точки для всей системы. а) Докажите, что если каждые три точки некоторого подмножества плоскости можно покрыть кругом радиуса R, то и все точки множества можно покрыть кругом этого радиуса. б)* Докажите, что если каждые три прямые из некоторого множества прямых можно пересечь кругом радиуса r, то и все прямые из этого множества можно пересечь кругом радиуса r. 8. Можно ли обобщить теорему Хелли на случай двух и более точек Иначе говоря, существует ли такое n, что если для любых n выпуклых множеств системы можно указать 2 точки, такие что каждое содержит хотя бы одну из них, то такие две точки можно указать для всех множеств системы. На прямой выбрано 100 множеств A 1 , A 2 , . . . , A 100 , каждое из которых является объединением 100 попарно непересекающихся отрезков Гл. 14. Комбинаторная геометрия Докажите, что пересечение множеств A 1 , A 2 , . . . , является объединением не более 9901 попарно непересекающихся отрезков. (Точка также считается отрезком. На прямой даны 2k − 1 белый и 2k − 1 черный отрезок. Известно, что любой белый отрезок пересекается хотя бы с k черными, а любой черный — хотя бы с k белыми. Докажите, что найдутся черный отрезок, пересекающийся со всеми белыми, и белый отрезок, пересекающийся со всеми черными. На прямоугольном столе лежат равные картонные квадраты k различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть любые k квадратов различных цветов, то какие-нибудь два из них можно прибить к столу одним гвоздем. Докажите, что все квадраты некоторого цвета можно прибить к столу 2k − 2 гвоздями. На плоскости дано конечное множество точек X и правильный треугольник T . Известно, что любое подмножество множества X, состоящее из не более чем 9 точек, можно покрыть двумя параллельными переносами треугольника T . Докажите, что все множество X можно покрыть двумя параллельными переносами треугольника T Контрольный вопрос. Какие из указанных теорем перестают быть верными, если отбросить условие выпуклости многоугольников, фигурирующих в условии теоремы? а) Теорема Хана—Банаха. б) Теорема Хелли. Зачетные задачи 2; 4 а 5 а 6 а, б 7 а 9; Решения. Докажем утверждение задачи для системы из конечного числа отрезков. Пусть a i — координаты левых концов отрезков нашей системы, а b i — координаты их правых концов. Пусть a — наибольшее из чисел, а b — наименьшее из чисел b i . Достаточно доказать, что a 6 b тогда любая точка отрезка [a; b] будет общей точкой для всех отрезков. Предположим, что это неверно, те. Рассмотрим следующую пару отрезков отрезок, для которого a — левый конец, и отрезок, для которого b — правый конец. Так как a > b, то данная пара отрезков не пересекается, вопреки условию. Полученное противоречие показывает, что a 6 b, что нами требовалось. Замечание. Для бесконечной системы рассуждаем аналогично, только вместо наибольшего и наименьшего числа рассматриваем инфимум и супремум соответствующих числовых множеств Теория вероятностей и комбинаторная геометрия 381 Теория вероятностей и комбинаторная геометрия (А. М. Райгородский Хроматическим числом пространства R n называется минимальное число χ(R n ) цветов, в которые можно так раскрасить все точки пространства, чтобы между одноцветными точками не было расстояния Диаметром множества Ω ⊂ R n называется величина diam Ω = sup x , y∈Ω |x − где через |x − y| обозначено стандартное евклидово расстояние, а — это «супремум», или точная верхняя грань. Поскольку вдаль- нейшем речь пойдет о шарах и конечных множествах, можно для простоты считать, что супремум — это обычный максимум. Числом Борсука для ограниченного тела Ω ⊂ R n называется величина, равная минимальному количеству частей меньшего диаметра, на которые может быть разбито Ω. Через f (n) обозначается max Ω f (Ω). 1. Дано множество точек A = {x 1 , . . . , x n } ⊂ R 2 . Пусть d = diam Докажите, что количество пар (x i , x j ), для которых |x i − x j | = d}| не превосходит n. 2. Выведите из задачи 1, что f(A) 6 3. 3. Пусть B — трехмерный шар. Докажите, что f(B) 6 4. Постарайтесь добиться того, чтобы диаметры всех частей были как можно меньше. Сделайте тоже самое в мерном случае с заменой четырех на n + 1. |