Страница:
<< 2 3 4 5 6 7 8 >> [Всего задач: 75]
|
|
|
Сложность: 3+
Классы: 7,8,9,10,11
|
Повесьте картину на веревочке на два гвоздя так, чтобы при вытаскивании любого
из гвоздей картина падала.
Подсказка
Вокруг каждого из гвоздей должно быть сделано равное число оборотов по и против часовой стрелки.
Решение
Вот один из возможных вариантов.
|
|
|
Сложность: 4-
Классы: 10,11
|
В городе 57 автобусных маршрутов. Известно, что:
1) с каждой остановки на любую другую остановку можно попасть без пересадки;
2) для каждой пары маршрутов найдётся, и притом только одна, остановка, на
которой можно пересесть с одного из этих маршрутов на другой;
3) на каждом маршруте не менее трёх остановок.
Сколько остановок имеет каждый из 57 маршрутов?
Решение
Пусть на каком-то маршруте a ровно n остановок. Возьмём остановку B, через которую a не проходит. Из B есть маршрут в каждую из n остановок маршрута a, причём такой маршрут ровно один, поскольку два разных маршрута не могут иметь двух общих остановок. Каждый маршрут, проходящий через B, пересекает маршрут a. Поэтому через B проходит ровно n маршрутов.
Теперь ясно, что любой маршрут b, не проходящий через остановку B, имеет ровно n остановок. Действительно, как и выше, число остановок на нём равно числу маршрутов, проходящих через B.
Рассмотрим произвольную точку A маршрута a, возьмём на маршруте AB остановку C, отличную от A и B, и проведём через неё маршрут c, отличный от AB. Маршрут c не проходит через B, следовательно, на нём n остановок. Остановка A не лежит на c, поэтому, как показано выше, через A проходит n маршрутов (включая a). То же верно для каждой точки маршрута a.
Значит, через точки маршрута a проходит всего n(n – 1) маршрутов, отличных от a, и ещё сам маршрут a. А это – все маршруты города.
Решая уравнение n(n – 1) + 1 = 57, находим, что n = 8.
Ответ
8 остановок.
Коля и Витя играют в следующую игру на бесконечной клетчатой бумаге. Начиная с
Коли, они по очереди отмечают узлы клетчатой бумаги — точки пересечения
вертикальных и горизонтальных прямых. При этом каждый из них своим ходом
должен отметить такой узел, что после этого все отмеченные узлы лежали в
вершинах выпуклого многоугольника (начиная со второго хода Коли). Тот из
играющих, кто не сможет сделать очередного хода, считается проигравшим. Кто
выигрывает при правильной игре?
Решение
Ответ: Витя. После первого хода Коли Витя мысленно отмечает произвольный
узел
O, отличный от того, который отметил Коля. Затем он каждый раз
отмечает узел, симметричный относительно
O тому узлу, который отметил Коля.
Ясно, что при этом снова получается выпуклый многоугольник. После шести ходов
получается центрально симметричный шестиугольник. В дальнейшем можно отмечать
только узлы, лежащие в шести треугольниках, образованных сторонами
шестиугольника и продолжениями сторон. Поэтому у Коли есть только конечное
число возможных ходов.
|
|
|
Сложность: 4
Классы: 8,9,10,11
|
Найдите наименьшее натуральное $k$ такое, что в любом выпуклом $1001$-угольнике сумма длин любых $k$ диагоналей не меньше суммы длин остальных диагоналей.
Решение
Пусть $AB = 1$. Рассмотрим выпуклый $1001$-угольник, одна из вершин которого совпадает с $A$, а остальные $1000$ вершин лежат на расстоянии, меньшем $\varepsilon$ от $B$, где $\varepsilon$ достаточно мало. Обозначим через $k + \ell$ общее число диагоналей, равное $\frac{1001 \cdot 998}{2}=499499$. При $k\ge 498501$ сумма длин кратчайших $k$ диагоналей примерно равна $k-498501=998-\ell$, а сумма остальных диагоналей примерно равна $\ell$. Следовательно, $\ell\le 499$ и $k\ge 499000$.
Покажем теперь, что $k = 499000$ удовлетворяет условию. Раскрасим произвольные $\ell=499$ зеленым. Для каждой зеленой диагонали $AB$, кроме, возможно, последней, построим красные диагонали $AC$ и $CB$ так, чтобы ни одна зеленая диагональ не была перекрашена в красный цвет и ни одна диагональ не была покрашена красным дважды.
Пусть для $0 \le i \le 498$ зеленых диагоналей соответствующие красно-зеленые треугольники построены. Рассмотрим очередную зеленую диагональ $AB$. Пусть $D$ – множество всех диагоналей с концами $A$ и $B$, отличных от $AB$; тогда $|D|=2\cdot 997=1994$. Каждый красно-зеленый треугольник имеет не больше двух сторон в $D$. Значит подмножество $E$ непокрашенных диагоналей из $D$ содержит не меньше $1994-2i$ элемента.
При $i\le 497$ имеем $1994-2i\ge 1000$. Общее число вершин, отличных от $A$ и $B$, равно $999$. Следовательно найдутся две диагонали из $E$ с общим концом $C$ и мы можем покрасить красным диагонали $AC$ и $CB$.
Осталось рассмотреть случай $i = 498$. Предположим, что никакие две диагонали из $E$ не имеют общих концов, отличных от $A$ и $B$. Тогда найдутся две диагонали из $E$, которые пересекаются. Действительно, в противном случае одна (назовем ее $a$) из двух соседних с $A$ вершин отделена от $B$ диагоналями, выходящими из $A$, и одна (назовем ее $b$) из двух соседних с $B$ вершин отделена от $A$ диагоналями, выходящими из $B$ (при этом $a \neq b$). Тогда у нас есть не больше $997$ подходящих вершин и не меньше $998$ диагоналей из $E$ – противоречие.
Для завершения доказательства осталось воспользоваться неравенством треугольника.
Ответ
$k = 499000$.
|
|
|
Сложность: 4
Классы: 10,11
|
На бесконечной шахматной доске через каждые три клетки по
горизонтали и по вертикали стоит фишка. Можно ли обойти конем
оставшуюся часть доски, побывав при этом на каждом поле ровно один
раз?
Подсказка
Рассмотрите достаточно большой квадрат на бесконечной доске.
Незанятых черных клеток в этом квадрате гораздо меньше, чем белых.
Решение
Предположим, что фишки расставлены на черных полях (см.
картинку).
Рассмотрим достаточно большой квадрат (4N-3)*(4N-3)
(значение N уточним позже), в углах которого расставлены фишки,
а также квадрат
размером (4N+1)*(4N+1), полученный из квадрата (4N-3)*(4N-3)
расширением на 2 клетки в каждую сторону.
Число белых полей в квадрате (4N-3)*(4N-3) равно A(N) = ((4N-3)*(4N-3)-1)/2 =
8N
2-12N+4.
Если бы конь обошел все не занятые фишками поля, то
с каждого белого поля квадрата (4N-3)*(4N-3) он бы пошел на одно из
черных полей квадрата (4N+1)*(4N+1), не занятых фишками
(причем все эти черные поля должны быть различны).
Всего внутри этого квадрата N
2 полей заняты фишками,
поэтому число незанятых черных полей равно
B(N) = ((4N+1)*(4N+1)+1)/2-N
2 = 7N
2+4N+1.
Итак, если конь обошел оставшуюся часть доски, то B(N) должно
быть не меньше, чем A(N).
Однако при N>16
имеем:
A(N)-B(N) = N
2-16N+3 = N(N-16)+3 > 0.
Таким образом, мы получили противоречие, показывающее, что искомый
обход конем бесконечной доски невозможен.
Ответ
нельзя.
Страница:
<< 2 3 4 5 6 7 8 >> [Всего задач: 75]
Фильтр
