Question

Петя выложил на столе 2019 карточек, на каждой из которых на обратной (невидимой) стороне написал одно из целых чисел от 1 до 2019 (числа не повторяются). Вася за один вопрос может показать на любые три карточки и узнать набор чисел, написанных на них (но неизвестно на какой карточке какое будет число). За какое наименьшее число вопросов Вася может узнать на какой карточке какое число записано?

Answer 1

Карточки лежат по порядку примерно 38

Answer 2

Для решения этой задачи мы можем использовать стратегию, известную как метод тестирования комбинаций (англ. combinatorial testing). Этот метод основан на принципе деления оставшихся возможностей на равные группы и проверки каждой группы, чтобы исключить некоторые комбинации.

В данном случае мы можем разделить 2019 карточек на группы по 3 карточки. Всего возможно разделить 2019 карточек на [(2019/3)] = 673 группы по 3 карточки каждая, где [] обозначает наибольшее целое число, не превышающее число в скобках.

Вася должен задать вопрос для каждой группы карточек. Это означает, что Васе понадобится 673 вопроса.

Предположим, что на первом вопросе Вася выбирает группу, которая содержит карты A, B и C. Возможны следующие варианты:

1. A содержит число 1.
2. B содержит число 1.
3. C содержит число 1.
4. Ни одна из карт не содержит число 1.

Если Вася получает ответ "Да" на свой вопрос, это означает, что одна из карт содержит число 1. Если Вася получает ответ "Нет", это означает, что ни одна из карт не содержит число 1.

В любом случае, Вася может исключить некоторые комбинации. Если, например, ответ "Да" и карта A содержит число 1, то Вася знает, что на карте B и C не может быть число 1. Таким образом, он может узнать, что на карте A находится число 1.

Продолжая задавать вопросы для каждой группы, Вася сможет узнать числа, записанные на каждой карточке, используя общее число вопросов равное 673.

Таким образом, наименьшее число вопросов, которое Васе нужно задать, чтобы узнать числа на каждой карточке, равно 673.