Die Strategie "wähle die unlogischste Strategie" oder wie wir den zweiten Platz bei der Tinkoff Mathematical Regatta belegt haben

Hallo! Wir studieren im vierten Jahr Angewandte Mathematik und Informatik an der HSE in St. Petersburg. Im Juli haben wir an der Tinkoff Mathematical Regatta teilgenommen. In diesem Beitrag werden wir Ihnen sagen, um welche Art von Wettbewerb es sich handelt, welche Strategie wir verfolgt haben, und Beispiele für Probleme zeigen.

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

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