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

Hello! We are fourth-year students in Applied Mathematics and Informatics at the St. Petersburg HSE. In July, we took part in the 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 the official website of the Mathematical Regatta

Our educational program teaches not only programming, but also mathematics (do it!). , , . . , -, , , .

, 18 -, Just4Fun, . 391 , 3–5 . 1628 131 .

. 25 , 5 5 : , , , , .

— 1000 . «» 100 500 : , . «» , ( ). $$$2x$ , — $$$1.5x$, — $$$1x$.

, . .

, .

. , , , , . , . 

— .

-, , , . . 

, , . , 300 - ( !) , .

, , 400 . , : , ( 1000) . 

! , , , . .

. - , , ( ). Wolfram, Python , , C++ ( ). , , — . 

.

(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.