Страница: << 51 52 53 54 55 56 57 >> [Всего задач: 385]
|
|
|
Сложность: 4
Классы: 6,7,8
|
а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?
|
|
|
Сложность: 4
Классы: 10,11
|
В некоторой стране есть 100 городов, которые связаны такой сетью дорог, что из любого города в любой другой можно проехать только одним способом без разворотов. Схема сети дорог известна, развилки и перекрестки сети необязательно являются городами, всякая тупиковая ветвь сети обязательно заканчивается городом. Навигатор может измерить длину пути по этой сети между любыми двумя городами. Можно ли за 100 таких измерений гарантированно определить длину всей сети дорог?
|
|
|
Сложность: 4
Классы: 8,9,10,11
|
В виртуальном компьютерном государстве не менее двух городов. Некоторые пары городов соединены дорогой, причём из каждого города можно добраться по дорогам до любого другого (переходить с дороги на дорогу разрешается только в городах). Если при этом можно, начав движение из какого-то города и не проходя дважды по одной и той же дороге, вернуться в этот город, государство называется сложным, иначе – простым. Петя и Вася играют в такую игру. В начале игры Петя указывает на каждой дороге направление, в котором по ней можно двигаться, и помещает в один из городов туриста. Далее за ход Петя перемещает туриста по дороге в разрешённом направлении в соседний город, а Вася в ответ меняет направление одной из дорог, входящей или выходящей из города, куда попал турист. Вася победит, если в какой-то момент Петя не сможет сделать ход. Докажите, что
а) в простом государстве Петя может играть так, чтобы не проиграть, как бы ни играл Вася;
б) в сложном государстве Вася может гарантировать себе победу, как бы ни играл Петя.
|
|
|
Сложность: 4
Классы: 8,9,10,11
|
Дан клетчатый квадрат $n\times n$, где $n$ > 1. Кроссвордом будем называть любое непустое множество его клеток, а словом – любую горизонтальную и любую вертикальную полоску (клетчатый прямоугольник шириной в одну клетку), целиком состоящую из клеток кроссворда и не содержащуюся ни в какой большей полоске из клеток кроссворда (ни горизонтальной, ни вертикальной). Пусть $x$ – количество слов в кроссворде, $y$ – наименьшее количество слов, которыми можно покрыть кроссворд. Найдите максимум отношения $\frac{x}{y}$ при данном $n$.
|
|
|
Сложность: 4
Классы: 8,9,10,11
|
В клетчатом квадрате между каждыми двумя соседними по стороне клетками есть закрытая дверь. Жук начинает с какой-то клетки и ходит по клеткам, проходя через двери. Закрытую дверь он открывает в ту сторону, в которую идёт, и оставляет дверь открытой. Через открытую дверь жук может пройти только в ту сторону, в которую дверь была открыта. Докажите, что если жук в какой-либо момент захочет вернуться в исходную клетку, то он сможет это сделать.
Страница: << 51 52 53 54 55 56 57 >> [Всего задач: 385]
Фильтр
