Математическая олимпиада им. Уильяма Лоуэлла Патнема (William Lowell Putnam Mathematical Competition) — математическая олимпиада для студентов бакалавриата, обучающихся в университетах (колледжах) США и Канады. Вдохновителем олимпиады был Уильям Лоуэлл Патнем, американский юрист и банкир. Проводится Математической ассоциацией Америки ежегодно с 1938 года. Денежными призами награждаются пять лучших университетских команд (приз $25 000 за первое место) и двадцать пять студентов, лучших в личном зачете (приз $1000 за первое место).
— Википедия
Длится олимпиада два раза по 3 часа, всего 12 задач по 10 баллов за каждую. Средний балл, который набирают студенты — 1 или 2. Рассмотрим одну из самых сложных задач из этой олимпиады.
![image](https://habrastorage.org/webt/jd/h5/kp/jdh5kpztsgeohtqaqmajjwa6on8.jpeg)
Выберем 4 случайные точки на сфере. Какова вероятность что центр сферы будет внутри тетраэдра, образованного этими точками?
Рассмотрим двумерный вариант этой задачи.
![image](https://habrastorage.org/webt/gp/sb/-m/gpsb-mmdoea_giyuhqrq87n5xow.jpeg)
Рассмотрим 3 случайные точки на окружности. Какова вероятность, что центр окружности будет внутри треугольника?
![image](https://habrastorage.org/webt/l-/io/zw/l-iozweqwnwis2jazej49etyasq.jpeg)
Можно закрепить две точки и поиграться с третьей. Легко заметить, что есть определенная зона, проекции закрепленных точек относительно центра, внутрь которой должна попасть третья точка, чтобы выполнилось условие. Окружность тем самым разделяется на 4 части. Вероятность попадания третей точки в дугу, равна отношению длины дуги к длине окружности. Какова длина дуги?
![image](https://habrastorage.org/webt/tf/ol/rq/tfolrqzmrrxhptigqa2oyx_uvvo.jpeg)
Вероятность колеблется от 0 до 0,5 в зависимости от расположения первых двух точек.
Какова средняя вероятность?
![image](https://habrastorage.org/webt/dy/y7/5g/dyy75g8hk1-t_4fkiszpjkyzaew.jpeg)
Зафиксируем первую точку и поиграемся со второй. Вероятность будет меняться от 0 до 0,5, то есть средняя вероятность будет 0,25.
Решение задачи для окружности и трёх точек — 25%.
Можно ли перенести такой подход на сферу и 4 точки?
![image](https://habrastorage.org/webt/33/7-/0p/337-0p4cp3-i7hlggxqufesgqx0.jpeg)
Фиксируем три точки и играем с четвертой. Нарисуем проекции фиксированных точек относительно центра и плоскостями разделим сферу на 8 частей.
![image](https://habrastorage.org/webt/zm/im/5h/zmim5ho9bqbgwf5ijoasxqef_yi.jpeg)
Центр сферы будет находиться внутри тетраэдра, если четвертая точка попадает на зеленый сферический треугольник, который находится «напротив» зафиксированных точек относительно центра. Каков средний размер зеленой секции?
//Дальше не придумали, импровизируй.
Можно вернуться к двумерному случаю и подумать откуда взялась 1/4. Откуда 4?
![image](https://habrastorage.org/webt/mo/qd/iz/moqdizqp3kpkq-i0obeopuc-u98.jpeg)
Можно перейти от 3 случайных точек на окружности к другой задаче. Выберем два случайных диаметра. Потом для каждого диаметра бросим монетку, выбирая тем самым, где будет точка Pi, с какого конца диаметра. Потом случайно выберем третью точку на окружности.
А потом еще хитрый ход.
Давайте сначала выберем случайным образом третью точку, а потом случайно выберем два диаметра. У нас будет 4 варианта размещения точек P2 P1:
![image](https://habrastorage.org/webt/ne/xl/gc/nexlgc1jnlb8ogrdq2wkneshxhu.jpeg)
Но только один из этих 4 вариантов содержит решение, когда центр окружности внутри треугольника:
![image](https://habrastorage.org/webt/gd/ib/f5/gdibf5ixrxwfjjbgdbm4ghkox6w.jpeg)
Какую бы мы ни выбирали рандомную начальную позицию третей точки и двух диаметров, только один из вариантов содержит центр окружности внутри треугольника:
![image](https://habrastorage.org/webt/cp/gy/ne/cpgynemwyhm_430tqm8o6nqx6bs.jpeg)
То как мы переформулировали задачу:
![image](https://habrastorage.org/webt/6s/_n/am/6s_nam7qw6esz7sve4ufm2vpr-c.jpeg)
Со сферой получается 8 вариантов выбора точек, после того, как зафиксирована первая точка и выбраны три диаметра:
![image](https://habrastorage.org/webt/kw/q4/6n/kwq46ncx4ophbox0t7xwmnonwhc.jpeg)
Только 1 из 8 удовлетворяет условию, что центр сферы внутри тетраэдра:
![image](https://habrastorage.org/webt/l3/pl/qi/l3plqincmwg6h83c9_n9lqepxdc.jpeg)
Ответ: 1/8
- Хардкорная линейная алгебра здесь: Capturing the Origin with Random Points: Generalizations of a Putnam Problem
- Все задачи олимпиады 1992 года: The 53rd William Lowell Putnam Mathematical Competition
Saturday, December 5, 1992
kronos
-