Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
 Скачать 2.18 Mb.
|
|
Задача 3 . Напомним, что мерный двоичный куб — это граф, вершинами которого являются двоичные последовательности длины и две вершины соединены ребром тогда и только тогда, когда их соответствующие члены равны за исключением одного случая. Тогда наша задача эквивалентна следующей докажите, что если из мерного двоичного куба удалить 8 рёбер, то получим всегда га- мильтонов граф (те. в нём найдётся гамильтонов цикл — замкнутый путь, содержащий все вершины графа ровно по одному разу). Индукцией по докажем следующее более общее утверждение: если из n-мерного двоичного куба, n > 1, удалить любые n − 2 ребра, то полученный граф будет гамильтоновым. Доказательство. Для n =2 утверждение очевидно, так как ничего удалять не нужно. Допустим, что для k > 1 утверждение верно, докажем его для k + Пусть {(a 0 , a 1 , . . . , a 𝑘 ): a 𝑖 ∈ {0, 1}, 0 ¶ i ¶ k} — множество вершин+ мерного куба C = 〈V, E〉, где E — множество его рёбер. Выберем любое удалённое ребро E. Без ограничения общности можно считать, что оно соединяет вершины (0, b 1 , . . . , и (1, b 1 , . . . , b 𝑘 ). Тогда рассмотрим множества вершин {(0, a 1 , . . . , a 𝑘 ): a 𝑖 ∈ {0, 1}, 1 ¶ i ¶ и {(1, a 1 , . . . , a 𝑘 ): a 𝑖 ∈ {0, 1}, 1 ¶ i ¶ образующие разбиение множества, и соответствующие им подграфы C 0 = 〈V 0 , E V 0 〉 и C 1 = 〈V 1 , E Под записью V 0 〉 понимается множество рёбер из E, соединяющие вершины из Решения задач МОШП 2010 Заметим, что каждый из подграфов C 0 и C 1 идентичен k-мерному двоичному кубу. Зададим естественное отображение (0, a 1 , . . . , a 𝑘 ) = = (1, a 1 , . . . , a 𝑘 ), которое переводит C 0 в C 1 Пусть D ⊂ E — множество удалённых рёбер, |D| = n − 2 = k − Тогда имеем разбиение D 0 ∪ D 1 ∪ D 2 , где множество рёбер, удалённых из подграфа C 𝑖 , i = 0, 1, а D 2 — множество удалённых р- бер, «соединяющих» C 0 и C 1 . В частности Так как f (D 0 ) ∪ D 1 | ¶ k − 2, по индукционному предположению в C 1 найдётся гамильтонов цикл v 1 , v 2 , . . . , v 2 𝑘 , не использующий рёбра из (D 0 ) ∪ D 1 . Тогда u 1 , u 2 , . . . , u 2 𝑘 — гамильтонов цикл в C 0 , где f (u 𝑖 ) = для 1 ¶ i ¶ 2 𝑘 , не проходящий через рёбра из D 0 Так как при ¾ 2 имеем 2 𝑘 > 2(k − 1), по принципу Дирихле для некоторого, 1 < i < 2 𝑘 , найдутся рёбра ( u 𝑖 , v 𝑖 ) и ( u 𝑖 +1 , v 𝑖 +1 ), не принадлежащие Тогда цепочка u 1 , u 2 , . . . , u 𝑖 , v 𝑖 , v 𝑖 −1 , . . . , v 1 , v 2 𝑘 , v 2 𝑘 −1 , . . . , v 𝑖 +1 , u 𝑖 +1 , . . . , будет гамильтоновым циклом вне проходящим через рёбра из. Утверждение доказано. Задача_4_.'>Задача 4 . Во-первых, заметим, что уравнение x 2 − py 2 = 1 имеет бесконечно много решений в натуральных числах (уравнение Пелля). Тогда для любого простого числа существует бесконечно много таких натуральных чисел и t, что s 2 − 1 = pt 2 . Положив s 2 − 1, y = s + 1, z = s − 1, получим+ s 2 − 1)( y 2 + s 2 − 1)(z 2 + s 2 − 1) = = (s 2 − 1)s 2 ( s + 1)(2s)(s − 1)(2s) = ((s 2 − Осталось проверить, что, y, z 6= t. Заметим, что x = s 2 − 1 = pt 2 6= Если s + 1 = t, то (s − 1)(s + 1) = pt 2 = p(s + 1) 2 , откуда следует, что s − 1 = p(s + 1) > s + 1 > s − 1, и мы получаем противоречие. Если же, то (s−1)(s+1)= pt 2 = p(s−1) 2 , откуда следует, что s +1=p(s−1)¾2(s−1)>s+1, и мы получаем противоречие для я олимпиада, 2010 год Задача 1 . Из условия ADB + ∠ ACB = ∠CAB + ∠DBA = следует, что ADC + ∠DCB = ∠ ADB + ∠BDC + ∠ ACD + ∠ ACB = = 30 ◦ + ∠ABD + ∠CAB = 60 ◦ , Решения задач МОШП Рис. поэтому ∠DAB + ∠ABC = 300 ◦ . Нетрудно понять, что ∠A и ∠B больше Построим точку , находящуюся по разные стороны отита- кую, что треугольник равносторонний (см. рис. 41 ). Заметим, что = 360 ◦ − ∠A − ∠BAX = 300 ◦ − ∠A = ∠B, ∠CBX = 360 ◦ − ∠B − ∠ABX = 300 ◦ − ∠B = Но тогда треугольники и CBA равны и треугольники DAB, тоже равны. Следовательно, DX = AC, CX = DB. Осталось лишь проверить, что = 90 ◦ . Действительно = ∠DXA + ∠ AXB + ∠BXC = ∠CAB + 60 ◦ + ∠DBA = 60 ◦ + 30 ◦ = Задача. Пусть p > 2011 — нечётное простое число, являющееся делителем числа. Тогда из соотношения 2010! ≡ −1 (mod p) и из теоремы Вильсона ( p − 1)! ≡ −1 (mod p) при простом p следует, что 1)(p − 2) . . . (p − (p − 2011)) ≡ 1 (mod p) ⇒ ⇒ (−1)(−2) . . . (−(p − 2011)) ≡ 1 (mod p) ⇒ ⇒ (p − 2011)! ≡ 1 (mod а) Если число 4021 не является простым, то число не может делиться на 4021, так как число 2010! делится на делители числа Если же число 4021 простое (что на самом деле является истиной, то из соотношения (1) имеем 2011)! = (2010)! ≡ 1 6≡ −1 (mod б) Аналогично если какое-то из чисел 2027, 2029, 2039 не является простым, то получим противоречие, как в пункте a). Поэтому будем считать, что они простые (а это также верно на самом деле Решения задач МОШП 2010 Для числа 2027 из соотношения (1) имеем 1 (mod Для получения противоречия докажем, что число 16! не является квадратичным вычетом по модулю 2027. Вычислим символ Лежандра (см. справочные материалы нас поскольку (мы используем квадратичный закон взаимности 2027 = −1, 5 2027 = 2027 5 = 2 5 = −1, 11 2027 = − 2027 11 = −3 11 = 2 3 = −1, 13 2027 = 2027 13 = 12 13 = 3 13 = Для числа 2029 из соотношения (1) имеем 1 (mod Вычислим символ Якоби (Лежандра = 5 · 11 · 13 · 17 2029 = 5 2029 11 2029 13 2029 17 2029 = поскольку 2029 = 2029 5 = 4 5 = 1, 11 2029 = 2029 11 = 5 11 = 11 5 = 1 5 = 1, 13 2029 = 2029 13 = 1 13 = 1, 17 2029 = 2029 17 = 6 17 = 17 6 = −1 6 = Для числа 2039 из соотношения (1) имеем 1 (mod Вычислим символ Якоби (Лежандра = 2 · 3 · 17 · 19 · 23 2039 = = 2 2039 3 2039 17 2037 19 2039 23 2039 = −1, Решения задач МОШП поскольку 2039 = 1, 3 2039 = − 2039 3 = − 2 3 = 1, 17 2039 = 2039 17 = 16 17 = 1, 19 2039 = − 2039 19 = − 6 19 = − 2 · 3 19 = −1, 23 2039 = − 2039 23 = − 15 23 = − 3 · 5 23 = Примечание. На самом деле можно не использовать символ Якоби, а посчитать напрямую каждый раз брать промежуточный результат по модулю простого числа. Например (15! (mod 2027)) · 16 (mod 2027) и т. д. В результате можно получить 765 (mod 2027), 18! ≡ 271 (mod 2029), 28! ≡ 2034 (mod в) Можно проверить, что кроме рассмотренных простых чисел, б´ ольших 2011 и меньших 2050, осталось только число 2017. Для него из соотношения (1) получаем, что 6! = 720 ≡ 1 (mod 2017), чего быть не может. Таким образом, осталось лишь доказать, что число не может быть степенью простого числа 2011. А это верно по теореме Лиувилля (см. например, книгу В. Серпинского «250 задач по теории чисел, М.: Просвещение, Существует очень много доказательств теоремы Лиувилля. При- ведём одно из них для Будем рассуждать от противного. Пусть для некоторого натурального числа верно равенство (p − 1)! + 1 = p 𝑚 . Так как число (p − 1)/2 не превосходит p − 2, оно делит (p − 2)!. Следовательно 2)! = p 𝑚 − 1 p − 1 = p 𝑚 −1 + . . . + 1 . Но 1 (mod q), поэтому p 𝑚 −1 + . . . + 1 ≡ m (mod q). Следовательно. Если q, то m ¾ 2q. Тогда (p − 1)! + 1 = p 𝑚 ¾ p 𝑝 −1 > (p − 1)! + 1. Решения задач МОШП 2010 Следовательно q, и тогда (p − 1)! + 1 = Для нашего случая имеем+ 1 = 2011 1005 ≡ (−1) 1005 ≡ −1 6≡ 1 (mod Задача. Из условия следует, что+ b 3 = ac 2 − bc 2 = c 2 ( a − Тогда по неравенству Коши — Буняковского имеем a Æ 1 − d 2 +b 2 Æ 1 + d 2 = d p a Æ a(1 − d 2 ) + Æ b 3 Æ b(1 + d 2 ) ¶ ¶ d Æ a + b 3 Æ a(1 − d 2 ) + b(1 + d 2 ) = = c Æ ( a − b)d 2 Æ a(1 − d 2 ) + b(1 + А по неравенству между средним арифметическими средним геометрическим имеем b)d 2 Æ a(1 − d 2 ) + b(1 + d 2 ) ¶ ¶ c ( a − b)d 2 + a(1 − d 2 ) + b(1 + d 2 ) 2 = c(a + b) 2 Задача 4 . Лемма. Пусть a, b 1 , b 2 , . . . , b 𝑛 — различные вершины конечного ориентированного мультиграфа (те. в таком графе могут быть кратные рёбра) G. Известно, что для каждого i, 1 ¶ i ¶ n, существует путь вот дои что любые два пути, соединяющие a с некоторой вершиной из множества B = {b 1 , b 2 , . . . , b 𝑛 }, имеют общее ребро. Тогда некоторое ребро является общим для всех путей от a до Доказательство. Через l(w) обозначим длину пути w, те. количество рёбер в нм. Пусть {w | w — простой путь от a до некоторой вершины из B}. Назовём число, B) = X 𝑤 ∈ тотальным) расстоянием от a до B. Проведём доказательство от противного. Допустим, что мульти- граф 〈V, E〉, его вершина a ∈ V и множество вершин {b 1 , b 2 , . . . , b 𝑛 } ⊆ образуют контрпример клемме с минимальным ρ(a, B), прич м для этого число вершин n является максимальным (такое Решения задач МОШП число существует, так как, очевидно, должно выполняться неравенство Утверждение 1. Для каждого i, 1 ¶ i ¶ n, существует путь от до b 𝑖 , обходящий вершины множества B 𝑖 = Доказательство. Докажем утверждение от противного. Пусть для некоторого, 1 ¶ i ¶ n, все пути от a до проходят через. Тогда, так как, B 𝑖 ) < m, в силу минимальности m существует общее ребро для всех путей от до B 𝑖 . Это ребро будет общим для всех путей от a до B, и мы получаем противоречие. Таким образом, каждая вершина b 𝑖 связана с некоторой вершиной, те, и существует путь от a до c 𝑖 , обходящий вершины из, 1 ¶ i ¶ Утверждение 2. Для каждого i, 1 ¶ i ¶ n, все простые пути от до проходят через вершину Доказательство. Докажем утверждение от противного. Допустим, что простые пути от до можно провести через соседние с a вершины c 0 1 , c 0 2 , . . . , c 0 𝑠 , где ¾ Рассмотрим новый мультиграф G 0 = 〈V 0 , E 0 〉, V 0 = (V 0 \{b 1 }) ∪ {b 0 , b 00 , . . . , где. . . , b (𝑠) — различные новые вершины, а E 0 получается из E удалением всех старых рёбер, в которых участвует, и добавлением новых рёбер (c 0 𝑖 , b (𝑖) ), 1 ¶ i ¶ Понятно, что и B 0 = B 1 ∪ {b 0 , b 00 , . . . , b (𝑠) } образуют контрпример в G 0 к лемме си Теперь понятно, что ¾ 2, иначе ребро (c 1 , b 1 ) было бы общим для всех путей от до b 1 . Докажем, что на самом деле Удалив лишние рёбра, мы можем предполагать, что в муль- тиграфе G вершина участвует только водном ребре, а именно в ребре ( c 𝑖 , b 𝑖 ), 1 ¶ i ¶ Допустим, что 2. Рассмотрим a ив мультиграфе G 00 = 〈V\{b 1 }, Так как, B 1 ) < m, существует общее ребро для всех путей вот до B 1 . Тогда и B ∗ = {b 1 , c 1 , . . . , c 𝑛 } — контрпример клемме в 〈V\B 1 , E \{(c 2 , b 2 ), . . . , (c 𝑛 , b 𝑛 ) }〉 Решения задач МОШП 2011 с, B∗) < m. Итаки мы имеем картину, изобра- b 1 b 2 c 1 c 2 a Рис. 42 жённую на рис. 42 Существуют простые пути, соединяющие с вершиной и не имеющие общих рёбер. Действительно, иначе не существовало бы контрпримера клемме в мультиграфе 〈V\{b 1 }, E\{(c 1 , b 1 ) }〉 с ρ(a, {c 1 , b 2 }) < Аналогично существуют простые пути, соединяющие с вершиной и не имеющие общих рёбер. Удалим из все вершины и рёбра, не участвующие в путях. Очевидно, в оставшемся мультиграфе a и B = = {b 1 , b 2 } будет контрпримером к лемме. К вершине c 1 приходят не менее двух рёбер, так как пути u 1 , u 2 , приходят к c 1 по разным рёбрам. С другой стороны, если к c 1 прихо- дят более двух рёбер, то одно из них обслуживает ровно один из путей. Стерев его, мы получим контрпример клемме с меньшим, B). Итак, к вершине приходят ровно два ребра, и к ней приводят по этим рёбрам пути. Если одно из этих рёбер не обслуживает ни, ни, то это ребро можно удалить и получить контрпример с меньшим, Наконец, допустим, что пути w 1 и w 2 проходят через. Тогда они выходят из c 1 по двум разным рёбрам, которые не участвуют нив одном из путей. Удалив любое из этих выходящих рёбер, получим контрпример с меньшим, B). Полученное противоречие доказывает лемму. Осталось заметить, что наша задача является частным случаем леммы при я олимпиада, 2011 год Задача 1 . Ответ Возможный пример {1, 3, 5}, A 2 = {1, 4, 6}, A 3 = {1, 2}, A 4 = = {2, 3, 6}, A 5 = {2, 4, Докажем, что объединение всех пяти множеств не может содержать менее 6 элементов. Предположим противное. Рассмотрим возможные случаи. Случай 1: |A 𝑖 | = 1 для некоторого i, 1 ¶ i ¶ 5. Тогда по условию единственный элемент множества A 𝑖 должен принадлежать всем множествам, что противоречит условию 2. Таким образом ¾ 2 для всех, 1 ¶ i ¶ 5. В частности, A 𝑖 6= при 1 ¶ i < j ¶ 5. Решения задач МОШП Случай 2: имеется не менее двух двухэлементных множества. Пусть A 1 = {a, b} и A 2 = {b, c}. Тогда существует не менее двух множеств среди, которые не содержат элемент. Эти два множества по условию 1 вынуждены содержать элементы и c одновременно. Следовательно, их пересечение содержит не менее двух элементов. Противоречие. Тогда мы можем утверждать, что существует не менее трёх множеств (пусть это будут, которые содержат более двух элементов. По формуле включения-исключения для этих трёх множеств имеем A 2 ∪ A 3 | = |A 1 | + |A 2 | + |A 3 | − |A 1 ∩ A 2 | − |A 1 ∩ A 3 | − − |A 2 ∩ A 3 | + |A 1 ∩ A 2 ∩ A 3 | ¾ 9 − 3 + |A 1 ∩ A 2 ∩ A 3 | ¾ Задача. Пусть H — середина отрезка AB. Понятно, что ∠SKB = = ∠SKC см. рис. 43 ). x y A B C S M H L K |