7 класс Группа "профи"("Ш")
жүктеу/скачать 471 Kb.
|
- Бұл бет үшін навигация:
- Для самостоятельного решения
- Задача о короле и ладье
Эйлеровы пути и обходыОпределение. Путь, проходящий по каждому ребру графа ровно один раз, называется эйлеровым. Замкнутый эйлеров путь называется эйлеровым циклом. Теорема 1. Пусть в графе есть незамкнутый эйлеров путь. Тогда степени двух концов этого пути нечетны, а степени всех остальных вершин четны. Теорема 2. Пусть в графе есть эйлеров цикл. Тогда степени всех вершин четны. Упр3. На плоскости нарисованы несколько окружностей так, что с любой можно перейти на любую, не сходя с этих окружностей. Докажите, что тогда существует замкнутый путь, проходящий по всем участкам всех окружностей ровно по разу. Лемма 4. Если в графе степени всех вершин четны, то его можно представить в виде объединения циклов так, что каждое ребро входит ровно в один цикл. Теорема 5. Если в связном графе степени всех вершин четны, то в нем есть эйлеров цикл. Теорема 6. Если в связном графе степени ровно двух вершин нечетны, то в нем есть эйлеров путь с концами в нечетных вершинах. Зад7. На занятии 20 школьников решили каждый по 2 задачи, причем каждая задача была решена ровно двумя школьниками. Докажите, что можно организовать разбор всех задач так, чтобы каждый школьник рассказал ровно по одной задаче. Зад8. Из куска проволоки длиной 12 дециметров требуется спаять каркас куба с ребром в 1 дм. На какое наименьшее число частей придется предварительно разрезать этот кусок? Зад9. Город в плане выглядит как квадрат 33, каждая сторона квартала-квадратика – участок улицы длиной 100м (включая внешний контур квадрата). Какой наименьший путь придется проделать паровому катку, чтобы заасфальтировать все улицы? Для самостоятельного решенияЗад10. Можно ли сетку, состоящую из границ единичных квадратиков клетчатого квадрата 44 представить в виде объединения а) восьми ломаных длиной 5; б) пяти ломаных длиной 8? Зад11. В Вишкилэнде все авиарейсы беспосадочные, летают туда и обратно, и из любого города (с пересадками) можно долететь в любой другой. Все рейсы поделены между двумя компаниями так, что для любой пары городов все прямые рейсы между ними принадлежат только одной компании, и из любого города рейсами одной компании можно улететь в такое же число городов, в какое и рейсами другой компании. Агенту 007 предписано путешествовать, меняя компанию при каждой пересадке. Докажите, что он может из столицы перелететь в любой город. Зад12. На каждой горизонтали и каждой вертикали шахматной доски стоит не менее двух фигур. Всегда ли можно убрать несколько фигур так, чтобы на каждой вертикали и каждой горизонтали стояло ровно по две фигуры? Зад13. 100 замов получили взыскания от 100 завов. При этом каждый зав наложил по одному взысканию на 15 замов, а каждый зам получил по одному взысканию от 15 завов. Докажите, что директор может снять часть взысканий так, что у каждого зама останется по одному взысканию, и все взыскания будут наложены разными завами. Задача о короле и ладьеКлетки шахматной доски nn раскрашены в синий и желтый цвета. Докажите, что либо ладья может пройти по синим клеткам с нижнего края на верхний, либо король может пройти с левого края на правый по желтым клеткам (то есть из двух возможностей всегда есть ровно одна!) Пусть ладья не может пройти как требуется. Добавим снизу синюю горизонталь, перекрасим недостижимые с нее синие клетки в белый цвет, и сделаем жирными все стороны отрезков, отделяющие синюю клетку от желтой. Лемма1. Из каждого внутреннего узла выходит четное число жирных отрезков. Лемма2. На верхней и нижней границах нет концов жирных отрезков. Лемма3. На правой и левой границе есть концы жирных отрезков. Лемма4. Змейка может по жирным отрезкам проползти с левого края на правый. Теорема5. Король может пройти по желтым клеткам с левого края на правый. Лемма6. Если есть такая раскраска, что могут пройти и ладья, и король, то найдется раскраска для доски вдвое больших размеров, на которой ладья может пройти снизу вверх по синим и слева направо по желтым клеткам. Клетки, которые не требуются для проходов ладьи, сделаем белыми (не цветными!). Назовем такую раскраску неожиданной. Лемма7. В неожиданной раскраске нет целиком желтой горизонтали. Занумеруем горизонтали снизу вверх, и номер горизонтали назовем высотой клетки. Выберем для доски данного размера минимальную неожиданную раскраску – то есть раскраску с наименьшей возможной суммой высот цветных клеток (почему такая найдется?). Лемма8. На минимальной раскраске у каждой цветной клетки не более двух соседей ее цвета. Ситуацию, когда в квадратике 22 ровно три клетки – цветные одного цвета, а оставшаяся клетка – нижняя, назовем уголком, при этом оставшуюся клетку квадратика назовем дополнением, а клетку по диагонали от нее – вершиной уголка. Лемма9. В неожиданной раскраске есть уголок. Упр10. Дополнение уголка либо белая клетка, либо крайняя клетка маршрута противоположного цвета, либо вершина уголка противоположного цвета. Лемма11. Если дополнение уголка – белая клетка, то раскраска не минимальна. Лемма12. Если дополнение уголка – крайняя клетка маршрута противоположного цвета, то раскраска не минимальна. Лемма13. Дополнение уголка с минимальной суммой высот не является вершиной другого уголка. Лемма14. Неожиданных раскрасок не существует. Теорема15. При любой раскраске в два цвета верно ровно одно из двух: либо ладья может пройти по синим клеткам снизу вверх, либо король может пройти по желтым клеткам справа налево. Лемма16. Если существуют две непересекающиеся ломаные внутри квадрата, одна из которых соединяет верхнюю сторону с нижней, а вторая – правую с левой, то существует неожиданная раскраска некоторой шахматной доски. Теорема17. Если внутри квадрата проведены две ломаные, одна из которых соединяет верхнюю сторону с нижней, а вторая – правую с левой, то эти ломаные пересекаются. жүктеу/скачать 471 Kb. Достарыңызбен бөлісу:
|