Чисто английское убийство

[peregoudov]

На следующее утро после загадочного убийства на борту океанского лайнера "Левиафан" капитан позвал в свою каюту комиссара Гоша и Эраста Петровича Фандорина.

— Господа, как продвигается расследование? — сразу перешёл к делу капитан.

— Эмм.. Чертовски запутанное дело, — промямлил комиссар Гош. — И ещё эта дурацкая записка...

— П-позвольте мне изложить факты, — Эраст Петрович достал из кармана нефритовые чётки. — На "Левиафане" сто пассажиров первого класса, и один из этих пассажиров - убийца. Кто именно убийца, мы пока не знаем. Это р-раз.
Среди пассажиров есть свидетель, который знает, кто убийца. Но кто именно из пассажиров свидетель, мы тоже не знаем. Это д-два.
Каждый вечер капитан приглашает некоторых пассажиров первого класса на ужин в кают-компанию. Свидетель оставил записку, из которой мы знаем, что если за ужином в кают-компании будет присутствовать свидетель, и при этом будет отсутствовать убийца, то свидетель признается и расскажет, кто убийца. Это т-три.
Необходимо найти убийцу, пока "Левиафан" находится в открытом море. Как только корабль пристанет к берегу, преступник сбежит.

— У меня есть идея, — прервал Фандорина комиссар Гош. — Вы, капитан, каждый вечер будете приглашать одного из пассажиров в кают-компанию, и за сто дней мы найдём убийцу.

— "Левиафан" не может оставаться в океане сто дней, — возразил капитан.

— Сто дней не п-потребуется, —загадочно улыбнулся Фандорин.

Сколько дней понадобится Эрасту Петровичу, чтобы поймать убийцу?

И бонусом: каково максимальное число пассажиров первого класса, среди которых Фандорин сможет найти убийцу за столько же дней?

Пусть у Фандорина есть N дней. Сколько может быть пассажиров первого класса, чтобы он мог за это время найти убийцу?

[Ian]

За 9 вечеров можно найти среди 126 пассажиров

[peregoudov]

Оптимальность доказать можете?

[Ian]

То есть у Вас такой же ответ? Ну тогда темнить и ждать кто еще как решит смысла нет. Всю систему m вечеров с пассажирами из множества n человек я представил как матрицу с n строками и m столбцами . В строке [math]a_i, соответствующей i-му пассажиру, стоит 1ца, когда он приглашен на очередной ужин, и 0, если не приглашен.Если по итогам серии m вечеров убийцу определить нельзя. то среди строк существует строка убийцы [math]a_k и строка свидетеля [math]a_s, такая, что убийца был на всех вечерах, на которых был свидетель, что означает отношение порядка между строками [math]a_k\geq a_s(в смысле каждый элемент строки [math]a_k не меньше элемента строки [math]a_s c тем же номером).Значит план приглашений работает тогда и только тогда, когда нет пары строк, между которыми возможно такое отношение нестрогого порядка. Представим строки как точки m-мерного куба, а на всех ребрах куба поставим стрелки в сторону возрастания координат. Надо найти в нем максимальное множество вершин,что ни из какой ни в какую не существует пути по стрелкам. Это задача кажется решенная, максимальное множество удовлетворяет условию: сумма координат постоянна и равна [math][ \frac m2] (ну или можно +1, если m нечетное, тоже годится). В нем при m=9 [math]C^4_9=126 точек (пассажиров), а при m=8 меньше 100

[zykov]

А конструктивное решение "кого приглашать" тоже есть?

[Ian]

Конечно конструктивно. В строчках перечисляем все различные сочетания 4х единиц среди 9 знаков, остальные нули. строчек можно написать более 100. Приглашаем 1й столбец в 1-й раз, 2-й столбец во 2-й. Если [math]a_k-строка убийцы, а [math]a_s строка свидетеля,k и s мы не знаем, то из-за равенства числа единиц в них найдется елиница строки [math]a_s в таком столбце, в котором нет единицы строки [math]a_k, вот тогда-то он и скажет

[zykov]

Да, сначала не совсем понял.
Каждый пассажир приглашается ровно на 4 раза из 9, так что просто генерируем все выборки "4 из 9".
При этом очевидно для каждой пары пассажиров найдётся вечер, когда был первый и не было второго, а так же другой вечер, когда не было первого, но был второй.

[peregoudov]

Автор задачи тут поделился ссылкой
https://en.wikipedia.org/wiki/Sperner%27s_theorem

Так что оптимальность тоже доказана.