Strategi "pilih strategi yang paling tidak logis", atau bagaimana kami menempati posisi kedua di Tinkoff Mathematical Regatta

Halo! Kami adalah siswa tahun keempat Matematika Terapan dan Informatika di St. Petersburg HSE. Pada bulan Juli kami mengambil bagian dalam Tinkoff Mathematical Regatta , dan dalam posting ini kami akan memberi tahu Anda seperti apa kompetisi itu, apa strategi kami, dan menunjukkan contoh masalah.

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

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