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

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

Страница: << 121 122 123 124 125 126 127 >> [Всего задач: 737]      



Задача 65175

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

Император пригласил на праздник 2015 волшебников, некоторые из которых добрые, а остальные злые. Добрый волшебник всегда говорит правду, а злой может говорить что угодно. При этом волшебники знают, кто добрый и кто злой, а император нет. На празднике император задаёт каждому волшебнику (в каком хочет порядке) по вопросу, на которые можно ответить "да" или "нет". Опросив всех волшебников, император изгоняет одного. Изгнанный волшебник выходит в заколдованную дверь, и император узнаёт, добрый он был или злой. Затем император вновь задает каждому из оставшихся волшебников по вопросу, вновь одного изгоняет, и так далее, пока император не решит остановиться (он может это сделать после любого вопроса). Докажите, что император может изгнать всех злых волшебников, удалив при этом не более одного доброго.

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

Задача 65735

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

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

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

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

Задача 66593

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

Автор: Шень А.Х.

Есть бесконечная в одну сторону клетчатая полоска, клетки которой пронумерованы натуральными числами, и мешок с десятью камнями. В клетках полоски камней изначально нет. Можно делать следующее:

– перемещать камень из мешка в первую клетку полоски или обратно;

– если в клетке с номером $i$ лежит камень, то можно переложить камень из мешка в клетку с номером $i + 1$ или обратно.

Можно ли, действуя по этим правилам, положить камень в клетку с номером 1000?

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

Задача 66757

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

Петя и Вася играют в игру. Для каждых пяти различных переменных из набора $x_{1}, ..., x_{10}$ имеется единственная карточка, на которой записано их произведение. Петя и Вася по очереди берут по карточке, начинает Петя. По правилам игры, когда все карточки разобраны, Вася присваивает переменным значения как хочет, но так, что  $0 \leqslant x_{1} \leqslant ... \leqslant x_{10}$.  Может ли Вася гарантированно добиться того, чтобы сумма произведений на его карточках была больше, чем у Пети?

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

Задача 66829

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

Есть 100 внешне неразличимых монет трёх типов: золотые, серебряные и медные (каждый тип встречается хотя бы раз). Известно, что золотые весят по 3 г, серебряные – по 2 г, медные – по 1 г.
Как на чашечных весах без гирек определить тип у всех монет не более чем за 101 взвешивание?

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

Страница: << 121 122 123 124 125 126 127 >> [Всего задач: 737]      



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

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