О стартовых взносах

Еще немного математики ориентирования, на этот раз тема гораздо более злободневная. Не стоит воспринимать результаты буквально, единственная моя цель - показать примерное поведение системы с помощью очень грубой модели и найти какие-то общие закономерности. Все совпадения с реальной жизнью случайны.

Итак, задача: найти оптимальный стартовый взнос для соревнований.
И сразу, чтобы внести ясность - здесь и далее "оптимальный" = "дающий максимальную прибыль". Тыкать пальцем в небо не стану, а применю математику. Для этого нужно построить примерную математическую модель (при этом "примерную" - это может быть даже слишком мягкое слово, модель будет очень примерной - такими же будут и результаты, но об этом я уже предупреждал).

Построение математической модели начну с расходов. Пусть расходы делятся на две категории:
1) Общие расходы, не зависящие от количества участников (работа судей, организация центра соревнований, аренда спорткомлекса/парковки, расходные материалы). Обозначим их "C".
2) Расходы на одного участника (печать/покупка карты, аренда отметки). Обозначим как "a".

От расходов сразу перехожу к доходам. Поскольку искомое значение - это размер стартового взноса, его я и обозначу как "x". Имея конкретные условия старта (время, место, карта, реклама, призы и т.д.), меняем только стартовый взнос. Количество участников в фиксированыых условиях, соответственно, будет функцией от стартового взноса - пока просто обозначаю как "f(x)".
Теперь есть все, чтобы найти суммарный доход от соревнований "P" - количество участников, умноженное на доход от одно участника (стартовый взнос минус затраты на участника), минус общий расход. Если проще, то:

P = f(x) * (x - a) - C

Наша задача - найти х, при котором P максимально (кстати говоря, при этом оно не обязательно положительно - это жестокое жизненное уточнение). Задача, если не ошибаюсь, из школьной программы 10-го или 11-го класса. Для поиска локального максимума (и минимума) нужно найти корни производной. Поехали:

P' = (f(x) * (x - a))' - C' = f'(x) * (x - a) + f(x) * (x - a)' - 0 = f'(x) * (x - a) + f(x)

f'(x) * (x - a) + f(x) = 0

На этом у меня всё.
Шутка.
Ну то есть дальше остается только сделать шаг, который сделает математическую модель "сферическими соревнованиями в вакууме". Ну и ладно.
f(x) - влияние стартового взноса на количество участников. Что, вообще, можно предположить про эту функцию.
1) Она монотонно убывающая. Было бы довольно странно, если бы количество участников росло, при увеличении стартового взноса (хотя с коллективным сознанием чего только не случается).
2) Имея свой максимум при нулевом стартовом взносе (в отрицательный стартовый взнос я не полезу) она сначала уменьшается довольно медленно (стартовый взнос в 1-2 рубля мало кого испугает).
3) Достигнув некоего значения (пусть будет "P1") стартовый взнос уже начинает оказывать существенное влияние на посещаемость, отток увеличивается.
4) Достигнув значения "P2" мы потеряли почти всех участников. Оставшиеся утекают медленнее, но рано или поздно f(x) все таки достигнет нуля. Впрочем, эта часть функции нас уже интересует меньше.

Естественно, для анализа функции ее нужно сделать непрерывной, так что с нецелым числом копеек и участников придется смириться. Кстати, еще одним упрощением модели является одинаковый стартовый взнос для всех участников, иначе считать все пришлось бы для каждой группы отдельно.
Набросаю такие условия:
1) При стартовом взносе 0 рублей наш старт посетит 250 человек.
2) При взносе в 5 рублей 10 человек откололось, осталось 240 человек.
3) Взнос в 25 рублей оставил нас с 10-ю отчаяными фанатами.
4) При 30 рублях участников не осталось.

Дальше воспользуюсь онлайн приложением (https://tools.timodenk.com/cubic-spline-interpolation) и проинтерполирую. Получаю такой график.

Сложно сказать, насколько он похож на правду, но выглядит неплохо.
Запись функции выглядит не так красиво:

Возвращаясь к выражению

f'(x) * (x - a) + f(x) = 0

посчитать его нужно будет для каждой из трех функций отдельно и найти корни, попадающие в соответствующий отрезок. Перед этим, нужно еще установить значение для "a" - расхода на одного участника. Пусть будет 3 рубля для начала, потом с этим можно будет поиграться.

Всю грязную работу я тут показывать не буду, в конце концов результатом будет кубическое уравнение. Его, конечно, я тоже не буду решать сам, для этого использую https://www.symbolab.com/solver/polynomial-equation-calculator/

Ну а результатом всего этого математического безобразия станет число x ~ 13.43 рубля. Количество участников f(x) ~ 148 человек.

Поиграемся значением расходов. При той же функции f(x) установим a = 0 рублей (не очень жизненно). x ~ 12,14, f(x) ~ 166.

a = 6 рублей. x ~ 14.87 рублей, f(x) ~ 127 человек.

В общем, это довольно интуитивно, увеличение затрат на человека двигает оптимальный стартовый взнос вверх (в данном случае примерно в 2 раза медленней самого взноса).

Так получилось, что начал я сразу с более сложной модели, но можно попробовать упростить её вот так:

Проще - не значит хуже, возможно завсимость участников от стартового взноса ближе к линейной. Расчет с похожими входными данными:

f(x) = 250 - 250 * x / 30

Тут уже не нужны сторонние приложения, несколько подсчетов, и получаем:

x = (30 + a) / 2

То есть, в этой модели оптимальное x больше (а f(x), соответственно меньше).

При а = 3, x = 17.5 - дополнительных 4 рубля. f(x) = 125 - минус 23 человека.

С такой зависимостью, кстати, оптимальный стартовый взнос достигается при числе участников меньше половины от максимально возможного.

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

Какая она на самом деле? Да кто ж его знает.

О рассевах

Подготовка масс-старта матчевой 2017 разбудила во мне математика и заставила чуть глубже взглянуть на известный вопрос рассеивания. Чтобы не потерять свои мысли просто так, я постараюсь их тут систематизировать.

Начну с азов: рассев "бабочка". Для экономия места дальше я везде буду использовать правый вариант (линия со стрелками может обозначать линейный участок дистанции любой длины), опуская все нерассевные КП, не представляющие интереса.

Все читающие это сразу скажут, что число рассевов, которые дает такой элемент - 2.
Можно чуть усложнить задачу, добавив бабочке еще одну петлю.

Исходя из опыта или быстрого подсчета, большинство легко ответят, что число рассевов здесь равно 6. На всякий случай, все возможные порядки прохождения: 123, 132, 213, 231, 312, 321.
В общем случае, для бабочки из n петель число рассевов (пусть оно дальше обозначается как R) равно n! = n*(n-1)* ... *3*2*1
То есть для 4-х петель R=24, для 5 - R=120. Это уже явно покрывает потребности любого старта, но пятикратное посещение одного пункта может вызвать ощутимое отторжение у спортсменов. На практике такой рассев можно реализовать с центром на старте/финише, заодно организовав там подпитку и смену карт. На ум приходит марафон в Багуте 2013, матчевая 2004 в Боровой, если покопаться в памяти хорошо, таких стартов можно будет вспомнить довольно много.

Идем дальше. Ф-рассев, "карусельска", "лепесток", то ли я забыл, то ли никогда не знал его правильного названия.

Тут тоже все понятно - 2 варианта рассева, рассев такого плана используется сейчас повсеместно и, похоже, бесповоротно вытеснил "бабочку". Наверное, основной причиной является то, насколько органичней можно вписать "лепесток" в дистанцию, а при наличии смены карт еще и скрыть рассев от участников.
Хотя встретить такой рассев можно много где, всегда используется только самая простая его вариация - 2 пути вперед, 1 - назад. В общем случае, рассев может выглядеть как 2 пункта, с n вариантами пути вперед, n-1 - назад. В таком случае, R=n!*(n-1)! - то есть много (для n=3, R=12; n=4, R=144). Проблемы те же, что и в "бабочках" с большим количеством лепестков. На практике, решить их можно также, сделав одну из точек стартом/финишем, а вторую - подпиткой.

По крайней мере, такая дистанция не выглядит безнадежной.

Следующий базовый (или уже нет?) факт - комбинация независимых рассевов. Если и "бабочки" и "карусельки" вы любите одинаково, можете попробовать такую конфигурацию:

Число рассевов для дистанции, состоящей из независимых элементов, равно произведению числа рассевов для каждого элемента в отдельности. В данном случае R=2*2=4
Чтобы быть независимыми, рассевы не обязательно должны быть соединены последовательно, с таким же успехом можно использовать вложение одного в другой, как например тут:

Пока, все приведенные рассевы давали в результаты четное число вариантов. Вопрос, который возник у меня какое-то время назад: "Может ли число рассевов R, быть нечетным числом >2?"
Желающие, могут подумать, к этому вопросу я вернусь позже.

Пока рассмотрю еще один базовый тип рассеивания. Эстафету обычную или эстафету одного участника концептуально можно нарисовать так:

k - число участников эстафеты (либо количество кругов one-man-relay), n - количество рассевных элементов.
R=(k!)^n - довольно внушительное число. Если переводить в реальную жизнь, то для трехэтапной эстафеты, с 3 рассеиваниями R=(3!)^3=6^3=216. Количество различных неповторяющихся этапов меньше - это просто k^n, то есть 3^3=27.

Говоря про эстафеты, хочется поднять одну идею, навеянную эстафетой WOC2015 в Шотландии.
https://www.woc2015.org/images/Relay_All_Courses_map.png
Обратите внимание на схемы дистанций справа - они содержат не только стандартные тройные рассевы, но и неожиданные шестерные. На каждом этапе участники дважды проходят путь между КП 67 и 47. В теории это может дать R=6!=720 различных рассеиваний за счет только одного этого элемента. На практике, рассевы были сгруппированы попарно (иначе один участник мог бы получить 2 слишком похожих варианта, например 67-59-47 и 67-76-60-47). Таким образом R=6*4*2=48, что все равно больше двух последовательно соединенных тройных рассевов (R=36). Однако главным преимуществом является то, что паровоз может быть разбит сразу на 6 потоков, вместо обычных трех.
Идею можно продолжить, например, группировать варианты можно не попарно, а группами по 3, скажем ABC и DEF. Если варианты внутри групп близки между собой, нашим желанием будет сделать такие рассевы, при котором каждый участник проходит на своем этапе по одному варианту из каждой группы. Тогда R=6*3*4*2*2*1=288 (если вы нашли ошибку в этом вычисление - сообщайте). На самом деле, такое рассеивание может убить сразу двух зайцев: увеличить количество вариантов и провести участников по одной местности без заметных повторений (например, такой рассев можно применить на 1-ый КП, а потом сразу после зрительного КП).
Вот как этот элемент будет выглядеть схематично:

Вернусь к эстафете одного участника. Чаще всего, из практических соображений, такие старты проходят в 2 круга. Число рассеиваний в результате заметно уменьшается, но упрощается планировка и организация.
Говоря об one-man-relay обычно подразумевают рассев охватывающий всю дистанцию от старта до финиша, то есть такой формат:

На самом деле, это не всегда так, присмотритесь к такой дистанции: http://omaps.obelarus.net/show_map.php?user=romanb&map=523
Схема рассеивания выглядит хаотичной и сразу получила определение "паутинка".
Если присмотрется к рассевам от 1-го до 10-го КП и от 15-го до 27-го КП, формализовать их и исключить петлю у 22-го КП, в узких кругах известную как "березинская бабочка", не дающую рассева, получим такую схему дистанции.

Так можно увидеть два независимых рассева типа one-man-relay с двумя элементами рассеивания каждый. R=(2^2)*(2^2)=16

Пока количество рассевов можно было определить аналитически, но будет ли это так для любой дистанции. Перехожу к заключительной части анализа, разбору рассевов на матчевой 2017.
Предупреждение: эта чать может быть еще тяжелее для понимания, чем первая.
http://3drerun.worldofo.com/?id=-457865&type=info
Вообще говоря, какого-то конкретного рассева заранее не планировалось. One-man-relay предъявляет требования к хорошему старту/финишу и местности вокруг него (поскольку там нужно провести спортсменов как-минимум два раза), так что он был отброшен. "Паутинка" предоставляет больше свободы в выборе места рассеивания, ее минусом (с которым пришлось смириться), является перенасыщение карты линиями, сбивающими спортсменов.
Дистанции, в целом, планировалась без оглядки на рассевы, просто в местах, где точки можно было использовать несколько раз - это делалось. Только в редких случаях перегон делался для закольцовывания рассева (пожалуй только 36-40 для Д1). После этого оставалось посчитать, что же вышло в итоге, вот к этому я и перехожу.
Группа Д3 получила довольно простой рассев типа "лепесток" внутри "бабочки" с четырьмя вариантами. У Д2 и Д1 все было несколько сложнее. Дистанция Д2:

Для начала нужно упростить эту схему, оставив только рассевные КП (посещаемые несколько раз) и соединить их, если между ними существует участок дистанции.

Можно указать несколько способов упрощения.
1) Предположим, что мы вставляем петлю "бабочки" (как на КП 44) в любое место существующей дистанции. Если в точку вставки петли спортсмен прибегает дважды, то каждому варианту рассева изначальной дистанции можно поставить два варианта дистанции с "бабочкой" (с уходом на нее при первом посещении или при втором). В общем случае, петля увеличивает количество вариантов во столько раз, сколько раз точка посещается спортсменом (без учета самой бабочки).
Так "бабочку" можно довольно эффективно использовать не как самостоятельный, а как вспомогательный элемент рассеивания. Слегка изменю уже приведенный здесь рассев (слева), соединив вместе два элемента:

Для дистанции слева R=4, справа - R=2*2*3=12

Возвращаясь к схеме дистанции Д2, я запоминаю множитель 2 и дальше рассматриваю такую схему:

Следующее упрощение которое можно сделать:

2) Оба пути, выходящие из КП 47, ведут к КП 44. Есть два варианта, как поставить им в соответствие пути исходящие из КП 44 (в общем случае, для n путей - это будет число n!). Поскольку оба пути 47-44 симметричны, полученые уменьшенные дистанции будут одинаковые. Число рассевов уменьшенной дистанции можно будет просто умножить на два (то есть запоминаемые множитель теперь равен 4). В результате упрощения, КП 44 перестает быть рассевным.

Немного "причесав" схему, можно увидеть что-то очень похожее на one-man-relay элемент, только направление путей движения будет отличатся.

Видимых способов упрощения я больше не вижу. Не уверен, что многие сходу уверенно назовут число R такой дистанции (хотя 4, из-за сходства с дистанцией one-man-relay напрашивается). Благо, посчитать его несложно.

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

1) Берем первый рассевный КП (50), по очереди смотрим все выходящие из него пути (50-56, 50-47).

2) Для каждого пути предполагаем, что рассев начинается с него. В результате можно получить упрощенную схему дистанции. Если полученная схема уже известна и рассчитана (например дистанция распалась в линейную, с R=1), то останавливаемся, иначе рассчитываем R этим же алгоритмом (то опять с пункта 1).

3) Суммируем результаты, полученные для каждого пути, получаем R для изначальной дистанции.

Поехали. Если начать рассев с пути 50-56, то оставшаяся дистанция будет выглядеть так (КП 50 становится обычным линейным, и из схемы его можно убрать):

Дальше рассчитывать не обязательно - это классический "лепесток" с R=2.

Смотрим 50-47:

Двойная "березинская бабочка" - это красиво, но рассеиванию не помогает. По очереди убирая петли (и добавляя множитель 1), получим R=1.

Возвращаясь к исходной схеме дистанции, суммируем результаты для обоих путей, получаем R=3. Если вы еще помните вопрос о нечетных R, то вот ответ на него. Пожалуй, назову этот рассев "божьей коровкой".

Прямо скажем, эффективностью он не отличается, спортивная справедливость тоже прихрамывает (паровоз участников делится не равномерно и не одновременно), но уж такой он есть. Вообще-то, отдельные преимущества над схожим рассевом типа one-man-relay у него можно найти, но не с математической точки зрения, а с точки зрения планирования дистанции и разнообразия путей.

Осталось вернутся к исходной дистанции Д2. Множитель был равен 4, а значит R=4*3=12 вариантов рассева.

Для закрепление, вкратце тот же алгоритм для Д1

Формализация:

Убираем петлю:

Если полученную дистанцию обозначить Д1а, то R(Д1)=2*R(Д1а). Это все, чего можно добится симметричными упрощениями. Если продолжать вводить термины, то "паутинкой" я бы называл именно такие рассевы, неупрощаемые до линейных дистанций преобразованиями, которые я приводил выше. Но это уже малополезная информация для, собственно, ориентирования.

Фиксируем первым путем 51-46. Д1б:

КП 51 и 60 больше не являются рассевными, удаляя их получаем "божью коровку". R(Д1б)=3.

Возвращаясь назад фиксируем 51-60. Д1в:

Поскольку 51 больше не рассевный, в дистанции появилось 2 симметричных пути 60-46, один направляем к КП 36, второй к КП 40. Д1г:

Очередной выход "божьей коровки". R(Д1г)=3. Остается сложить всю формулу назад.

R(Д1)=2*R(Д1а), R(Д1а)=R(Д1б)+R(Д1в), R(Д1в)=2*R(Д1г), подставляя R(Д1б)=R(Д1г)=3: R(Д1)=2*(3+2*3)=2*9=18.

На волне математики и закончу (большинство все равно не дочитает до этого момента). На вопрос о нечетных R ответ нашелся, нетрудно показать алгоритм построения рассева с любым заданным R:

для такого рассева R=n+1. Остается вопрос оптимального, с точки зрения минимизации количества рассевных точек.

В общем виде сформулирую вопрос так: для заданного R, каким будет минимальное необходимое количество рассевных точек, необходимых для построения? Кстати, если формулировать задачу математическими терминами, ресь идет о построении ориентированного мультиграфа с заданным числом эйлеровых циклов, но это уже, пожалуй, перебор.

На этом пора закончивать.