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

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

Страница: << 29 30 31 32 33 34 35 >> [Всего задач: 200]      



Задача 98278

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

В компанию из n человек пришёл журналист. Ему известно, что в этой компании есть человек Z, который знает всех остальных членов компании, но его не знает никто. Журналист может к каждому члену компании обратиться с вопросом: "Знаете ли вы такого-то?"
  а) Может ли журналист установить, кто из компании есть Z, задав менее n вопросов?
  б) Найдите наименьшее количество вопросов, достаточное для того, чтобы наверняка найти Z, и докажите, что меньшим числом вопросов обойтись нельзя.
(Все отвечают на вопросы правдиво. Одному человеку можно задавать несколько вопросов.)

Решение

  а) Вот пример стратегии, приводящей к цели. Сначала журналист выбирает произвольных членов компании А и B. Человеку А он задаёт вопрос: "Знаете ли вы B?" Из ответа "да" следует, что B не Z. Из ответа "нет" следует, что А не Z. Итак, один вопрос задан и один человек отброшен – в дальнейшем не нужно задавать вопросы ни ему, ни о нём. Продолжая в том же духе, мы отбросим  n – 1  человека, задав  n – 1  вопрос. Остаётся один человек. Он и есть Z.

  б) Докажем, что необходимо задать не менее  n – 1  вопроса.
  Пусть на некотором шаге опроса человека А спросили, знает ли он B. В случае ответа "да" будем считать B отмеченным, в случае ответа "нет" будем считать А отмеченным. Про отмеченного мы уже знаем, что он не Z, так как либо он кого-то не знает, либо его кто-то знает. После того как заданы все вопросы (их не больше, чем  n – 2),  неотмеченных людей будет не меньше двух.
  Пусть X – один из тех, кто остался неотмеченным. В результате заданных вопросов мы уже обладаем некоторыми сведениями о том, кто кого знает. Изменим систему знакомств так, чтобы все имеющиеся сведения сохранились и при этом X стал Z. Для этого сделаем так, что X знает всех, а в остальных случаях (кроме тех, которые выяснились в результате заданных вопросов) установим, что никто никого не знает.
  Итак, для любого из неотмеченных (X был взят среди них произвольно) можно изменить систему знакомств так, что именно он будет Z. А это и означает, что заданных вопросов недостаточно для выяснения того, кто есть Z.

Ответ

а) Может.  б)  n – 1.

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

Задача 109591

Темы:   [ Математическая логика (прочее) ]
[ Таблицы и турниры (прочее) ]
[ Разбиения на пары и группы; биекции ]
[ Принцип Дирихле (прочее) ]
Сложность: 4-
Классы: 7,8,9

На совместной конференции партий лжецов и правдолюбов в президиум было избрано 32 человека, которых рассадили в четыре ряда по 8 человек. В перерыве каждый член президиума заявил, что среди его соседей есть представители обеих партий. Известно, что лжецы всегда лгут, а правдолюбы всегда говорят правду. При каком наименьшем числе лжецов в президиуме возможна описанная ситуация? (Два члена президиума являются соседями, если один из них сидит слева, справа, спереди или сзади от другого.)

Решение

Разобьём все места в президиуме на восемь групп так, как показано на рисунке. Если лжецов меньше восьми, то в какой-то из этих групп сидят одни правдолюбы, чего быть не может.


На том же рисунке также показано, как можно рассадить восемь лжецов.

Ответ

При восьми лжецах.

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

Задача 109656

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

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

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

Решение

Ясно, что мудрец, стоящий в колонне последним, может спастись только случайно, ведь его колпака не видит никто из мудрецов. Но он может спасти всех остальных, сообщив им чётность числа белых колпаков, надетых на них (по договоренности он скажет "белый", если это число нечётно, и "чёрный" в противном случае). Теперь мудрецы должны вычислять и называть цвета своих колпаков по порядку от предпоследнего к первому: сначала предпоследний, видя колпаки впереди стоящих и зная чётность числа белых колпаков (среди колпаков впереди стоящих и своего), легко определит цвет своего колпака и назовёт его; затем мудрец, стоящий перед ним, зная цвета всех тех же колпаков, кроме своего (передние он видит, а про задний только что услышал), по чётности может определить цвет своего колпака и назвать его. Остается продолжать описанную процедуру до тех пор, пока первый мудрец не определит цвет своего колпака.

Ответ

Всем, кроме одного.

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

Задача 65175

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

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

Решение

См. решение задачи 65168.

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

Задача 89956

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

Попугаи. Собрались три попугая — Гоша, Кеша и Рома. Один из них всегда говорит правду, другой всегда лжет, а третий — хитрец, он иногда говорит правду, иногда лжет. На вопрос: «Кто Кеша?» — попугаи ответили так: Гоша: — Кеша лжец. Кеша: — Я хитрец! Рома: — Он абсолютно честный попугай. Кто же из попугаев честный, кто лжец, а кто хитрец?

Подсказка

Заметьте, Рома не может быть честным.

Решение

Рома не может быть честным, т.к. тогда и Кеша честный, что невозможно. Значит Рома либо лжец, либо хитрец. Пусть Рома лжец. Тогда Кеша хитрец (он не может быть лжецом, ибо лжец Рома, и не может быть честным, поскольку тогда его высказывание ложно). Но тогда Гоша должен быть честным, но этому противоречит его высказывание. Отсюда следует, что Рома хитрец. Тогда Кеша, судя по его высказыванию, лжец, а для Гоши остается только возможность быть честным. Его высказывание действительно истинно. А из Роминого высказывания следует, что в данном случае он (Рома) солгал. Итак, честный — Гоша, хитрец — Рома, лжец — Кеша.
Прислать комментарий


Страница: << 29 30 31 32 33 34 35 >> [Всего задач: 200]      



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

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