Выбрано 13 задач 
Убрать все задачи
Пусть M – внутренняя точка прямоугольника ABCD, а S – его площадь. Докажите, что S ≤ AM·CM + BM·DM.
В стране 1001 город, каждые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из каждого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.
В выпуклом четырёхугольнике все стороны и все углы попарно различны.
а) Может ли наибольший угол примыкать к наибольшей стороне, и при этом наименьший – к наименьшей?
б) Может ли наибольший угол не примыкать к наименьшей стороне, и при этом наименьший не примыкать к наибольшей?
а) Сколько осей симметрии может иметь клетчатый многоугольник, то есть многоугольник, стороны которого лежат на линиях листа бумаги в клетку?
б) Сколько осей симметрии может иметь клетчатый многогранник, то есть многогранник, составленный из одинаковых кубиков, примыкающих друг к другу гранями?
Найдите все такие нечётные натуральные n > 1, что для любых взаимно простых делителей a и b числа n число a + b – 1 также является делителем n.
Решил шах проверить придворного мудреца. «Вот тебе шесть шкатулок, — сказал шах, — с надписями 1, 2, 3, 4, 5, 6 на крышках. В каждой шкатулке золотая монета, которая весит ровно столько граммов, сколько написано. Ты расставляешь шкатулки как угодно в клетках прямоугольника 2×3. Потом я втайне от тебя меняю местами монеты в каких-то двух шкатулках, стоящих в соседних по стороне клетках (или ничего не меняю). Затем ты укажешь на несколько шкатулок, а я назову тебе общий вес монет в них. Если после этого правильно определишь, какие монеты я переложил, останешься при дворе. А не сможешь — прогоню вон!»
Как может действовать мудрец, чтобы выдержать испытание?
Доска 2N×2N покрыта неперекрывающимися доминошками 1×2. По доске прошла хромая ладья, побывав на каждой клетке по одному разу (каждый ход хромой ладьи – на клетку, соседнюю по стороне). Назовём ход продольным, если это переход из одной клетки доминошки на другую клетку той же доминошки. Каково
а) наибольшее;
б) наименьшее возможное число продольных ходов?
В треугольнике $ABC$ $O$ – центр описанной окружности, $H$ – ортоцентр, $M$ – середина $AB$. Прямая $MH$ пересекает прямую, проходящую через $O$ и параллельную $AB$, в точке $K$, лежащей на описанной окружности треугольника. Точка $P$ – проекция $K$ на $AC$. Докажите, что $PH\parallel BC$.
Клетки шахматной доски 8×8 занумерованы по диагоналям, идущим влево вниз, от 1 в левом верхнем до 64 в правом нижнем углу: (см. рис.). Петя расставил на доске 8 фишек так, что на каждой горизонтали и на каждой вертикали оказалось по одной фишке. Затем он переставил фишки так, что каждая фишка попала на клетку с бóльшим номером. Могло ли по-прежнему в каждой строке и в каждом столбце оказаться по одной фишке?
За круглым столом сидят десять человек, перед каждым – несколько орехов. Всего орехов – сто. По общему сигналу каждый передаёт часть своих орехов соседу справа: половину, если у него (у того, кто передаёт) было чётное число, или один орех плюс половину остатка – если нечётное число. Такая операция проделывается второй раз, затем третий и так далее, до бесконечности. Докажите, что через некоторое время у всех станет по десять орехов.
В таблице $44\times 44$ часть клеток синие, а остальные красные. Никакие синие клетки не граничат друг с другом по стороне. Множество красных клеток, наоборот, связно по сторонам (от любой красной клетки можно добраться до любой другой красной, переходя из клетки в клетку через общую сторону и не заходя в синие клетки). Докажите, что синих клеток в таблице меньше трети.
Постройте вписанно-описанный четырёхугольник по двум противоположным вершинам и центру вписанной окружности.
У выпуклого многогранника одна вершина A имеет степень 5, а все остальные – степень 3. Назовём раскраску рёбер многогранника в синий, красный и лиловый цвета хорошей, если для каждой вершины степени 3 все выходящие из нее ребра покрашены в разные цвета. Оказалось, что количество хороших раскрасок не делится на 5. Докажите, что в одной из хороших раскрасок какие-то три последовательных ребра, выходящие из A , покрашены в один цвет.
|
|
 |
Условие
У выпуклого многогранника одна вершина A имеет степень 5, а все остальные – степень 3. Назовём раскраску рёбер многогранника в синий, красный и лиловый цвета хорошей, если для каждой вершины степени 3 все выходящие из нее ребра покрашены в разные цвета. Оказалось, что количество хороших раскрасок не делится на 5. Докажите, что в одной из хороших раскрасок какие-то три последовательных ребра, выходящие из A , покрашены в один цвет.
Решение
Рассмотрим произвольную хорошую раскраску. Заметим, что общее число концов рёбер каждого цвета чётно; при этом в каждой вершине степени 3 количество концов каждого цвета имеет одинаковую чётность (их там по одному). Поэтому и в вершине A чётность их количеств также одинакова; тогда все они нечётны, и в ней сходится три ребра одного цвета и по одному ребру остальных.
Предположим, что нет хорошей раскраски с тремя последовательными рёбрами одного цвета, выходящими из одной вершины. Докажем, что тогда количество хороших раскрасок, в которых из A выходит три синих ребра, делится на 5. Тогда, очевидно, и общее количество хороших раскрасок будет делиться на 5, что противоречит условию.
Пусть из вершины A последовательно выходят ребра AB1, AB2, AB3, AB4 и AB5 (далее по циклу опять идет ребро AB1). В любой раскраске красное и лиловое рёбра из A идут не подряд (иначе и три синих ребра идут подряд). Следовательно, для концов красного и лилового ребер есть 5 вариантов: (B1, B4), (B2, B5), (B3, B1), (B4, B2), (B5, B3); обозначим соответствующие количества раскрасок через k14, k25, k31, k42, k53. Мы докажем, что
k14 ≤ k42 ≤ k25 ≤ k53 ≤ k31 ≤ k14, откуда будет следовать, что все пять чисел равны, а общее количество раскрасок делится на 5.
Покажем, что k25 ≤ k53 (остальные неравенства аналогичны). Пусть в некоторой раскраске рёбра AB2 и AB5 – не синие (пусть для определенности AB2 красное). Рассмотрим граф, вершинами которого являются вершины многогранника, а рёбрами – синие и красные рёбра. Тогда степень вершины A равна 4, а степени остальных вершин – по 2. Отсюда сразу следует, что граф распался на несколько циклов, причём два из них пересекаются только по вершине A , а остальные не пересекаются вовсе. Рассмотрим цикл, проходящий через A и содержащий AB2; тогда он содержит ещё и синее ребро, выходящее из A. Перекрасив синие рёбра этого цикла в красные и наоборот, мы получили другую хорошую раскраску.
При этом возможны три случая (см. рис.). Если цикл содержит синее ребро
AB1 или AB4 , то после перекраски три последовательных ребра (AB2, AB3, AB4 или AB1, AB2, AB3) окрашены в синий цвет; это невозможно по предположению. Значит,
в цикле есть ребро AB3, и после перекрашивания получилась раскраска, в которой красное и лиловое ребра – AB3 и AB5. При этом из разных раскрасок после перекрашивания получались разные, так как исходная раскраска восстанавливается по новой аналогичной процедурой. Поэтому k25 ≤ k53, что и требовалось.
Замечания
1. Легко видеть, что мы нигде не пользовались специфическими особенностями многогранника. Зафиксировав некоторую (вообще говоря, произвольную) циклическую нумерацию B1, B2, B3, B4, B5 соседей вершины A, мы доказали существование хорошей раскраски, в которой в один цвет покрашены три ребра, идущих из A к последовательным в этой нумерации вершинам.
2. Предположим, что в нашем многограннике есть хорошие раскраски, но откажемся от условия, что их количество не кратно 5. Сделаем еще более смелое предположение, что нам в таких условиях удалось доказать наличие хорошей раскраски, в которой три последовательных ребра, выходящие из A, покрашены в один и тот же цвет. Отсюда без труда выводится самое известное (без преувеличения!) утверждение в теории графов – гипотеза четырёх красок.
