Всё ещё проще. Пусть игроки играют не до k=11 очков, а фиксированные 2k-1 = 21 раунд. Тогда тот, кто в течение игры первым наберёт 11 очков, гарантировано выиграет по результатам 21 раунда. В результате мы получаем биномиальное распределение очков x, набранных первым игроком, а нас интересует вероятность P(x >= k), что соответствует кумулятивной вероятности 1-F(k; 2k-1, p) = F(k; 2k-1, q) которая выражается через регулярную неполную бета-функцию. P(x >=k ) = I_p(k, k). Ответ в виде графика можно спросить у вольфрам-альфы.

Это никоим образом не меняет сути. Положение точек L4 и L5 не зависят от масс. Если планета 2 находится в точке L4 планеты 1, то планета 1 автоматически находится в точке L5 планенты 2. И система оказывается устойчивой.

Речь шла про устойчивые системы. Две и более планеты в вершинах многоугольника — это пример неустойчивого равновесия.

Как раз идея в том, что их список — лишь начальное приближение. Поскольку он собирался на корпусах нэтивов, он не лучшим образом отражает то, как видят английский язык русскоговорящие люди.

Если бы у вас получилось прогнать эту задачу на SAT солвере и показать прирост скорости, было бы здорово.

Было бы интересно понять, за счёт чего.

Не сочтите за рекламу, но вот пост, а вот само решение.

а есть ли математическое доказательство тому, что получилась именно кардиоида (в приближении), а не какая-то другая (похожая) фигура?

Это вполне может сойти за пример по математике для первокурсника технического вуза.

Вместо номера точки будем пользоваться её полярной координатой . Тогда точка соединяется прямой с точкой . Уравнение такой прямой в декартовых координатах:
.
Мы хотим найти огибающую семейства прямых . Не трудно показать (или прочитать в википедии), что для этого должно выполняться . Решив эту линейную систему уравнений, получим параметрическое уравнение огибающей: , . Что и требовалось доказать.

А в чем преимущество?

Я не утверждал, что для многогранника Монте-Карло будет чем-то лучше. Я написал «альтернативный алгоритм» =)

Вы невнимательно читали статью. Фактически поверхность тела разбивается на малые площадки (треугольники), а само тело представляется как алгебраическая сумма конусов с малыми телесными углами (вытянутых тетраэдров). Тогда от каждого такого конуса вклад в силу тяжести составит:


Конечно, мы нормальную проекцию площадки вычисляем через объём конуса , но это не отменяет того, что интегрируем мы по площади (хотя совсем корректно было бы сказать, что мы интегрируем по телесному углу, так как близкие треугольники нам приходится дополнительно разбивать, чтобы ).

Кстати, это сразу нам даёт идею для альтернативного алгоритма методом Монте-Карло: надо из точки пустить n лучей, и из расстояний от точки до пересечения лучей с телом можно будет посчитать итоговую силу.

Как же не уйти, если в статье интеграл берётся по площади = квадратичная зависимость.

Скорее всего имелось ввиду что-то типа этого, интегрирование потенциала, а затем взятие градиента. Но при таком способе вычислиельная трудность растёт как куб разбиения, а ошибка уменьшается линейно. Так себе способ.

Когда вы будете брать градиент потенциала, то внезапно ближайшие кубики начнут вносить вклад, и ещё огого какой.

Вот такая.


<zanuda>
Если уж вспоминать баяны классику, то хотя бы с верной формулировкой. Нужно требовать постоянную плотность. Если попросить, чтобы лишь массы и объёмы совпадали, то планета, большая часть массы которой сосредоточена в точке на поверхности, сможет иметь сколь угодно большое g, и задача не будет иметь смысла.
</zanuda>

2,6 %

Монте-Карло? Выкидывать рандомные билетики пока не выпадет счастливый или rand(0,1) не станет меньше 0.055252/(1-0.055252)

Я неточно выразился. Если U и V – множество рёбер одного и второго многранников соответственно, то все произведения u×v, где u∈U, а v∈V. В примере с тетраэдрами, два наиболее близких ребра дадут плоскость, которая им параллельна и которая разделяет тетраэдры.

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

Вообще, метод разделяющей оси в трёхмерном случае предполагает поиск оси, а не плоскости =) Если существует разделяющая плоскость, то проекция двух многогранников на нормаль к ней даст непересекающиеся отрезки (проверка непересечения в одномерном случае сильно проще). Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого. Наконец, существуют эвристики, как найти эту нормаль эффективно.

Я разобрался в авторском алгоритме выбора перпендкулярной плоскости.

// from Vector3.orthogonal
setFrom(-y, x, 0);

// from Plane.setFrom
zAxis.setFrom(normal); // = (x, y, z)
xAxis.setFrom(normal);
xAxis.orthogonal();    // = (-y, x, 0)

// from Plane.swapZY -- странное название
Vector3 temp = xAxis;
xAxis = zAxis;
zAxis = temp;          // = (-y, x, 0)

То есть почти всегда перпендикулярная плоскость выбирается с нормалью (-y, x, 0). Так что для приведённого примера всё хорошо, и я поспешил нарисовать к нему картинку. Но стоит повернуть тетраэдры неудачно, как проблема снова возникает.

Чтобы было понятно, я тут картинку нарисовал.