Выбрана 1 задача 
Убрать все задачи
Бильярдный стол имеет форму многоугольника (не обязательно выпуклого), у которого соседние стороны перпендикулярны друг другу. Вершины этого многоугольника – лузы, при попадании в которые шар там и остаётся. Из вершины A с (внутренним) углом 90° выпущен шар, который отражается от бортов (сторон многоугольника) по закону "угол падения равен углу отражения". Докажите, что он никогда не вернётся в вершину A.
Решение
|
|
 |
Условие
В стране несколько городов (больше одного); некоторые пары городов соединены дорогами. Известно, что из каждого города можно попасть в любой другой, проезжая по нескольким дорогам. Кроме того, дороги не образуют циклов, то есть если выйти из некоторого города по какой-то дороге и далее двигаться так, чтобы не проходить по одной дороге дважды, то невозможно возвратиться в начальный город. Докажите, что в этой стране найдутся хотя бы два города, каждый из которых соединен дорогой ровно с одним городом.
Подсказка
Можно рассмотреть самую длинную цепь из дорог, концы этой цепи будут искомыми городами.
Решение
Первый способ. Рассмотрим самую длинную цепь из дорог, то есть возьмём самую длинную последовательность попарно различных городов A1, A2, ..., Ak, в которой каждые два соседних города в этой последовательности соединены дорогой. Докажем, что из городов A1 и Ak выходит ровно одна дорога (соответственно в A2 и Ak–1). Пусть, например, из A1 идет дорога в некоторый город B, отличный от A2. Если B – один из городов A3, ..., Ak, то возникает цикл из дорог, что противоречит условию. Таким образом, город B отличен от городов A1, A2, ..., Ak. Следовательно, в последовательности городов B, A1, A2, ..., Ak города попарно различны и соседние города соединены дорогой. Но эта последовательность содержит больше k городов вопреки выбору последовательности A1, A2, ..., Ak.
Второй способ. См. задачу 31098 в).
Источники и прецеденты использования
| web-сайт | |
| задача |
