14.08.2020 12:33
hse_spb 1 1800 Источник

Всем привет! Мы — студенты четвертого курса «Прикладной математики и информатики» Питерской Вышки. В июле мы поучаствовали в Математической регате Тинькофф, и в этом посте расскажем о том, что это за соревнование, о том, какова была наша стратегия, и покажем примеры задач.


image
Картинка с официального сайта Математической регаты


На нашей образовательной программе учат не только программированию, но и математике (поступайте!). Чтобы знания не застаивались, мы иногда участвуем в олимпиадах, и нам особенно привлекательны командные соревнования с интересными правилами. Под эти пожелания идеально подошла Математическая регата Тинькофф. Кстати, на соревновании даже предусмотрен денежный приз для команды-победительницы, но мы шли не за ним, а за тем, чтобы хорошо провести время.


Итак, 18 июля пятеро студентов-программистов, которые вошли в состав команды Just4Fun, собрались участвовать в первом туре соревнования. С нами соперничала 391 команда, в каждой было по 3–5 человек. Всего 1628 участников из 131 города мира.


Правила первого тура


Первый тур длился два с половиной часа. Было предложено 25 задач, разбитых по 5 уровням сложности и 5 темам: комбинаторика, числовые задачи, алгебра, теория вероятностей, геометрия.


Начальный капитал команды — 1000 очков. Каждая задача «стоит» от 100 до 500 очков: чем выше стоимость, тем сложнее задача. Если команда «покупает» задачу, ее стоимость вычитается из начального капитала (при этом нельзя уходить в минус). За верное решение с первой попытки начисляется $2x$ от стоимости задачи, со второй — $1.5x$, с третьей — $1x$.


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


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


image


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


Одновременно разрешалось открыть не более трех задач — серьезное ограничение для команд из пяти человек.


Первый тур


Так как все участники нашей команды находились в разных уголках России от Уфы до Санкт-Петербурга, у нас, к сожалению, не получилось собраться вживую ни на один из туров. Мы создали несколько комнат в видеоконференции и обсуждали решения в них. 


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


Мы решили бороться за бонус, который дадут первой команде, решившей все задачи стоимостью в 400 баллов. Мы выбрали такую стратегию, чтобы уменьшить конкуренцию: план показался нам самым нелогичным, ведь в начале соревнования нельзя открыть три задачи такой стоимости (начальный капитал всего лишь 1000) и в то же время бонус за эти задачи не самый ценный. 


Наш план увенчался успехом! В итоге мы решили все задачи первого тура, причем все, кроме одной, сдали с первой попытки. Вместе с бонусом это позволило нам занять второе место в первом этапе и пройти в финал.


image


Отдельно хочется остановиться на процессе решения задач. Все-таки мы скорее программисты, чем математики, и во время соревнования мы активно пользовались компьютером (это было разрешено правилами). Более половины задач мы решили при помощи Wolfram, Python и, неожиданно, C++ (для действительно быстрых переборов). С одной стороны, это не математично, но с другой — позволило решить задачи в максимально короткие сроки. 


Правила второго тура


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


image


Каждой задаче соответствовала доминошка (0:1, 0:2, ..., 6:6 — всего 27 штук).  В первые 2,5 часа команды решали задачи и собирали себе «снаряды» в виде доминошек.


Затем состоялась битва. Она продолжалась три раунда, в каждом из которых нужно было выбрать 7 доминошек — по одной на каждую команду соперников — и определить, какое из чисел доминошки будет соответствовать атаке, а какое защите. Затем команды отправляли организаторам ответы на задачи, соответствующие доминошкам. Если ответ неправильный, то и атака, и защита становились равны нулю. В течение боя можно было дорешивать задачи, ответ на которые еще не был найден.


Допустим, наша команда поставила доминошку [2:5] против команды N и решила, что число 5 будет соответствовать атаке, а 2 — защите. Команда N поставила против нас доминошку с защитой 3 и атакой 4. Тогда наша команда получит урон, равный 2 $(4-2=2)$, и команда N — тоже $(5-3=2)$. Каждое из этих чисел вычитается из очков команды, которая защищалась, и прибавляется к очкам нападающей команды. Побеждает команда с наибольшим количеством очков по итогам трех раундов.


Второй тур


Во втором туре нам интереснее всего было выбирать, какие задачи использовать в раунде и против кого, а потом ждать результатов, радоваться или грустить в зависимости от того, попали по нам противники или нет. Что касается задач, то были как интересные, так и не очень; как те, которые можно было запрограммировать, так и те, которые приходилось решать математически. 


К началу первого раунда мы решили порядка 15 задач разной сложности и этого не хватало на все три тура (нужна 21 задача). Во время боя нам в авральном режиме пришлось решать задачи попроще, которые прежде казались скучными, чтобы получить хоть сколько-нибудь очков. В итоге мы почти справились, но в поле ответа 21-ой задачи все-таки был отправлен рандом. 


По результатам финального тура мы заняли второе место, сильно отстав от первой команды и прилично обогнав третью. У нас 25 очков, у первой 55 и у третьей 14.


Общие впечатления


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


Задачки с турнира


Задача из первого тура


Тема: Вероятность. 
Стоимость: 500.
У Вани есть два доллара. Он подбрасывает монетку. Если выпадает орел, Ваня получает 2 доллара; если решка, он теряет половину своих денег. Если решка выпала два раза подряд, то игра заканчивается, при этом в последнем раунде Ваня не теряет деньги. Найти матожидание количества денег у Вани после окончания игры.


Решение:
Найдем количество последовательностей длины $n$ из орлов и решек с фиксированным последним элементом, в которых нет двух решек, идущих подряд.


Число последовательностей длины $n$ с последней решкой обозначим как $h(n)$, с последним орлом — $F(n)$.
$h(n) = F(n — 1)$ (нельзя, чтобы предпоследний элемент тоже был решкой). 
$F(n) = F(n — 1) + h(n - 1) = F(n - 1) + F(n - 2)$ (предпоследний элемент любой)


Получили последовательность Фибоначчи c начальными данными $F(0) = F(1) = 1$.


Допустим, Ваня сделал $n$ бросков и игра не закончилась. Зафиксируем последнюю выпавшую сторону монетки (орел или решка) и обозначим сумму Ваниных выигрышей по всем последовательностям, удовлетворяющим условиям (последняя сторона зафиксирована и нет двух решек подряд), как $f(n)$ (последний орел) и $g(n)$ (последняя решка).


Осталось написать рекуррентные соотношения на $f$ и $g$. 


Для начала разберемся с $g$. Заметим, что если последовательность оканчивается на решку, то предпоследним должен идти орел (т. к. двух последовательных решек быть не может), следовательно, $g(n) = \frac{f(n — 1)}{2}$, при выпадении решки Ванина сумма уменьшилась в два раза.


Теперь с $f$. В этом варианте предпоследним может быть как орел, так и решка. По условию, выпадения орла просто добавляет 2 к сумме, т. е. $f(n) = f(n — 1) + g(n - 1) + 2F(n)$ (вот для этого $F$ были посчитаны заранее).


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


Игра заканчивается тогда, когда Ваня выбрасывает вторую решку подряд. Заметим, что вероятность в итоге получить конкретную последовательность длины $n  > 1$ (с двумя решками в конце) это $\frac{1}{2^n}$ (случайно равновероятно выбираем каждый элемент). Тогда осталось найти $\sum\limits_{i = 2}^{+\infty} \frac{g(i — 1)}{2^i} = \frac{f(i - 2)}{2^{i + 1}}$.


Это некоторое техническое упражнение, далее идут соответствующие выкладки. Опустим корректность перестановки слагаемых в суммах.


Сперва вспомогательная сумма:


$S_1 = \sum_{n = 1}^{\infty} \frac{F(n)}{2^n} = F(1) + \sum_{n=2}^{\infty} \frac {F(n — 1) + F(n - 2)} {2 ^ n} = \\ = F(1) + \frac{3}{4} \sum_{n = 1}^{\infty} \frac{F(n)}{2 ^ n} = F(1) + \frac{3}{4} S_1    \implies S_1 = 4$


И аналогичные действия уже для нашей рекурренты:


$S_2 = \sum \frac{f(n)}{ 2 ^ {n + 3}} = \sum \frac {F(n)} {2 ^ {n + 2}} + \sum \frac {f(n — 1) + f(n - 2) / 2} {2 ^ {n + 3}} = \\ = S_1 / 4 + \frac{5}{8} S_2 \implies S_2 = \frac{8}{3}$


Ответ: $\frac{8}{3}$


Задача из второго тура


Соответствовала доминошке [2:3].


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


Математическое решение:
Заметим, что повороты кубика рубика можно описать с помощью некоторой подгруппы симметрической группы S_48. 


Обозначим поворот фронтальной части как $F$, а нижней как $D$. В таких обозначениях мы с кубиком сначала совершаем операцию $F$, а затем операцию $D$. Таким образом, если кубик находился в состоянии $x$, то он после одного хода перейдет в состояние $DFx$. Мы хотим найти минимальное количество шагов, которое нужно, чтобы перевести кубик в исходное состояние. Т. е. нужно посчитать порядок элемента $DF$. И $D$, и $F$ описываются перемножением перестановок. Давайте перемножим их все и обозначим результат как некоторую перестановку p. Чтобы посчитать ее порядок, достаточно найти НОК длин ее циклов.


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


Ответ: 105.