ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 75]      



Задача 35737

Темы:   [ Комбинаторная геометрия (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3+
Классы: 7,8,9,10,11

Повесьте картину на веревочке на два гвоздя так, чтобы при вытаскивании любого из гвоздей картина падала.

Подсказка

Вокруг каждого из гвоздей должно быть сделано равное число оборотов по и против часовой стрелки.

Решение

Вот один из возможных вариантов.


Прислать комментарий

Задача 76535

Темы:   [ Комбинаторная геометрия (прочее) ]
[ Классическая комбинаторика (прочее) ]
[ Проективная плоскость с конечным числом точек ]
Сложность: 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 остановок.

Прислать комментарий

Задача 79364

Темы:   [ Комбинаторная геометрия (прочее) ]
[ Симметричная стратегия ]
Сложность: 4-
Классы: 8

Коля и Витя играют в следующую игру на бесконечной клетчатой бумаге. Начиная с Коли, они по очереди отмечают узлы клетчатой бумаги — точки пересечения вертикальных и горизонтальных прямых. При этом каждый из них своим ходом должен отметить такой узел, что после этого все отмеченные узлы лежали в вершинах выпуклого многоугольника (начиная со второго хода Коли). Тот из играющих, кто не сможет сделать очередного хода, считается проигравшим. Кто выигрывает при правильной игре?

Решение

Ответ: Витя. После первого хода Коли Витя мысленно отмечает произвольный узел O, отличный от того, который отметил Коля. Затем он каждый раз отмечает узел, симметричный относительно O тому узлу, который отметил Коля. Ясно, что при этом снова получается выпуклый многоугольник. После шести ходов получается центрально симметричный шестиугольник. В дальнейшем можно отмечать только узлы, лежащие в шести треугольниках, образованных сторонами шестиугольника и продолжениями сторон. Поэтому у Коли есть только конечное число возможных ходов.
Прислать комментарий


Задача 66800

Тема:   [ Комбинаторная геометрия (прочее) ]
Сложность: 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$.
Прислать комментарий


Задача 35656

Темы:   [ Комбинаторная геометрия (прочее) ]
[ Разбиения на пары и группы; биекции ]
Сложность: 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 = 8N2-12N+4. Если бы конь обошел все не занятые фишками поля, то с каждого белого поля квадрата (4N-3)*(4N-3) он бы пошел на одно из черных полей квадрата (4N+1)*(4N+1), не занятых фишками (причем все эти черные поля должны быть различны). Всего внутри этого квадрата N2 полей заняты фишками, поэтому число незанятых черных полей равно B(N) = ((4N+1)*(4N+1)+1)/2-N2 = 7N2+4N+1. Итак, если конь обошел оставшуюся часть доски, то B(N) должно быть не меньше, чем A(N). Однако при N>16 имеем: A(N)-B(N) = N2-16N+3 = N(N-16)+3 > 0. Таким образом, мы получили противоречие, показывающее, что искомый обход конем бесконечной доски невозможен.

Ответ

нельзя.
Прислать комментарий


Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 75]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .