RUS  ENG
Полная версия
ВИДЕОТЕКА

Летняя школа «Современная математика» имени Виталия Арнольда, 2023
19 июля 2023 г. 15:30, Московская область, г. Дубна, дом отдыха «Ратмино»


Поиск фальшивых монет на (не)точных весах, и при чем здесь линейная алгебра? Семинар 1

Г. А. Кабатянский


https://youtu.be/cO1So7YU-9I?si=_iidu1BrD8L5HtPz

Аннотация: Пусть имеются $m$ монет, из которых не более $t$ фальшивых, и точные весы, на которые можно положить любое количество монет. Мы будем рассматривать два крайних варианта постановки задачи, различающиеся тем, какая информация известна о весах монет.

В первой, традиционной постановке задачи предполагается, что все правильные монеты имеют вес $\alpha$, все фальшивые - вес $\beta$, и величины $\alpha,\beta$ известны заранее.

Во второй постановке задачи известно лишь, что все правильные монеты имеют один и тот же вес, но даже он неизвестен (подсказка - тут-то и нужна линейная алгебра!).

Мы рассматриваем только так называемый <em>неадаптивный поиск</em>, то есть когда все взвешивания производятся одновременно. И нас будет интересовать асимптотика минимального числа необходимых взвешиваний при $t-const$ и $m\rightarrow{\infty}$.

А что если весы иногда ошибаются, да не просто, а злонамеренно? Простейший случай этой задачи, когда все веса известны и фальшивая монета всего одна, да и весы могут ошибиться только один раз, известна как задача поиска со лжецом, или задача Улама-Реньи. Придумал задачу известный венгерский математик Альфред Реньи, но переоткрыл и сделал популярной другой известный математик и физик Станислав Улам, опубликовав в книге «Приключения математика» (Adventures of a Mathematician) в 1976 году. Одним из таких «приключений» и была эта задача в случае, когда имеется миллион монет. Как вы думаете сколько вопросов-взвешиваний нужно?

Эти задачи, несмотря на свой олимпиадный привкус, являются ключевыми для комбинаторной теории поиска и имеют серьезные приложения (подумайте про тесты на ковид!).

Website: https://mccme.ru/dubna/2023/courses/kabatyansky.html
Цикл лекций


© МИАН, 2024