патнемовские задачи
Три дня назад в США прошла Патнемовская олимпиада - это знаменитая математическая олимпиада для студентов. В отличие от "обычных" математических олимпиад, ее задания и решения опираются на высшую математику, которую учат на первых курсах бакалавриата. Сложность ее заданий примерно соответствует IMO (международной математической олимпиаде).
Внизу прилагаю условия задач, может, какие-то вам понравятся и захочется решить.
Меня очень заинтересовала задача B4. Вот пересказ условия чуть более простыми словами. Для данного n пронумеруем n клеток от 1 до n, слева направо, и встанем в клетку номер 1. Теперь много раз подряд будем разыгрывать случайное число от 1 до n, равновероятным образом; если выпадет ровно то число, где мы стоим, то остаемся на месте, если больше нашего, переходим на 1 клетку вправо, если меньше - на 1 клетку влево. Делаем ровно n таких розыгрышей. В итоге в среднем мы окажемся на какой-то клетке E(n) (матожидание номера клетки, куда придем после n розыгрышей). Чему равно E(n)/n в пределе n к бесконечности?
Со вчера до сегодня мое отношение к этой задаче прошло через четыре стадии:
1. (прочитал условие, чуть подумал) Если ответ не 1/2, то мы живем в несправедливом мире.
2. (подумал еще немного) Если ответ 1/2, то мы живем в несправедливом мире. Он должен быть другим, но каким, непонятно. Кстати, я из первого пункта - идиот.
3. (набросал на коленке за три минуты симуляцию, запустил) Есть подозрение, чему равен ответ, но понятия не имею, как доказать.
4. (подумал в кровати перед сном, уснул, подскочил утром, собираю и развожу детей в школы-садики, в фоновом режиме продолжаю думать) Секунду-секунду, оно что, решается в уме??? Да, оно решается в уме, вот ответ (и он не тот, который подозревал в пункте 3).
Все-таки удовольствие от завершенной математической мысли совершенно особое и не сравнится ни с чем другим, вообще ни с чем, ни с каким другим наслаждением, включая то, о чем вы сейчас подумали.
Задачи патнемовской олимпиады-2024:
Внизу прилагаю условия задач, может, какие-то вам понравятся и захочется решить.
Меня очень заинтересовала задача B4. Вот пересказ условия чуть более простыми словами. Для данного n пронумеруем n клеток от 1 до n, слева направо, и встанем в клетку номер 1. Теперь много раз подряд будем разыгрывать случайное число от 1 до n, равновероятным образом; если выпадет ровно то число, где мы стоим, то остаемся на месте, если больше нашего, переходим на 1 клетку вправо, если меньше - на 1 клетку влево. Делаем ровно n таких розыгрышей. В итоге в среднем мы окажемся на какой-то клетке E(n) (матожидание номера клетки, куда придем после n розыгрышей). Чему равно E(n)/n в пределе n к бесконечности?
Со вчера до сегодня мое отношение к этой задаче прошло через четыре стадии:
1. (прочитал условие, чуть подумал) Если ответ не 1/2, то мы живем в несправедливом мире.
2. (подумал еще немного) Если ответ 1/2, то мы живем в несправедливом мире. Он должен быть другим, но каким, непонятно. Кстати, я из первого пункта - идиот.
3. (набросал на коленке за три минуты симуляцию, запустил) Есть подозрение, чему равен ответ, но понятия не имею, как доказать.
4. (подумал в кровати перед сном, уснул, подскочил утром, собираю и развожу детей в школы-садики, в фоновом режиме продолжаю думать) Секунду-секунду, оно что, решается в уме??? Да, оно решается в уме, вот ответ (и он не тот, который подозревал в пункте 3).
Все-таки удовольствие от завершенной математической мысли совершенно особое и не сравнится ни с чем другим, вообще ни с чем, ни с каким другим наслаждением, включая то, о чем вы сейчас подумали.
Задачи патнемовской олимпиады-2024:
