Аннотация:
Пусть имеются $m$ монет, из которых не более $t$ фальшивых, и точные весы, на которые можно положить любое количество монет. Мы будем рассматривать два крайних варианта постановки задачи, различающиеся тем, какая информация известна о весах монет.
В первой, традиционной постановке задачи предполагается, что все правильные монеты имеют вес $\alpha$, все фальшивые - вес $\beta$, и величины $\alpha,\beta$ известны заранее.
Во второй постановке задачи известно лишь, что все правильные монеты имеют один и тот же вес, но даже он неизвестен (подсказка - тут-то и нужна линейная алгебра!).
Мы рассматриваем только так называемый <em>неадаптивный поиск</em>, то есть когда все взвешивания производятся одновременно.
И нас будет интересовать асимптотика минимального числа необходимых взвешиваний при $t-const$ и $m\rightarrow{\infty}$.
А что если весы иногда ошибаются, да не просто, а злонамеренно? Простейший случай этой задачи, когда все веса известны и фальшивая монета всего одна, да и весы могут ошибиться только один раз, известна как задача поиска со лжецом, или задача Улама-Реньи. Придумал задачу известный венгерский математик Альфред Реньи, но переоткрыл и сделал популярной другой известный математик и физик Станислав Улам, опубликовав в книге «Приключения математика» (Adventures of a Mathematician) в 1976 году. Одним из таких «приключений» и была эта задача в случае, когда имеется миллион монет. Как вы думаете сколько вопросов-взвешиваний нужно?
Эти задачи, несмотря на свой олимпиадный привкус, являются ключевыми для комбинаторной теории поиска и имеют серьезные приложения (подумайте про тесты на ковид!).
Обратная связь: