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

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

Автор: Кноп К.А.

В стране 64 города, некоторые пары из них соединены дорогой, но нам неизвестно, какие именно. Можно выбрать любую пару городов и получить ответ на вопрос “есть ли дорога между ними?”. Нужно узнать, можно ли в этой стране добраться от любого города до любого другого, двигаясь по дорогам. Докажите, что не существует алгоритма, позволяющего сделать это менее чем за 2016 вопросов.

   Решение

Задачи

Страница: << 58 59 60 61 62 63 64 >> [Всего задач: 1006]      



Задача 65731

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

а) Есть  2n + 1  батарейка  (n > 2).  Известно, что хороших среди них на одну больше, чем плохих, но какие именно батарейки хорошие, а какие плохие, неизвестно. В фонарик вставляются две батарейки, при этом он светит, только если обе они хорошие. За какое наименьшее число таких попыток можно гарантированно добиться, чтобы фонарик светил?

б) Та же задача, но батареек 2n  (n > 2),  причём хороших и плохих поровну.

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

Задача 65735

Темы:   [ Связность и разложение на связные компоненты ]
[ Теория алгоритмов (прочее) ]
Сложность: 4
Классы: 9,10,11

Автор: Кноп К.А.

В стране 64 города, некоторые пары из них соединены дорогой, но нам неизвестно, какие именно. Можно выбрать любую пару городов и получить ответ на вопрос “есть ли дорога между ними?”. Нужно узнать, можно ли в этой стране добраться от любого города до любого другого, двигаясь по дорогам. Докажите, что не существует алгоритма, позволяющего сделать это менее чем за 2016 вопросов.

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

Задача 65762

Темы:   [ Теория графов (прочее) ]
[ Делимость чисел. Общие свойства ]
[ Четность и нечетность ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 4
Классы: 9,10,11

Автор: Петров Ф.

В стране есть  n > 1  городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между каждыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города X подсчитал количество таких нумераций всех городов числами от 1 до n, что на любом авиамаршруте, начинающемся в X, номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчётов делятся на 2016. Докажите, что и у оставшегося мэра результат также делится на 2016.

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

Задача 67252

Темы:   [ Степень вершины ]
[ Четность и нечетность ]
[ Наглядная геометрия в пространстве ]
Сложность: 4
Классы: 10,11

В пространстве имеется 43 точки: 3 желтых и 40 красных. Никакие четыре из них не лежат в одной плоскости. Может ли количество треугольников с красными вершинами, зацепленных с треугольником с желтыми вершинами, быть равно $2023$?

Жёлтый треугольник зацеплен с красным, если контур красного пересекает часть плоскости, ограниченную жёлтым, ровно в одной точке. Треугольники, отличающиеся перестановкой вершин, считаются одинаковыми.
Прислать комментарий     Решение


Задача 73683

Темы:   [ Треугольник Паскаля и бином Ньютона ]
[ Рекуррентные соотношения (прочее) ]
[ Индукция (прочее) ]
Сложность: 4
Классы: 10,11

Последовательность  x0, x1, x2, ...  определена следующими условиями:  x0 = 1,  x1 = λ,  для любого  n > 1  выполнено равенство

(α + β)nxn = αnxnx0 + αn–1βxn–1x1 + αn–2β2xn–2x2 + ... + βnx0xn.
Здесь α, β, λ – заданные положительные числа. Найдите xn и выясните, при каком n величина xn наибольшая.

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

Страница: << 58 59 60 61 62 63 64 >> [Всего задач: 1006]      



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

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