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

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

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



Задача 66904

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

Автор: Ивлев Ф.

В отель ночью приехали $100$ туристов. Они знают, что в отеле есть одноместные номера $1$, $2, \ldots, n$, из которых $k$ на ремонте (но неизвестно какие), а остальные свободны. Туристы могут заранее договориться о своих действиях, после чего по очереди уходят заселяться: каждый проверяет номера в любом порядке, находит первый свободный номер не на ремонте и остаётся там ночевать. Но туристы не хотят беспокоить друг друга: нельзя проверять номер, куда уже кто-то заселился. Для каждого $k$ укажите наименьшее $n$, при котором туристы гарантированно смогут заселиться, не потревожив друг друга.
Прислать комментарий     Решение


Задача 64616

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

Одиннадцати мудрецам завязывают глаза и надевают каждому на голову колпак одного из 1000 цветов. После этого им глаза развязывают, и каждый видит все колпаки, кроме своего. Затем одновременно каждый показывает остальным одну из двух карточек – белую или чёрную. После этого все должны одновременно назвать цвет своих колпаков. Удастся ли это? Мудрецы могут заранее договориться о своих действиях (до того, как им завязали глаза); мудрецам известно, каких 1000 цветов могут быть колпаки.

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

Задача 64784

Темы:   [ Процессы и операции ]
[ Кооперативные алгоритмы ]
[ Доказательство от противного ]
[ Принцип Дирихле (прочее) ]
Сложность: 5-
Классы: 10,11

Двое игроков играют в карточную игру. У них есть колода из n попарно различных карт. Про любые две карты из колоды известно, какая из них бьёт другую (при этом, если A бьёт B, а B бьёт C, то может оказаться, что C бьёт A). Колода распределена между игроками произвольным образом. На каждом ходу игроки открывают по верхней карте из своих колод, и тот, чья карта бьёт карту другого игрока, берёт обе карты и кладёт их в самый низ своей колоды в произвольном порядке по своему усмотрению. Докажите, что при любой исходной раздаче игроки могут, зная расположение карт, договориться и действовать так, чтобы один из игроков остался без карт.

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

Задача 111853

Темы:   [ Наименьшее или наибольшее расстояние (длина) ]
[ Центральный угол. Длина дуги и длина окружности ]
[ Кооперативные алгоритмы ]
Сложность: 4-
Классы: 7,8,9

Фокусник Арутюн и его помощник Амаяк собираются показать следующий фокус. На доске нарисована окружность. Зрители отмечают на ней 2007 различных точек, затем помощник фокусника стирает одну из них. После этого фокусник впервые входит в комнату, смотрит на рисунок и отмечает полуокружность, на которой лежала стертая точка. Как фокуснику договориться с помощником, чтобы фокус гарантированно удался?
Прислать комментарий     Решение


Задача 109656

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

Автор: Фольклор

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

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

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



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

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