Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
 Скачать 3.42 Mb.
|
|
4. Чему равно χ(R)? 5. Докажите, что χ(R 2 ) > 4. 6. Докажите, что χ(R 2 ) 6 7. 7. Конечны ли числа f(n) и χ(R n )? Если да, то как они оцениваются сверху. Докажите, что f(n) > n + 1, а χ(R n ) > n + 2 при n > 2. 9. Рассмотрим = x = (x 1 , . . . , x n ) : x i ∈ {0, 1}, x 1 + . . . + x n = Пусть Q = {x 1 , . . . , x s } ⊂ V таково, что (x i , x j ) 6= 1 для любых i и Здесь (x i , x j ) = x 1 i x 1 j + . . . + x n i x n j — скалярное произведение векторов x ν = (x 1 ν , . . . , x n ν ), ν ∈ {i, j}. Докажите как можно лучшую верхнюю оценку на мощность Q. Проверьте оптимальность этой оценки Гл. 14. Комбинаторная геометрия. Рассмотрим V = {x = (x 1 , . . . , x n ) : x i ∈ {0, 1}, x 1 + . . . + x n = = 5}. Пусть Q = {x 1 , . . . , x n } ⊂ V таково, что (x i , x j ) 6= 2 для любых i и j. Докажите как можно лучшую верхнюю оценку на мощность Проверьте оптимальность этой оценки. Пользуясь результатом задачи 9, докажите, что χ(R n ) > с некоторым c > 0. 12*. Пользуясь результатом задачи 10, докажите, что χ(R n ) > с некоторым c > 0. 13*. Как много можно выбрать попарно пересекающихся сочетаний из {1, . . . , n}? 14*. Пусть множество A = {x 1 , . . . , x n } ⊂ таково, что diam A = = 1. Существует ли такое A, что при любой раскраске его элементов в три цвета найдется пара одноцветных элементов на расстоянии 1 и что в тоже время никакие три вершины вне образуют равносторонних треугольников с длиной стороны Определение схемы испытаний Бернулли Обозначим через Ω множество последовательностей из нулей и единиц длины n. Пусть даны числа p ∈ (0, 1) и q = 1 − p. Вероятность последовательности ω ∈ Ω — это число P (ω) = p |ω| q n−|ω| , где |ω| — число единиц в последовательности. Вероятностью подмножества B ⊂ Ω называется число P (B) = P ω∈B P (Мотивировка. Приведенное определение описывает следующую физическую ситуацию. Пусть дана монета со смещенным центром тяжести при случайном бросании монета падает на стол решкой кверху с вероятностью p и орлом кверху с вероятностью q = 1— p. Бросаем монету на стол n раз. При каждом бросании записываем единицу, если выпала решка, и ноль в противном случае. Последовательность ω является элементарным событием, а любой набор последовательностей — событием. Простейшие задачи на схему испытаний Бернулли. Найдите P (µ = k). 16. Докажите, что P (Ω) = 1. 17. Докажите свойства вероятности: а) P (A ∪ B) = P (A) + P (B) − P (A ∩ б) P (A 1 ∪ . . . ∪ A n ) 6 P (A 1 ) + . . . + P (в) P (Ω \ A) = 1 − P (A). Теория вероятностей и комбинаторная геометрия 383 Задачи о сочетаниях. Рассмотрим множество R = {1, . . . , n} и будем производить последовательные испытания Бернулли. Если нам шаге выпала решка вынимаем элемент ν из R. Иначе — не вынимаем. В результате получается множество A 1 . Точно также строим A 2 , . . . , A m . Найдите (A i ∩ A j = ∅∀i, j). 19. Найдите P (|A 1 ∪ . . . ∪ A m | = k). 20. Найдите P (∀ i 1 , . . . , i r A i 1 ∩. . .∩A i r =∅) (r 6 m фиксировано. Найдите P (A i ∩ A j ⊆ A k ⊆ A i ∪ A j ) (i, j, k фиксированы). Определение случайной величины и ее математического ожидания Случайная величина — это произвольная функция ξ : Ω 7→ R. Пусть : Ω 7→ {y 1 , . . . , y k }. Тогда математическое ожидание ξ — это ее взвешенное среднее M ξ = k P i=1 y i P (ξ = y Задачи о математическом ожидании. Найдите Mµ. 23. Докажите линейность математического ожидания M(c 1 ξ 1 + + c 2 ξ 2 ) = c 1 M ξ 1 + c 2 M ξ 2 , где c 1 , c 2 ∈ R, а ξ i — случайные величины. Докажите, что если Mξ 6 x, то существует ω ∈ Ω: ξ(ω) 6 Задача комбинаторной геометрии Как много можно взять точек в R n , чтобы углы, образованные любыми тремя из них, были меньше Пусть f (n) — это интересующий нас максимум. Докажите, что f(n) 6 2 n 26. Докажите, что f(n) > 2n − 1. 27*. Докажите, что f(n) > 1 Пошаговое решение задачи Пусть A 1 , . . . , A 2m — такие же множества, как в задаче 18 (p = Им отвечают последовательности испытаний Бернулли ω 1 , . . . , ω 2m , которые можно интерпретировать как точки в R n . Очевидно, углы, образованные любыми тремя из них, не превосходят. Таким образом, если мы избавимся от прямых углов, удалив из множества векторов, . . . , не слишком много элементов, то мы получим достаточно хорошую нижнюю оценку на f (n). Действуем Гл. 14. Комбинаторная геометрия. Докажите, что тройка ω i , ω j , ω k образует прямой угол сверши- ной в в том числе и вырожденный, те. некоторые из совпадают, что возможно по построению) тогда и только тогда, когда A i ∩ ∩ A j ⊆ A k ⊆ A i ∪ A j (ср. задачу 21). 29. Пусть ξ — это число троек ω i , ω j , ω k , образующих прямой угол. Найдите x = M ξ, пользуясь результатами задачи. В силу утверждения задачи 24 найдутся такие ω 1 , . . . , ω 2m , что среди них не больше, чем x, прямых углов. Выведите отсюда неравенство за счет оптимального выбора m = m(n). III. Количество горизонтальных ребер у графа Га) четно; б) нечетно; в) может быть как четным, таки нечетным. Теорема о 12 (В. В. Прасолов, М. Б. Скопенков Многоугольники на клетчатой бумаге Пусть на клетчатой плоскости нарисован выпуклый многоугольник = A 1 A 2 . . . A n с вершинами в узлах сетки (рис. 1 слева. Предположим, что внутри M расположен ровно один узел O. Отложим векторы A 1 A 2 , # A 2 A 3 , . . . , # от узла O и на каждом из полученных отрезков выберем ближайший к точке O узел. Соединяя последовательно выбранные точек, получим некоторый многоугольник M ∗ , который называется двойственным к исходному многоугольнику (рис. 1 справа). M M M M M M Рис. Данный цикл задач посвящен элементарному доказательству открытой совсем недавно теоремы 1) (см. Несколько элементарных применений этой теоремы приводится в контрольных вопросах ниже Теорема о 12 Теорема о 12. Пусть внутри выпуклого многоугольника M расположен ровно один узел O, на его границе — b узлов, а на границе многоугольника M ∗ — узлов. Тогда b + b ∗ = 12. 0. Нарисуйте многоугольники, двойственные к изображенным на рис. 2. Сколько узлов расположено внутри в каждом случае Чему равны M ∗∗ ? Как связаны площади M и M ∗ ? Возможно ли равенство = M ∗ ? Сформулируйте ваши наблюдения и предположения, попытайтесь их доказать. M ? M ∗ ? ? а б в г д Рис. 2 1. Внутри треугольника ровно 1 узел. Какое наибольшее число узлов может быть на границе. Докажите теорему о 12 для параллелограмма с b = Простым треугольником назовем треугольник, не содержащий других узлов, кроме вершин (как внутри, таки на сторонах. Прыжок (рис. 3) — это преобразование, при котором вершина A треугольника заменяется на точку, симметричную ей относительно B. 3. Докажите, что а) площадь треугольника при прыжке не меняется; б) из простого треугольника при прыжке получается простой; в) у простого треугольника один из углов — тупой или прямой (причем последний случай возможен только для треугольника со сторонами, 1, √ 2, который мы назовем минимальным Гл. 14. Комбинаторная геометрия A 0 B C C B A Рис. г) из любого простого не минимального треугольника одним прыжком можно получить треугольнику которого наибольшая сторона меньше, чем наибольшая сторона исходного; д) любой простой треугольник можно конечным числом прыжков перевести в минимальный; е) площадь простого треугольника равна 1/2. 4. а) Докажите, что выпуклый четырехугольник, не содержащий узлов (кроме вершин, — параллелограмм. б) Существует ли выпуклый пятиугольник, не содержащий внутри себя узлов? в) Внутри выпуклого многоугольника ровно 1 узел. Какое наибольшее число вершин он может иметь. а) Если на сторонах треугольника нет узлов (кроме вершина внутри него — ровно 1 узел, то это точка пересечения медиан треуголь- ника. б) Докажите теорему о 12 для треугольника с b = Пусть S — площадь многоугольника, внутри которого i узлов, а на границе b узлов. а) Рассмотрим триангуляцию многоугольника с вершинами в данных b + i узлах. Сколько в ней может быть треугольников? б) Докажите формулу Пика = i + b 2 − 1. 7. Пусть отношение площади многоугольника к квадрату одной из его сторон иррационально (так будет, например, для правильного треугольника. Докажите, что подобный ему многоугольник нельзя нарисовать на клетчатой бумаге так, чтобы вершины лежали в узлах Теорема о 12 387 8. Шахматный король обошел доску 8 × 8 клеток, побывав на каждом поле ровно 1 рази последним ходом вернувшись на исходное поле. Ломаная, соединяющая последовательно центры полей, которые проходил король, не имеет самопересечений. а) Какую площадь может ограничивать эта ломаная? б) Какую наибольшую длину она может иметь? Удалением треугольника назовем операцию отрезания от многоугольника простого треугольника, имеющего с ним две общие стороны. Например, из многоугольника на риса удалением треугольника получается многоугольник на рис. 2 в. Обратную операцию назовем добавлением треугольника. Верно ли, что любые два многоугольника а) на рис. б) без узлов внутри; в) выпуклые, ровно с 1 узлом внутри получаются друг из друга серией удалений и добавлений треугольников Контрольные вопросы. Внутри выпуклого многоугольника с вершинами в узлах решетки расположен ровно 1 узел решетки. Какое наибольшее число сторон может иметь многоугольника) б) в) где) сколь угодно много. Внутри выпуклого многоугольника с вершинами в узлах решетки расположен ровно 1 узел решетки. Какую наибольшую площадь он может иметь? а) б) в) где) сколь угодно большую. Внутри выпуклого четырехугольника с вершинами в узлах решетки расположен ровно 1 узел решетки. Какое наибольшее число узлов решетки может быть на его границе? а) б) в) где) сколь угодно много. Какую наибольшую длину может иметь сторона простого треугольника а) 1; б) √ 2; в) 2; г) √ 5; д) сколь угодно большую. Сколько существует попарно неравных треугольников сверши- нами в узлах решетки и ровно 1 узлом решетки внутри? а) б) в) где) сколь угодно много. Могут ли многоугольники M и быть симметричны друг другу и при этом не совпадать? а) Могут; б) не могут Гл. 14. Комбинаторная геометрия Двойственность Пусть O — начало декартовой системы координат. Сопоставим каждой точке A(a, b) 6= O прямую A ∗ , задаваемую уравнением ax + by = Эта прямая называется двойственной к данной точке. Наоборот, каждой прямой ax + by = 1 сопоставим двойственную точку (a, b). 10. Нарисуйте фигуры, двойственные к фигурам на рис. 4. Проверьте, что на риса прямая l ∗ ∈ и что на рис. 4 б прямые A ∗ , B ∗ , проходят через одну точку. Докажите, что для любой точки C 6= O прямая перпендикулярна OC и проходит через точку C ′ ∈ OC, такую что OC · OC ′ = 1. A l A B C A B C c a b а б в г Рис. В многоугольнике M = A 1 . . . A n положим (A 1 A 2 ) ∗ . . . (A n A 1 ) ∗ 11. Проверьте, что это определение двойственного многоугольника согласуется с предыдущим (с точностью до поворота на 90 ◦ ). Докажите равенство M ∗∗ = M . 12. Если внутри M расположен ровно 1 узел, то внутри также расположен ровно 1 узел. а) При удалении треугольника из M происходит добавление треугольника к б) Из любого выпуклого многоугольника с ровно одним узлом внутри последовательностью удалений/добавлений треугольников можно получить параллелограмм св) Докажите теорему о 12. Теорема о 12 389 14. Какая фигура будет двойственной к невыпуклому многоугольнику (рис. 2 д При каком условии на M два определения равносильны Как обобщить теорему она невыпуклые многоугольники? Двойственная кривая γ ∗ — это ГМТ двойственных ко всем касательным к кривой γ. 15. Какая кривая двойственна единичной окружности Завершите рис. 5. Верно ли, что γ ∗∗ = а б в г Рис. 5 16*. Как обобщить теорему она многоугольники с более чем одним узлом внутри? Дополнительные задачи. На прямоугольном листе бумаги проведено несколько ломаных, идущих по сторонам клеток. Эти ломаные не имеют самопересечений и пересечений друг с другом. Ломаные лежат строго внутри прямоугольника, и лишь их концы находятся на его границе. Очевидно, что вершины прямоугольника не лежат на этих ломаных. Могут ли все остальные узлы клетчатой бумаги лежать на этих ломаных, если исходный прямоугольник имеет размеры а) 5 × 10; б) 6 × 12? 18. Проведите по линиям сетки замкнутую несамопересекающую- ся ломаную, которая бы проходила через все узлы клетчатой бумаги, лежащие внутри прямоугольника p × q клеток Гл. 14. Комбинаторная геометрия а) При каких p и q это возможно? б) Какую длину будет иметь эта ломаная? в) Какую площадь она будет ограничивать. а) Обозначим через kM многоугольник, который получается из гомотетией с коэффициентом k с центром вначале координат. Докажите формулу 2S(M ) = n(2M ) − 2n(M) + 1, где n(M) — число узлов внутри и на границе M б) Придумайте и докажите аналогичную формулу для объема многогранника в пространстве. Придумайте оценку для максимального числа вершин выпуклого многоугольника через число узлов внутри него. Аффинным преобразованием назовем преобразование плоскости, заданное равенствами x ′ = ax + by, y ′ = cx + dy, сохраняющее целочисленную решетку (это означает, что числа a, b, c, d — целые и ad − bc = ±1). 21. Классифицируйте выпуклые многоугольники а) без узлов внутри; б) с ровно одним узлом внутри с точностью до аффинных преобразований. а) Найдите образ прямой y = ax + b при преобразовании, y) 7→ x б) Число решений уравнения x 2 + ax + b = 0 (x 3 + ax + b = 0) равно числу касательных, которые можно провести к кривой x 2 = 4y (4x 3 = = −27y 2 ) из точки (a, в) Сколько решений имеет уравнение x 3 + ax + b = 0 в зависимости от a и г) Попытайтесь исследовать таким образом другие уравнения. Контрольные вопросы. Какие из следующих утверждений верны для любых точек A и таких что прямая AB не проходит через начало координата) A ∗∗ = б) A ∗ ∩ B ∗ = (в) A(AB) ∗ = (B ∗ ∩ AB) ∗ II. Какая кривая двойственна параболе y = а) Прямая; б) парабола; в) единичная окружность. Может ли для выпуклого многоугольника двойственный многоугольник быть невыпуклым? а) Может; б) не может Теорема о 12 Решения. См. риса г. Для многоугольника на рис. 2 дне существует двойственного, поскольку он не выпуклый (см. также задачу 14). На рис. 6 д показан пример, когда M = M ∗ . Возможные наблюдения) внутри расположен ровно 1 узел (см. задачу 12); 2) M ∗∗ = −M (см. задачу 11) 3) S(M ) + S(M ∗ ) = 6, что равносильно теореме о 12, так как по формуле Пика (задача 6 б) S(M ) = i + b 2 − 1 а б в где Рис. 6 1. Ответ 9. Пример изображен на рисе. Идею построения примера подсказывает теорема о 12. Раз на границах треугольников T ив сумме расположено 12 узлов, то, чтобы максимизировать число узлов на границе T , нужно минимизировать их число на границе T ∗ , и наоборот. Поэтому нужно взять треугольник с 3 узлами на границе, тогда двойственный треугольники будет искомым примером. Максимальность числа 9 следует, конечно, из теоремы о 12. Приведем независимое доказательство (рис. 7 a). Если на каждой стороне треугольника расположено не более 2 узлов (не считая вершин, то доказывать нечего. Рассмотрим случай, когда одна из сторон треугольника, назовем ее AB, содержит > 3 узлов (такая ситуация действительно возможна, см. рис. 6 в. Достаточно доказать, что на остальных сторонах расположено не более 1 узла. Пусть это не так, например, AC содержит узлов. Выберем из них узел D, ближайший к A. Проведем DE k где E ∈ AC. Выберем на стороне AB узел F , ближайший к A. Рассмотрим точки G и H на отрезке DE, такие что DG = AF и GH = AF , они, очевидно, являются узлами решетки. Так как узлы решетки разбивают и AC на равные отрезки, то CD : CA > 2 и AF : AB 6 1 4 . Из подобия Гл. 14. Комбинаторная геометрия : AB > 2 3 . Отсюда следует, что DH < DE, те и H лежат внутри треугольника, что противоречит условию. Максимальность доказана. H G F E D C B A M M C B D A O а б Рис. 7 2. Действительно, в этом случае O = AC ∩ BD (рис. 7 б ). Это следует из того, что точка, симметричная точке O относительно AC ∩ BD, целая и лежит внутри ABCD, а поэтому совпадает с O. Легко видеть, что M ∗ — параллелограмм, стороны которого получаются из диагоналей и BD параллельными переносами на векторы ± # OB и ± # соответственно. Так как на этих диагоналях лежит единственная целая точка O, тона каждой стороне параллелограмма лежит по одной целой точке, откуда b + b ∗ = 4 + 8 = 12. 3. а) Треугольники ABC и A ′ BC имеют общее основание BC, а поскольку, то соответствующие высоты равны. Значит, площади этих треугольников равны. б) Пусть D — середина BC. Заметим, что при центральной симметрии с центром D решетка переходит в себя. Поэтому если треугольник — простой, то его образ при этой центральной симметрии A ′′ BC тоже простой. Аналогично треугольник простой, поскольку получается центральной симметрией из A ′′ BC. Значит, внутри параллелограмма нет узлов, в частности, A ′ BC — простой. в) Рассмотрим минимальный прямоугольник со сторонами, параллельными линиям сетки, содержащий наш треугольник. Тогда на каждой его стороне лежит по вершине треугольника. Это возможно, только если хотя бы одна из вершин треугольника совпала с вершиной прямоугольника. Если таких совпадающих вершин три, то легко видеть, что наш треугольник — минимальный. Если их две и они являются про Теорема о 12 393 тивоположными (для прямоугольника, то, очевидно, угол при третьей вершине треугольника тупой. Остальные случаи для простого треугольника невозможны. Действительно, пусть треугольники прямоугольник имеют общую вершину A, а больше совпадающих вершин либо нет, либо это одна из соседних с ней вершин прямоугольника. Обозначим через вершину прямоугольника, противоположную ка через M — середину стороны треугольника, противоположной к A. Тогда легко видеть, что точка, симметричная точке D относительно M , — узел, лежащий внутри исходного треугольника или внутри его стороны. г) Достаточно сделать прыжок через вершину B с тупым углом. Так как AC наибольшая сторона, то AC > BC и AC > AB = BA ′ . Так как угол ABC тупой, то он больше угла A ′ BC, значит AC > A ′ C (потому что две другие стороны треугольников ABC и A ′ BC одинаковы). д) Будем, пока это возможно, уменьшать длину наибольшей стороны простого треугольника. Этот процесс не может продолжаться бесконечно, так как квадрат длины этой стороны принимает лишь целые значения (по теореме Пифагора. Согласно пункту г) этот процесс остановится на минимальном треугольнике. е) Следует из пунктов аи да) Пусть ABCD — наш четырехугольник, O = AC ∩ BD. Так как не содержит узлов внутри и на сторонах, то треугольники и ACD — простые. По задаче 3 е) их площади равны 1/2. Отсюда BO = = OD. Аналогично AO = OC, следовательно, ABCD — параллелограмм. б) Без ограничения общности можно считать, что на сторонах пятиугольника нет узлов (иначе рассмотрим меньший пятиугольник. Тогда по пункту а) ABCD — параллелограмм, BCDE — тоже параллелограмм. Отсюда A = E — противоречие. Значит, искомого пятиугольника не существует. в) Ответ 6. Пример изображен на рис. 6 д. Докажем максимальность (она также следует, конечно, из теоремы о 12). Проведем через единственный узел O внутри многоугольника прямую, не проходящую через его вершины. Она разбивает плоскость на две части. Если число вершин > 7, то по принципу Дирихле водной из частей находится хотя бы 4 вершины. Обозначим их A, B, C, D. Тогда внутри пятиугольника нет узлов, что противоречит пункту б. Максимальность доказана. Отсюда получаем, что число вершин многоугольника M может принимать значения n = 3, 4, 5, 6. 5. а) Пусть треугольник ABC содержит внутри единственный узел. Тогда треугольники AOB, BOC и COA — простые, по задаче 3 е) их площади равны 1/2. Это означает, в частности, что прямая AO равно Гл. 14. Комбинаторная геометрия удалена от вершин B и C. По признаку AO — медиана. Аналогично и CO — медианы. б) Согласно пункту а) точка O — это точка пересечения медиан данного треугольника ABC. Тогда по известному свойству этой точки AB − # CA = 3 # AO, # BC − # AB = 3 # BO, # CA − # BC = 3 # Но векторы в левой части это векторы сторон двойственного треугольника. Значит, двойственный треугольник получается из треугольника, построенного на векторах AO, BO и CO, растяжением в 3 раза. Поскольку отрезки # AO, # BO и CO не содержат узлов внутри, то отсюда получаем, что каждая сторона двойственного треугольника содержит ровно 2 узла (кроме вершин. Поэтому b + b ∗ = 3 + 9 = 12. 6. а) Ответ 2i + b − 2. Посчитаем сумму углов всех треугольников триангуляции двумя способами. С одной стороны, она равна nπ, где n число треугольников. С другой стороны, в эту сумму внутренние узлы дают вклад 2iπ, поскольку в каждом из них примыкающие треугольники образуют полный угол. Граничные узлы дают вклад, равный сумме углов угольника (у которого, возможно, некоторые углы равны π), те. Сравнивая полученные выражения для суммы углов, получаем ответ. б) Формула Пика следует из задачи 3 и пункта а). Более подробно данное доказательство обсуждается в статье [1]. Дадим указания к более простому доказательству (по сравнению с решением задачи 3; сама задача 3 является следствием формулы Пика). Обозначим через ϕ(P , M ) угол, под которым виден многоугольник из узла P , те если P — вершина, π, если P лежит на стороне, 2π, если P лежит внутри M Рассмотрим величину ) = X P ∈M ϕ(P , M где сумма берется по всем узлам внутри и на границе M . Теперь достаточно доказать следующие утверждения Теорема о 12 395 1) ϕ(M ∪ N) = ϕ(M) + ϕ(N), если многоугольники M и N не имеют общих внутренних точек) ϕ(M ) = 2πS(M а) если M — прямоугольник со сторонами, параллельными линиям сетки; б) если M — прямоугольный треугольник с катетами, параллельными линиям сетки; в) если M — произвольный треугольник; г) если M — произвольный многоугольник) ϕ(M ) = (2i + b − 2)π. 7. Если вершины многоугольника лежат в узлах, то квадрат стороны число целое (по теореме Пифагора, а площадь — число полуцелое (по формуле Пика, поэтому их отношение рационально. а) Ответ 31. Из формулы Пика следует, что площадь, ограниченная ломаной, равна 64/2 − 1 = 31 (узлами клетчатой бумаги служат центры 64 полей по условию все они лежат на границе многоугольни- каб) Ответ 28 + 36 √ 2. Нетрудно придумать путь короля, в котором из 64 ходов имеют длину (направлены по диагонали. Докажем, что больше 36 таких ходов быть не может. На каждом отрезке длины, входящем в путь короля, построим как на диагонали квадрат × 1. Одна половинка этого квадрата лежит вне многоугольника, который ограничивает путь короля. Но общая площадь, занятая такими половинками, не превышает 49 − 31 = 18, поскольку все они не выходят за пределы квадрата 7 × 7 клетчатой бумаги. Значит, количество диагональных ходов не превышает 36. 9. Ответ на все 3 вопроса утвердительный. Пункта) следует из в). б) Достаточно доказать, что изданного многоугольника, не содержащего внутри себя узлов, последовательностью добавлений и удалений вершин можно получить минимальный простой треугольник (см. задачу в. Рассмотрим триангуляцию многоугольника с вершинами во всех его граничных узлах. В ней все треугольники простые. Среди них найдется крайний треугольник, те. треугольник, имеющий две общие стороны с исходным многоугольником. Удалим его. Будем продолжать действовать таким образом, пока не останется один простой треугольник. Остается воспользоваться задачей 3 д, поскольку прыжок простого треугольника есть результат добавления треугольника и последующего удаления исходного треугольника. в) Докажем, что из любого параллелограмма с b = 4, i = 1 серией удалений/добавлений треугольников можно получить параллелограмм на рис. 2 б. Тем самым мы сведем нашу задачу к задаче 13 б. Пусть Гл. 14. Комбинаторная геометрия наш параллелограмм. Треугольник AOB простой. Если он минимальный, то наш параллелограмм совпадает с параллелограммом на рис. 2 б. Иначе рассмотрим последовательность прыжков треугольника, переводящую его в минимальный (см. задачу 3 e)), и будем на каждом шаге достраивать треугольник AOB до параллелограмма. Легко видеть, что любые два соседних параллелограмма в построенной цепочке получаются друг из друга серией удалений/добавлений треугольников. Наше утверждение доказано. См. рис. 8. Докажем, что картинки на риса, б выглядят именно так. Пусть точка A на риса имеет координаты (u, v), а прямая l задается уравнением ax + by = 1. Тогда A ∈ l ⇐⇒ au + bv = 1 ⇐⇒ l ∗ ∈ что и требовалось. Далее, пусть l — прямая, на которой лежат точки на рис. 8 б. Тогда из предыдущего рассуждения следует, что три прямые, и имеют общую точку Докажем теперь последнее утверждение задачи 10. Пусть точка имеет координаты (a, b), тогда ax + by = 1 — уравнение прямой C ∗ . Докажем, что C ∗ ⊥ OC. Если A(x 1 , y 1 ) и B(x 2 , y 2 ) — две различные точки на прямой ax + by = 1, то a(x 1 − x 2 ) + b(y 1 − y 2 ) = 0. Это означает, что скалярное произведение векторов # AB и OC равно нулю, те Остается проверить, что ρ(O, C ∗ ) · OC = 1, те. что расстояние ρ от начала координат до прямой ax + by = 1 равно+ b 2 . Пусть X и Y точки пересечения нашей прямой с осями Ox и Oy соответственно. Их координаты равны X 1 a , и Y 0, 1 b . Посчитаем двумя способами площадь S треугольника XOY . С одной стороны, S = 1 2 OX · OY = 1 2ab l A C B A b а б в г Рис. 8 Теорема о 12 С другой, S = 1 2 ρ · XY = ρ √ a 2 + b 2 2ab . Сравнивая найденные выражения для S, получаем требуемое. Заметим, что прямая, двойственная точке A, есть нечто иное как поляра этой точки относительно единичной окружности. Доказательство основано наследующем замечании (которое следует из задачи 3 е — единственный узел внутри M ⇐⇒ для любых двух соседних узлов A и B на границе M площадь треугольника AOB равна Для доказательства равносильности двух определений двойственного многоугольника достаточно проверить, что вектор # OC, где C = = (AB) ∗ , получается из AB поворотом напротив часовой стрелки. Согласно задаче 10 AB ⊥ OC. По той же задаче ρ(O, AB) · OC = = 1. С другой стороны, согласно замечанию, сделанному выше 2 = = S(AOB) = 1 2 ρ(O, AB) · AB. Значит, AB = OC. Тем самым установлено, что OC получается из AB поворотом на 90 ◦ . Легко видеть, что если граница M ориентирована почасовой стрелке, то этот поворот происходит против часовой стрелки. Для доказательства равенства M = достаточно заметить, что стороны многоугольника M ∗ двойственны вершинам исходного. Действительно, поскольку A i ∈ A i−1 A i и A i ∈ A i A i+1 , то (A i−1 A i ) ∗ ∈ A ∗ i и (A i A i+1 ) ∗ ∈ A ∗ i , те. прямая A ∗ i содержит сторону двойственного многоугольника. Предположим, что внутри есть еще один узел Q, отличный от O. Тогда он расположен внутри некоторого треугольника AOB, где и B — пара соседних вершин многоугольника M . Треугольники и OQB — простые, по задаче 3 е) их площади равны 1/2. Отсюда следует (смотри решение задачи 5 а, что Q лежит на медиане OM . По определению на границе M найдутся три узла D, E и F , такие что DE = # OA и EF = # OB. Легко видеть, что DF k OM, следовательно k OQ. Но DF = 2OM > 2OQ, поэтому внутри DF есть хотя бы целые точки. Так как M — выпуклый, есть две возможности либо лежит внутри M , либо DF — часть границы M . В первом случае получаем, что внутри M содержится хотя бы 2 узла. Во втором случае = DEF вообще не содержит внутри себя узлов. Получаем противоречие. Значит, такого узла Q не найдется. а) Нам достаточно доказать, что, например, удаление простого треугольника из M приводит к добавлению простого треугольника к рис. 9). Здесь через A kl обозначена такая точка Гл. 14. Комбинаторная геометрия A 34 A 23 A 13 A 12 A n1 O A 4 A 3 A 2 A 1 O Рис. что # OA kl = # A k A l . В частности, если l = k + 1, то A kl — вершина многоугольника. Удалим A 1 A 2 A 3 . Тогда у многоугольника исчезнут вершины и A 23 , зато добавится новая вершина A 13 . Ее еще нужно соединить отрезками си. Покажем, что точки и лежат на этих отрезках. В самом деле, так как O — единственная целая точка внутри M , то треугольники A 1 OA 3 , A 2 OA 3 , A 4 OA 3 простые. Из формулы Пика следует, что их площади равны 1/2. Поскольку они имеют общее основание OA 3 , то проекции векторов # A 1 A 3 , # и # на перпендикуляр к равны. Отсюда следует, что точки A 13 , и лежат на одной прямой, атак как M — выпуклый, толе- жит между двумя остальными (это очевидно также из второго определения двойственного многоугольника. Аналогично доказывается, что A 12 принадлежит отрезку A n1 A 13 . Значит, преобразование сводится к добавлению треугольника A 12 A 13 A 23 . Заметим, что треугольник OA 12 A 13 получается из простого треугольника параллельным переносом, а OA 23 A 13 — центральной симметрией. Поэтому треугольник простой, что и требовалось. б) Действительно, предположим вначале, что уесть диагональ, не проходящая через O. Разрежем M вдоль этой диагонали и рассмотрим ту из полученных частей, которая не содержит O. Эта часть обязательно содержит простой треугольник вида A i−1 A i A i+1 . Удалим его, уменьшив тем самым число b. Будем действовать так, пока это возможно. Очевидно, есть только три случая, когда требуемой диагонали не найдется) b = 4, M = ABCD, O = AC ∩ BD. Так как отрезки OA, OB, и OD не содержат целых точек, то OA = OC и OB = OD, те искомый параллелограмм) b = 4, M = ABCD, один из углов, скажем BCD, — развернутый. В этом случае обозначим через точку, симметричную точке относительно O, через E — середину D ′ B. Искомая серия удале- Теорема о 12 399 ний/добавлений треугольников имеет вид → AEBCD → AD ′ EBCD → AD ′ ECD → рис. 10 слева) b = 3, M = ABC. В этом случае обозначим через и C ′ точки, симметричные относительно O вершинами соответственно. Тогда искомая серия имеет вид → AC ′ BC → AC ′ BA ′ C → рис. 10 справа). Рис. Тем самым в каждом случае мы получили требуемый параллело- грамм. в) Из пункта а) получаем, что при удалении/добавлении треугольника величина b + сохраняется. Согласно пункту б) данный многоугольник можно перевести в параллелограмм с b = 4 серией удале- ний/добавлений треугольников. Для такого параллелограмма b + b ∗ = = 12 (задача 2). Теорема о 12 доказана. Примерна рис. 1 д показывает, что замкнутая ломаная, двойственная к невыпуклому многоугольнику, может иметь самопересечения. Поэтому теорему о 12 естественно пытаться обобщить сразу именно на этот случай. Итак, пусть M — замкнутая ломаная с вершинами в узлах, возможно самопересекающаяся. Замечание вначале решения задачи 11 подсказывает, каким условием нужно заменить в нашей ситуации условие того, что O — единственный узел внутри M . Нужно потребовать, чтобы для каждого звена AB ломаной площадь треугольника равнялась 1/2 (при этом мы считаем все узлы, попавшие на ломаную, ее вершинами, возможно с углом 180 ◦ ). Именно при этом условии (плюс условие положительности всех сторон, приведенное ниже) два определения двойственного многоугольника равносильны Гл. 14. Комбинаторная геометрия Мы предлагаем в этом месте читателю прервать чтение и попытаться, рассмотрев несколько примеров, самому придумать обобщение теоремы она самопересекающиеся ломаные. Ответ выглядит следующим образом. Назовем звено AB ломаной положительным, если при движении точки X по нему от A кот- резок OX вращается почасовой стрелке, и отрицательным — иначе. Корректность данного определения следует из того, что площадь треугольника равна 1/2, в частности, точки A, O и B не лежат на одной прямой. Обозначим через и количество положительных и отрицательных звеньев ломаной L соответственно, а через и аналогичные числа для L ∗ . Теперь может быть сформулирована Теорема о 12 для ломаных. Пусть M — замкнутая ломаная с вершинами в узлах (причем все узлы, попавшие на M, мы считаем вершинами, возможно с углом 180 ◦ ). Пусть нашелся такой узел что для каждого звена AB ломаной M площадь треугольника равна 1/2. Предположим, что M делает r оборотов вокруг точки Тогда b + − b − + b ∗ + − b ∗ − = Эта теорема доказана в статье [7]. Ее элементарное доказательство неизвестно. Кривая, двойственная к единичной окружности, — она сама, что следует из задачи 10. Рис. 11 завершает риса б в г Рис. Для любой гладкой кривой γ действительно γ ∗∗ = γ. Приведем неформальное доказательство этого утверждения. Рассмотрим кри- Теорема о 12 401 вую γ ∗ . Чтобы построить двойственную к ней кривую, нужно рассмотреть касательные к γ ∗ . Вместо касательной мы возьмем на две близкие точки и проведем через них прямую (верхняя часть рис. 11 г. Двойственная картинка будет выглядеть как на нижней части рис. 11 г. Если начать сближать выбранные точки на кривой γ ∗ , то наша прямая (секущая) будет стремиться к касательной, а двойственная ей точка будет стремиться к точке на кривой γ. Это и означает, что множество касательных прямых к определяет исходную кривую γ, те Более подробно о двойственных кривых написано в замечательной статье [5]. 16. Ответ авторам неизвестен. а) Ответ можно. б) Ответ нельзя. Доказательство. Предположим, что требуемый набор ломаных существует. Раскрасим узлы клетчатой решетки в шахматном порядке. Тогда все вершины — одного цвета, пусть для определенности белого. Тогда во всей решетке, кроме вершин, черных узлов на 3 больше. Каждая ломаная соединяет два узла на границе. При этом ломаная, соединяющая два черных узла, содержит черных узлов на 1 больше, чем белых. Ломаная, соединяющая два белых узла наоборот, а ломаная с концами разного цвета — поровну. Поэтому на границе прямоугольника черных узлов должно быть ровно на 6 больше, чем белых. А в действительности черных узлов там на 4 больше, чем белых. Получаем противоречие, те. требуемого набора ломаных не существует. Ответа) при p, q > 3 и четном (p − 1)(q − 1); б) (p − 1)(q − в − 1)(q − 1) 2 − 1. Решение легко следует из соображений четности и формулы Пика. Пункта) сразу получается из формулы Пика, а также может быть доказан аналогично этой формуле (см. замечание после решения задачи В пункте б) можно предложить несколько различных формул, например или (M ) = n(2M ) − 2n(M) − b(M) + Эти формулы доказаны в интересной статье [2]. В ней также объясняется, как можно получить все такие формулы. Рекомендуем также статью [3] того же автора Гл. 14. Комбинаторная геометрия. Обозначим через n(i) максимальное число вершин выпуклого многоугольника с ровно i узлами внутри. Приведем значения n(i) при малых i: i 0 1 2 3 4 5 n(i) 4 6 6 6 8 Равенства n(0) = 4 и n(1) = 6 фактически доказаны в задаче 4 б, в). Для доказательства равенства n(2) = 6 достаточно провести прямую через две внутренние точки и рассуждать далее аналогично решению 4 в). Для больших i жюри известна следующая оценка для числа n(i): n(i) 6 2i при i > Для доказательства рассмотрим выпуклую оболочку i внутренних узлов. Это либо отрезок, либо многоугольник сне более чем i вершинами. В первом случае, рассуждая аналогично решению задачи 4c, легко получить оценку n(i) 6 6. Во втором случае возьмем произвольную точку O (необязательно узел) внутри выпуклой оболочки и проведем из нее лучи через все вершины выпуклой оболочки. Выбором точки можно добиться, чтобы вершины исходного многоугольника не попали на наши лучи. Если число вершин n(i) > 2i, то по принципу Дирихле водной из частей, на которые разбивают плоскость проведенные лучи, найдется хотя бы 3 вершины. Вместе с двумя вершинами выпуклой оболочки, принадлежащими той же части, они образуют выпуклый пятиугольник без узлов внутри, что противоречит задаче 4 б. Требуемая оценка доказана. Известна также оценка n(i) 6 с некоторой константой C, но доказательство довольно сложно. Интересное замечание n(5) < n(4)(!). 21. а) Классификация выпуклых многоугольников без узлов внутри приведена в статье б) Классификация выпуклых многоугольников с ровно 1 узлом внутри приведена в статье [7] (правда без доказательства. Оказывается, существует всего 16 таких многоугольников с точностью до аффинного преобразования. Доказательство основано на той же идее, что ив пункте а) (смотри статью [6]). 22. а) Ответ прямая ax + by = б) Число решений уравнения x 2 + ax + b = 0 равно числу решений системы = −x 2 , y = ax + b. Теорема о 12 Преобразованием (x, y) 7→ x эта система сводится к системе считаем Число решений этой системы равно количеству точек пересечения кривой и прямой ax + by = 1. Но это тоже самое, что количество касательных, которые можно провести из точки (a, b) к двойственной кривой (см. рис. 11 г. Остается заметить, что кривая x 2 = 4y двойствен- на кв чем можно убедиться, например, с помощью дифференцирования. Для кубического уравнения рассуждения аналогичны. в) Ответ: 3, если D < если D = 0 и ab 6= если D > 0 или a = b = где D = 4a 3 + 27b 2 — дискриминант кубического уравнения. Решение поясняет рис. 11 б. Подробнее о двойственных кривых и их связи с решением уравнений можно прочитать в статье [5]. Любопытно, что при определении числа решений систем алгебраических уравнений естественным образом возникают многоугольники с вершинами в узлах клетчатой бумаги (так называемые многоугольники Ньютона. О многоугольниках Ньютона можно прочитать в интересных статьях [2], Литература Васильев Н. Б. Вокруг формулы Пика // Квант. 1974. № 12. [2] Кушниренко А. Целые точки в многоугольниках и многогранниках Квант. 1977. № 4. [3] Кушниренко А. Многоугольник Ньютона // Квант. 1977. № 6. [4] Реповш Д, Скопенков М, Ценцель М. Б. Элементарное доказательство теоремы о 12 целых точках // Матем. заметки. 2005. Т. вып. 1. С. 117–120. [5] Табачников С. Л. Геометрия уравнений // Квант. 1988. № 10. [6] Хованский А. Г. Многоугольники Ньютона, кривые на торических поверхностях и обращение теоремы Вейля // Успехи матем. наук. Т. 52, вып. 6. С. 113–142. [7] Poonen B., Rodriguez-Villegas F. Lattice polygons and the number 12 // Amer. Math. Mon. 2000. V. 107, № 3. P. 238–250. Гл. 14. Комбинаторная геометрия Третья проблема Гильберта и разрезания прямоугольника 2) (10–11) В. В. Прасолов, М. Б. Скопенков Данная подборка посвящена решению следующих двух задач. Задача A. Третья проблема Гильберта. Докажите, что правильный тетраэдр нельзя разрезать наконечное число многогранников, из которых складывается куб. Задача B. Комната имеет форму прямоугольника с отношением сторон x. Пол в комнате выложен прямоугольными плитками с таким же отношением сторон, причем хотя бы одна плитка ориентирована поперек комнаты, а не вдоль нее (рис. 1). Докажите, что x является корнем многочлена с целыми коэффициентами Рис. Удивительно, что решить ю проблему Гильберта можно, изучая только разрезания прямоугольников, а не многогранников В данном цикле задач будет предложен новый вариант элементарного решения 3-й проблемы Гильберта, основанный на этой идее. Что касается задачи B, то, оказывается, ее можно решить с помощью. физической интерпретации А именно, каждому разрезанию прямоугольника мы сопоставляем электрическую схему, составленную из сопротивлений. Разрежьте куб на 6 равных тетраэдров. Выложите плитками комнаты с указанным отношением сторон, как это требуется в задаче а) x б) x = p p/q, p и q — целые; в) x Авторы благодарны С. Дориченко, А. Заславскому, К. Кохасю, Б. Френкину, Г. Челнокову и А. Шаповалову за полезные обсуждения Третья проблема Гильберта и разрезания прямоугольника 405 г)* x = √ r, где r — периодическая цепная дробь; д)* x = √ s, где s — корень кубического многочлена с целыми коэффициентами без рациональных корней (требуется построить замощение для какого-нибудь одного значения s, удовлетворяющего условию); е) выложите произвольную комнату n плитками, ориентированными вдоль комнаты, n > 4, n 6= Третья проблема Гильберта сведение к планиметрической задаче Пусть M — многогранник. Занумеруем его ребра числами 1, 2, . . . , Пусть l 1 , l 2 , . . . , l n — длины соответствующих ребер, α 1 , α 2 , . . . , двугранные углы при соответствующих ребрах. Сопоставим многограннику набор прямоугольников l i × α i на плоскости, у которых стороны горизонтальны, а стороны α i вертикальны (рис. 2). l Рис. Будем называть два таких набора прямоугольно равносоставленны- ми (-равносоставленными), если прямоугольники одного набора можно разрезать на несколько меньших прямоугольников, из которых можно сложить второй набор, используя только параллельные переносы частей (рис. 3). Назовем два многогранника равносоставленными, если один из них разрезается на несколько меньших многогранников, из которых можно сложить второй многогранник, как угодно поворачивая части 5 4 4 2 2 3 3 1 Рис. Следующая лемма сводит вопрос о равносоставленности многогранников к задаче планиметрии. Лемма 1. Если два многогранника равносоставленны, то соответствующие им наборы прямоугольников будут -равносоставленны после добавления к ним подходящих прямоугольников вида l × π. Гл. 14. Комбинаторная геометрия Доказательство этой леммы содержится в задаче Предположим, что выпуклый многогранник M разрезан намного- гранники M 1 , M 2 , . . . , M k 3. а) Пусть e — ребро многогранника M, l — его длина, а α — двугранный угол при этом ребре. Обозначим через l 1 , l 2 , . . . l длины всех ребер многогранников M i , лежащих на ребре e, а через α 1 , α 2 , . . . , двугранные углы при соответствующих ребрах. Тогда прямоугольник l × α можно разрезать на n прямоугольников l 1 × α 1 , . . . , l n × α n б) Пусть ℓ — прямая в пространстве, не содержащая ребер многогранника. Пусть l 1 , l 2 , . . . l n — длины всех ребер многогранников лежащих на прямой ℓ, а α 1 , α 2 , . . . , α n — двугранные углы при соответствующих ребрах. Тогда набор n прямоугольников l 1 × α 1 , . . . , l n × α n -равносоставлен c некоторым прямоугольником видав) Докажите лемму Чтобы доказать, что правильный тетраэдр и куб одинакового объема не равносоставленны, мы покажем, что соответствующие им наборы прямоугольников не равносоставленны. Для этого нам потребуется следующее утверждение. г) Докажите, что двугранный угол θ при ребре правильного тетраэдра несоизмерим с Таким образом, решение задачи A сводится к следующему утвер- ждению. Лемма 2. Если θ и π несоизмеримы те, то при любых a и b прямоугольники a × θ и b × π не -равносоставленные. Более того, они остаются не -равносоставленными после добавления к ним любых прямоугольников вида l × Третья проблема Гильберта решение планиметрической задачи В этом разделе мы докажем лемму 2. Доказательство содержится в пунктах задачи Пусть дан некоторый набор прямоугольников. Можно получить новый набор, разрезав один изданных прямоугольников на два новых. Такую операцию назовем элементарным преобразованием набора. а) Если два набора прямоугольников -равносоставленны, то один из них можно получить из другого последовательностью элементарных преобразований и обратных к ним. Пусть θ и π несоизмеримы. Предположим, что из прямоугольника a × θ получили прямоугольник b × π последовательностью элементарных преобразований и обратных к ним. Пусть θ, π, y 1 , y 2 , y 3 , . . . , y N — Третья проблема Гильберта и разрезания прямоугольника 407 длины вертикальных сторон всех прямоугольников, которые возникали в данной последовательности элементарных преобразований. Обозначим, б) Можно выбрать такие числа y ′ 1 , y ′ 2 , . . . , y ′ n ⊂ Y , чтобы любое число y ∈ Y единственным образом представлялось в виде y = pθ + qπ + p 1 y ′ 1 + p 2 y ′ 2 + . . . + p где числа p, q, p 1 , p 2 , . . . , p n — рациональные. Зафиксируем набор таких чисел y ′ 1 , . . . , как в задаче 4 б. Для числа y ∈ Y обозначим f(y) = p, где p — коэффициент при θ в представлении Если M — набор прямоугольников x 1 × y 1 , x 2 × y 2 , . . . , x n × y n , где все y i ∈ Y , то положим ) = x 1 f (y 1 ) + x 2 f (y 2 ) + . . . + x n f (y в) Величина J(M ) не меняется при элементарном преобразовании набора M г) Докажите лемму д) Докажите теорему Дена: правильный тетраэдр и куб не равносо- ставленны. Наш метод позволяет установить и другие интересные факты о раз- резаниях фигура) Докажите другую теорему Дена: если прямоугольник a × b разрезан на квадраты, то a b рационально. б) Докажите, что правильный тетраэдр нельзя разрезать на несколько (больше 1) правильных тетраэдров. Разрезания прямоугольника и электрические схемы Разрезанию прямоугольника на прямоугольники можно сопоставить электрическую схему, как показано на рис. 4. Каждому прямоугольнику соответствует резистора каждой вертикальной линии разреза (а также вертикальным сторонам исходного прямоугольника) — узел, в котором соединяются несколько резисторов. Сопротивление каждого резистора равно отношению горизонтальной стороны соответствующего прямоугольника к вертикальной. Можно показать, что общее сопротивление данной схемы равно отношению сторон разрезаемого прямоугольника. Покажем, как искать общее сопротивление электрической схемы Гл. 14. Комбинаторная геометрия 5 4 2 3 Рис. Рассмотрим электрическую схему из резисторов. Пусть для каждого резистора задано его сопротивление R k . Зафиксируем начало и конец схемы, а также число U > 0 (напряжение схемы. Каждому узлу сопоставим действительное число U i , которое будем называть напряжением в данном узле, следующим образом. В начальном узле напряжение положим равным нулю, а в конечном — равным U . В остальных узлах выберем напряжения так, чтобы сумма величин по всем резисторам была минимальна, где △U k — разность напряжений на концах го резистора. Обозначим эту сумму через P , она называется общим выделением тепла схемы. Общим сопротивлением схемы называется величина R Будем считать известным, что распределение напряжений с минимальным выделением тепла существует. Пример 1. Рассмотрим схему из двух резисторов и R 2 , соединенных параллельно. По определению P = U 2 R 1 + U 2 R 2 , и общее сопротивление равно R = U 2 P = R 1 · R 2 R 1 + Пример 2. Рассмотрим схему из двух резисторов и R 2 , соединенных последовательно. Пусть U 1 — напряжение в их общем узле. Величина должна быть минимальной. Это квадратный трехчлен относительно U 1 . Находя получим R = R 1 + Элементарным преобразованием электрической схемы называется одна из следующих операций) замена одного резистора с сопротивлением R 2 R 1 + на два параллельно соединенных резистора и R 2 ; 2) замена одного резистора с сопротивлением R 1 + на два последовательно соединенных резистора и R 2 ; Третья проблема Гильберта и разрезания прямоугольника 409 R 4 R 3 R 2 R 1 • • • • • • Рис. 5 3) объединение двух узлов с одинаковым напряжением. Найдите общее сопротивление и соответствующее разбиение прямоугольника для схема) на рисунке 4 при R 1 = R 2 = R 3 = R 4 = б) на риса) Пусть квадрат разрезан на квадраты и прямоугольники, у которых отношение горизонтальной стороны к вертикальной равно R. Тогда соответствующая электрическая схема состоит из резисторов сопротивлением и R и имеет общее сопротивление б Электрическая схема состоит из резисторов сопротивлением и R. Докажите, что сопротивление всей схемы выражается в виде (где P (x) и Q(x) — многочлены с целыми коэффициентами. в) Пусть напряжения в двух узлах, соединенных с некоторым резистором, различны. Докажите, что общее сопротивление схемы растет с ростом сопротивления этого резистора г) Решите задачу д (Решение этой задачи авторам неизвестно) Верно ли, что выложить комнату так, как это требуется в задаче B, можно тогда и только тогда, когда число x является корнем многочлена степени n с целыми коэффициентами, имеющего ровно n − 1 отрицательный корень? Замечание. Силой тока на резисторе называется величина I k = = △U k R k , где △U k — разность напряжений между узлами, соединенными с резистором. Покажем, что сумма сил тока на резисторах, выходящих из неконцевого узла, равна нулю. Зафиксируем некоторый неконцевой узел. Перенумеруем узлы так, чтобы этот узел был первым, а сопротивления резисторов, выходящих из этого узла, были R 1 , R 2 , . . . , Посмотрим, как зависит общее выделение тепла схемы от U 1 . Общее выделение тепла равно n X i=1 (U i − U 1 ) 2 R i + C, Гл. 14. Комбинаторная геометрия где C — константане зависящая от U 1 . Минимум достигается в вершине параболы, те. при n P i=1 или, что тоже самое, при n X i=1 U i − U 1 R i = Из наших определений следуют законы Кирхгофа) сумма сил токов на резисторах, выходящих из одного узла, равна нулю) I 1 R 1 + I 2 R 2 + . . . + I n R n = U для любого пути 1, 2, . . . , n от начала к концу, где U — общее напряжение, независящее от пути. Обратно, из законов Кирхгофа следует, что токи распределяются так, чтобы общее выделение тепла было минимальным. Зачетные задачи 3 а, г 4 в, г). Контрольные вопросы. Рассмотрим набор прямоугольников, соответствующий правильному тетраэдру со стороной a и двугранными углами θ между гранями. Какому из следующих прямоугольников прямоугольно равносоставлен этот набора) 4a × б) 4a × 4θ; в) 6a × θ; г) 6a × 6θ. II. Насколько равных правильных тетраэдров можно разрезать правильный тетраэдра) На любое число тетраэдров; б) только на 1, 8, 27, 64, . . . тетраэдров (те. количество должно быть точным кубом); в) ни на какое число тетраэдров, большее 1. |