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

Проект МЦНМО
при участии
школы 57
Задача 66096
Темы:    [ Теория алгоритмов (прочее) ]
[ Сочетания и размещения ]
[ Двоичная система счисления ]
[ Троичная система счисления ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Детектив Ниро Вульф расследует преступление. В деле замешаны 80 человек, среди которых один – преступник, еще один – свидетель преступления (но неизвестно, кто это). Каждый день детектив может пригласить к себе одного или нескольких из этих 80 человек, и если среди приглашенных есть свидетель, но нет преступника, то свидетель сообщит, кто преступник. Может ли детектив заведомо раскрыть дело за 12 дней?


Решение

  Первый способ. Занумеруем 80 подозреваемых четырёхзначными троичными числами abcd от 0001 до 2222 (таких чисел ровно  34 – 1 = 80).
В k-й день  (k = 1, 2, ..., 12)  Ниро Вульф приглашает к себе тех подозреваемых, номера которых удовлетворяет k-му из равенств  a = 0,  a = 1,  a = 2,
b = 0,  b = 1,  b = 2,  c = 0,  c = 1,  c = 2,  d = 0,  d = 1,  d = 2.  Тогда в один из этих дней он пригласит к себе свидетеля, но при этом не пригласит преступника, так как их номера отличаются хотя бы в одной цифре.

  Второй способ. Разобьём подозреваемых на 16 групп по 5 человек. Занумеруем группы четырёхзначными двоичными числами abcd от 0000 до 1111, а её членов занумеруем числами от 1 до 5.
  В k-й день  (k = 1, 2, ..., 8)  Ниро Вульф приглашает к себе подозреваемых из групп, номера которых удовлетворяет k-му из равенств:  a = 0,  a = 1,
b = 0,  b = 1,  c = 0,  c = 1,  d = 0,  d = 1.  Если преступник и свидетель попали в разные группы, то преступление будет раскрыто в один из этих дней.
  Предположим, что свидетель находится в одной группе с преступником. Обозначим через m и n номера свидетеля и преступника в этой группе соответственно. На 9-й день Ниро Вульф приглашает из каждой группы подозреваемых с номерами 1 и 2, на 10-й день – подозреваемых с номерами 3 и 4, на 11-й день – подозреваемых с номерами 1, 3 и 5, на 12-й день – подозреваемых с номерами 2, 4 и 5. Тогда найдётся один из этих дней, в который из каждой группы были приглашены подозреваемые с номером m, но при этом не были приглашены подозреваемые с номером n. Значит, в этот день преступление будет раскрыто.

  Третий способ. Покажем, что Ниро Вульф сможет найти преступника даже за 9 дней. Для этого сопоставим каждому подозреваемому свой номер – девятизначное двоичное число, четыре цифры которого – единицы, а пять – нули (это возможно, так как всего таких чисел   ).
  В k-й день  (k = 1, 2, ..., 9)  Ниро Вульф приглашает к себе тех подозреваемых, k-я цифра номера которых равна 1. Поскольку все номера содержат ровно по 4 единицы, найдётся такое число m от 1 до 9, что на m-м месте у свидетеля стоит единица, а у преступника – ноль. Значит, в m-й день свидетель будет приглашен к Ниро Вульфу без преступника, и преступление будет раскрыто.


Ответ

Может.

Замечания

  Пользуясь методом из третьего способа, можно показать, что за 12 дней детектив сможет раскрыть дело, если в нем замешаны не более    подозреваемых.
  Более того, эта оценка точная, что вытекает из следующего факта. Пусть A – множество всех подмножеств некоторого n-элементного множества. Рассмотрим такое подмножество B множества A, что никакие два элемента из B не вложены друг в друга (такое подмножество B называется антицепью). Теорема Шпернера утверждает, что максимальное число элементов, которое может содержать B, равно    Для чётного n эта теорема фактически доказана в решении задачи 78166.
  Из этой теоремы следует, что максимальное число подозреваемых, среди которых заведомо можно выявить преступника за n дней, равно    Действительно, сопоставим каждому из подозреваемых код из нулей и единиц длины n, в котором на k-м месте стоит 1, если в k-й день он был приглашен к Ниро Вульфу, и 0 в противном случае. Такой код однозначно определяет подмножество дней, в которые подозреваемый побывал у детектива. Чтобы дело было раскрыто, в какой-то день свидетель должен побывать у Ниро Вульфа без преступника. Это произойдёт, если существует такое число k  (k = 1, 2, ..., n),  что на k-м месте в коде свидетеля стоит 1, а в коде преступника стоит 0. Максимальное число кодов, при котором это можно гарантировать, в соответствии с теоремой Шпернера как раз равно  
  Из вышеизложенного также следует, что минимальное число дней, за которое можно заведомо выявить преступника среди 80 подозреваемых, равно 9 (так как за 8 дней преступника можно найти лишь среди не более    человек).

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 80
Год 2017
класс
Класс 11
задача
Номер 3

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

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