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

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

а) Электрическая схема имеет вид решетки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от каждого узла к любому другому. За какое наименьшее число измерений всегда можно в этом удостовериться?

б) Тот же вопрос для решётки 5×5 (всего 36 узлов).

   Решение

Задачи

Страница: << 18 19 20 21 22 23 24 >> [Всего задач: 136]      



Задача 98141

Темы:   [ Взвешивания ]
[ Метод спуска ]
[ Отношение порядка ]
[ Оценка + пример ]
Сложность: 4
Классы: 7,8,9

Автор: Анджанс А.

Имеется 100 серебряных монет, упорядоченных по весу, и 101 золотая монета, они также упорядочены по весу. Известно, что все монеты по весу различны. В нашем распоряжении – двухчашечные весы, позволяющие про каждые две монеты установить, какая тяжелее. Как за наименьшее число взвешиваний найти монету, занимающую среди всех монет 101-е место?

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

Задача 98596

Темы:   [ Теория алгоритмов (прочее) ]
[ Связность и разложение на связные компоненты ]
[ Внутренность и внешность. Лемма Жордана ]
[ Оценка + пример ]
Сложность: 4
Классы: 8,9,10

а) Электрическая схема имеет вид решетки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от каждого узла к любому другому. За какое наименьшее число измерений всегда можно в этом удостовериться?

б) Тот же вопрос для решётки 5×5 (всего 36 узлов).

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

Задача 109918

Темы:   [ Задачи с неравенствами. Разбор случаев ]
[ Теория алгоритмов (прочее) ]
[ Принцип Дирихле (прочее) ]
[ Оценка + пример ]
Сложность: 4
Классы: 8,9,10

а) В городе Мехико для ограничения транспортного потока для каждой частной автомашины устанавливаются два дня недели, в которые она не может выезжать на улицы города. Семье требуется каждый день иметь в распоряжении не менее десяти машин. Каким наименьшим количеством машин может обойтись семья, если её члены могут сами выбирать запрещенные дни для своих автомобилей?

б) В Мехико для каждой частной автомашины устанавливается один день в неделю, в который она не может выезжать на улицы города. Состоятельная семья из десяти человек подкупила полицию, и для каждой машины они называют два дня, один из которых полиция выбирает в качестве невыездного дня. Какое наименьшее количество машин нужно купить семье, чтобы каждый день каждый член семьи мог самостоятельно ездить, если утверждение невыездных дней для автомобилей идёт последовательно?

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

Задача 65687

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

С левого берега реки на правый с помощью одной лодки переправились N туземцев, каждый раз плавая направо вдвоем, а обратно – в одиночку. Изначально каждый знал по одному анекдоту, каждый – свой. На берегах они анекдотов не рассказывали, но в лодке каждый рассказывал попутчику все известные ему на данный момент анекдоты. Для каждого натурального k найдите наименьшее возможное значение N, при котором могло случиться так, что в конце каждый туземец знал, кроме своего, еще не менее чем k анекдотов.

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

Задача 65835

Темы:   [ Инварианты ]
[ Принцип крайнего (прочее) ]
[ Теория алгоритмов (прочее) ]
[ Оценка + пример ]
Сложность: 4+
Классы: 10,11

На доске можно либо написать две единицы, либо стереть любые два уже написанных одинаковых числа n и написать вместо них числа  n + 1  и  n – 1.  Какое минимальное количество таких операций требуется, чтобы получить число 2005? (Сначала доска была чистой.)

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

Страница: << 18 19 20 21 22 23 24 >> [Всего задач: 136]      



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

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