A estratégia "escolher a estratégia mais ilógica", ou como ficamos em segundo lugar na Regata Matemática Tinkoff

Olá! Somos alunos do quarto ano de Matemática Aplicada e Informática no HSE de São Petersburgo. Em julho, participamos da Tinkoff Mathematical Regatta , e neste post vamos contar para vocês que tipo de competição é, qual foi a nossa estratégia, e mostrar exemplos de problemas.

,  (!). , , . . , -, , , .

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