The strategy “choose the most illogical strategy”, or how we took second place in the Tinkoff Mathematical Regatta

Hello! We are fourth year students “Applied Mathematics and Computer Science»St. Petersburg HSE. In July, we took part in Tinkoff Mathematical Regatta, and in this post we will tell you what kind of competition it is, what our strategy was, and show examples of problems.

Picture from official site Mathematical regatta

Our educational program teaches not only programming, but also mathematics (do it!)… So that knowledge does not stagnate, we sometimes participate in olympiads, and we are especially attractive to team competitions with interesting rules. The Tinkoff Mathematical Regatta was ideal for these wishes. By the way, the competition even provides a cash prize for the winning team, but we did not follow him, but to have a good time 🙂

So, on July 18th, five student programmers who were part of the Just4Fun team gathered to participate in the first round of the competition. 391 teams competed with us, each of them had 3-5 people. A total of 1628 participants from 131 cities of the world.

First round rules

The first round lasted two and a half hours. 25 problems were proposed, divided into 5 levels of difficulty and 5 topics: combinatorics, numerical problems, algebra, probability theory, geometry.

The initial capital of the team is 1000 points. Each task “costs” from 100 to 500 points: the higher the cost, the more difficult the task. If the team “buys” a task, its cost is deducted from the initial capital (and you cannot go into a minus). For the correct decision on the first try, $ inline $ 2x $ inline $ from the cost of the task, from the second – $ inline $ 1.5x $ inline $, with the third – $ inline $ 1x $ inline $

Each task has an answer in the form of a number that must be entered in the appropriate field on the site. Only the captain can buy and turn in tasks.

It was necessary to maximize points by buying and solving problems.

There were also several ways to get bonus points. For example, they were awarded to the team that was the first to solve all problems from one topic or one level of difficulty, and to the first team to pass all the problems without a single mistake. The more difficult it was to fulfill the condition for receiving the bonus, the more points it brought.

No more than three problems were allowed to open at a time – a serious limitation for teams of five.

First tour

Since all the members of our team were in different parts of Russia from Ufa to St. Petersburg, we, unfortunately, did not manage to get together live for any of the tours. We created several videoconference rooms and discussed solutions in them.

Having carefully studied the rules and looked at the problems of the last year, we realized that the main struggle in the first round will be for bonus points. There are eight teams going to the second round, and surely out of more than 300 participating teams there will be eight (or even more!) Of them that will solve all the problems.

We decided to fight for the bonus that will be given to the first team to complete all tasks worth 400 points. We chose this strategy in order to reduce competition: the plan seemed to us the most illogical, because at the beginning of the competition it is impossible to open three tasks of such a value (initial capital is only 1000) and at the same time the bonus for these tasks is not the most valuable.

Our plan was crowned with success! As a result, we solved all the problems of the first round, and all but one passed on the first try. Together with the bonus, this allowed us to take second place in the first stage and go to the final.

I would also like to dwell on the process of solving problems. After all, we are more programmers than mathematicians, and during the competition we actively used the computer (this was allowed by the rules). We solved more than half of the problems using Wolfram, Python and, unexpectedly, C ++ (for really fast enumeration). On the one hand, it is not mathematical, but on the other hand, it allowed solving problems as soon as possible.

Second round rules

In the second round, there were already significantly fewer participants and the organizers came up with a simple combat system based on dominoes.

Each problem has a corresponding domino (0: 1, 0: 2, …, 6: 6 – 27 pieces in total). In the first 2.5 hours, the teams were solving problems and collecting “shells” in the form of dominoes.

Then the battle took place. It lasted three rounds, in each of which it was necessary to choose 7 dominoes – one for each opposing team – and determine which of the domino numbers would correspond to the attack and which to the defense. Then the teams sent the organizers answers to the problems corresponding to the dominoes. If the answer is incorrect, then both attack and defense become equal to zero. During the battle, it was possible to complete the tasks, the answer to which had not yet been found.

Let’s say our team has put a domino [2:5] against team N and decided that the number 5 would correspond to attack and 2 to defense. Team N put a domino against us with defense 3 and attack 4. Then our team will take damage equal to 2 $ inline $ (4-2 = 2) $ inline $, and team N is also $ inline $ (5-3 = 2) $ inline $… Each of these numbers is subtracted from the points of the defending team and added to the points of the attacking team. The team with the most points in the three rounds wins.

Second round

In the second round, it was most interesting for us to choose which tasks to use in the round and against whom, and then wait for the results, rejoice or be sad, depending on whether the opponents hit us or not. As for the tasks, they were both interesting and not very; both those that could be programmed and those that had to be solved mathematically.

By the beginning of the first round, we had solved about 15 problems of varying difficulty, and this was not enough for all three rounds (21 problems are needed). During the battle, in an emergency mode, we had to solve simpler tasks that previously seemed boring in order to get at least some points. In the end, we almost did it, but in the answer field of the 21st problem, a random was still sent.

According to the results of the final round, we took the second place, far behind the first team and well ahead of the third. We have 25 points, the first has 55 and the third has 14.

General impressions

What we liked the most was not the problems, but the format of the competition. It was necessary to work in a team, and it reminded school physics and matboys. Coming up with a strategy and arguing about solutions was much more fun than just solving problems. Next year we are going to participate in team fights again – we hope that already offline.

Challenges from the tournament

Problem from the first round

Topic: Probability.
Cost: 500.

Vanya has two dollars. He tosses a coin. If heads, Vanya gets 2 dollars; if it’s tails, he loses half of his money. If heads come up twice in a row, then the game ends, while in the last round Vanya does not lose money. Find the expected value of the amount of money Vanya has after the end of the game.

Decision:

Find the number of sequences of length $ inline $ n $ inline $ from heads and tails with a fixed last element, in which there are no two tails in a row.

Number of length sequences $ inline $ n $ inline $ with the last tails we denote as $ inline $ h (n) $ inline $, with the last eagle – $ inline $ F (n) $ inline $
$ inline $ h (n) = F (n – 1) $ inline $ (it is impossible for the penultimate element to be also tails).
$ inline $ F (n) = F (n – 1) + h (n – 1) = F (n – 1) + F (n – 2) $ inline $ (penultimate element any)

Received the Fibonacci sequence with initial data $ inline $ F (0) = F (1) = 1 $ inline $

Let’s say Vanya did $ inline $ n $ inline $ shots and the game is not over. We fix the last side of the coin (heads or tails) and denote the sum of Vania’s winnings over all sequences satisfying the conditions (the last side is fixed and there are no two tails in a row) as $ inline $ f (n) $ inline $ (the last eagle) and $ inline $ g (n) $ inline $ (last heads).

It remains to write the recurrence relations on $ inline $ f $ inline $ and $ inline $ g $ inline $

First, let’s deal with $ inline $ g $ inline $… Note that if the sequence ends in tails, then the penultimate must go heads (since there can be no two consecutive tails), therefore, $ inline $ g (n) = frac {f (n – 1)} {2} $ inline $, when Vanin comes up tails, the amount is halved.

Now with $ inline $ f $ inline $… In this variation, the penultimate can be either heads or tails. By hypothesis, getting heads just adds 2 to the total, i.e. $ inline $ f (n) = f (n – 1) + g (n – 1) + 2F (n) $ inline $ (here for this $ inline $ F $ inline $ were calculated in advance).

All intermediate calculations have been done, it remains only to calculate the answer.

The game ends when Vanya throws the second heads in a row. Note that the probability of eventually getting a specific sequence of length $ inline $ n> 1 $ inline $ (with two heads at the end) is $ inline $ frac {1} {2 ^ n} $ inline $ (randomly select each element with equal probability). Then it remains to find $ inline $ sum limits_ {i = 2} ^ {+ infty} frac {g (i – 1)} {2 ^ i} = frac {f (i – 2)} {2 ^ {i + 1}} $ inline $

This is some technical exercise, followed by the corresponding calculations. Let us omit the correctness of the permutation of the terms in the sums.

First, the auxiliary amount:

$$ display $$ 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 $$ display $$

And similar actions already for our recurrent:

$$ display $$ 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} $$ display $$

Answer: $ inline $ frac {8} {3} $ inline $

Problem from the second round

Matched the domino [2:3]…

I remember most of all one simple problem from the second round. It required counting how many times the operation had to be performed $ inline $ DF $ inline $ with a Rubik’s cube so that it returns to its original state (operation $ inline $ DF $ inline $: first turn the front section clockwise, then turn the bottom section clockwise).

Mathematical solution:

Note that rotations of the Rubik’s cube can be described using some subgroup symmetric group S_48

Let us denote the rotation of the frontal part as $ inline $ F $ inline $and the bottom as $ inline $ D $ inline $… In such notation, we first perform the operation with the cube $ inline $ F $ inline $and then the operation $ inline $ D $ inline $… Thus, if the cube was in the state $ inline $ x $ inline $, then after one move it will go to the state $ inline $ DFx $ inline $… We want to find the minimum number of steps needed to return the cube to its original state. That is, you need to calculate the order of the element $ inline $ DF $ inline $… AND $ inline $ D $ inline $and $ inline $ F $ inline $ are described by multiplication of permutations. Let’s multiply them all and denote the result as some permutation p. To calculate its order, it is enough to find the LCM of the lengths of its cycles.

By multiplying the permutations, we realized that it would take 105 steps. But in order to be sure that the problem will definitely turn out to be completed on the first try, we asked one team member to still scroll the cube faces about a hundred times to check.

Answer: 105.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *