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

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

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



Задача 105148

Темы:   [ Связность и разложение на связные компоненты ]
[ Деревья ]
[ Подсчет двумя способами ]
Сложность: 4-
Классы: 8,9,10

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

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

Задача 111260

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

Клетчатая прямоугольная сетка m×n связана из верёвочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную верёвочку. Если не останется ни одного замкнутого верёвочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть?

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

Задача 30814

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

В некоторой стране каждые два города соединены либо авиалинией, либо железной дорогой. Докажите, что
  а) можно выбрать вид транспорта так, чтобы от каждого города можно было добраться до любого другого, пользуясь только этим видом транспорта;
  б) из некоторого города, выбрав один из видов транспорта, можно добраться до любого другого города не более чем с одной пересадкой (пользоваться можно только выбранным видом транспорта);
  в) каждый город обладает свойством из пункта б);
  г) можно выбрать вид транспорта так, чтобы пользуясь только им, можно было добраться из каждого города до любого другого не более чем с двумя пересадками.

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

Задача 65735

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

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

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

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

Задача 73723

Темы:   [ Связность и разложение на связные компоненты ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4
Классы: 8,9,10

Между некоторыми из 2n городов установлено воздушное сообщение, причём каждый город связан (беспосадочными рейсами) не менее чем с n другими.
  а) Докажите, что если отменить любые  n – 1  рейсов, то всё равно из любого города можно добраться в любой другой на самолётах (с пересадками).
  б) Укажите все случаи, когда связность нарушается при отмене n рейсов.

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

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



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

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