该策略“选择最不合逻辑的策略”，或者我们如何在Tinkoff数学赛中获得第二名

你好！我们是圣彼得堡HSE应用数学和信息学的四年级学生。7月，我们参加了Tinkoff数学竞赛，在这篇文章中，我们将告诉您这是一场什么样的竞赛，我们的战略是什么，并举例说明问题。

图片来自“数学帆船赛”官方网站

我们的教育课程不仅教授编程，还教授数学 （做！）... 为了使知识不会停滞不前，我们有时会参加奥林匹克竞赛，并且对于具有有趣规则的团队比赛特别有吸引力。Tinkoff数学帆船赛非常适合这些愿望。顺便说一下，比赛甚至为获胜的团队提供了现金奖励，但是我们没有跟随他，而是为了度过美好的时光。

因此，在7月18日，属于Just4Fun团队的五名学生程序员聚集在一起参加了第一轮比赛。391个团队与我们竞争，每个团队都有3-5人。来自世界131个城市的1628名参与者。

第一轮规则

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