OI 与其高考数学应用

| 0 | 总字数 996 | 期望阅读时间 4 min
  1. 1. OI 与其高考数学应用
    1. 1.1. Pro 01
    2. 1.2. Pro 02

OI 与其高考数学应用

假的标题…

Pro 01

几位大学生响应国家的创业号召,开发了一款应用软件。为激发大家学习数学的兴趣,他们推出了“解题获取软件激活码”的活动。这款软件的激活码为下面数学问题的答案:已知数列$1, 1, 2, 1, 2, 4, 1, 2, 4, 8, 1, 2, 4, 8, 16, \cdots$,其中第一项是$2^0$,接下来两项是$2^0, 2^1$,再接下来三项是$2^0, 2^1, 2^2$,依此类推。求满足如下条件的最小整数$N:N > 100$且该数列的前$N$项和为$2$的整数幂。那么该款软件的激活码为( )

A B C D
440 330 220 110

高考中的新题的解法,往往都可以联系到 OI 上去。我们称此题最终构造的数列为$A$,处理$A$这个整体会不方便,想到每一个子数列为$B$,则$A$为$n$个$B$首尾相接,且最后还会有一段剩余序列$C$,于是有

$$
A:\underbrace{[2^0]}_{B_1}, \underbrace{[2^0, 2^1]}_{B_2}, \underbrace{[2^0, 2^1, 2^2]}_{B_3}, \cdots, \underbrace{[2^0, 2^1, 2^2, \cdots,2^{n - 1}]}_{B_n}, C
$$

注意到,若对此数列求和,$S = \sum_{i = 1}^{n}{\sum{B_i}} + \sum{C}$,若求$\sum{B_i}$,对于高中数学,可以用差比数列求和方式。对于OIer,可以发现$B_i$与二进制的关系,即$\sum{B_i} = 2^i - 1$,则$\sum_{i = 1}^{n}{\sum{B_i}} = 2^{n + 1} - (n + 2)$。此时能够想到,若$S = 2^k, k \in \mathbb{N^+}$,则

$$
\sum{C} - (n + 2) = 2^k - 2^{n + 1} \Rightarrow \sum{C} = 2^{n + 1}(2^{k - (n + 1)} - 1) + (n + 2)
$$

很显然,若$k > n + 1$,有$\sum{C} > B_n$,与$C$的定义冲突,故$k = n + 1$,$\sum{C} = n + 2$,假设$C = B_t$,满足$\sum{C} = 2^t - 1$

对于考场做题,对于整体的数列$B$总共占位$(n^2 + n)/2$,分别带入选项,可得$29 \times 29 + 29 = 870$,剩余为$5$,则$5 + 3 = 2^3$,满足条件,其余检验略(我记得有优化)。欸,有点记不到当初做题时候怎么排除选项的了,先这样吧(结尾水)。

Pro 02

定义”规范01数列“${a_n}$如下:${a_n}$共有$2m$项,其中$m$项为$0$,$m$项为$1$,且对于任意$k \le 2m, a_1, a_2, \cdots,a_k$中$0$的个数不少于$1$的个数,若$m = 4$,则不同的”规范01数列“共有多少个?

第一次见这题是在 mgt 博客上,第二次见是小题狂练,mgt 博客给出的方法是 dp,小题狂练给出的方法是枚举。经同桌尝试,纯粹的枚举在考场上基本不可行。是否有一种,容易想到,且容易计算的方法,能够优雅地解决这个选择压轴题?

首先,对于$a_n$的前缀和数列$S_n$,满足$S_k \ge 0$,且$S_{2n} = 0$(将数列中的$0$看成$-1$)。对于 OIer 们容易想到$f[i][j]$,最后取$f[n][0]$,但是抽象的$f[i][j]$不适合打草稿——这是初始的想法。当然,对于没有 OI 的文化课选手,其实也能想到该方法(比如我,我个人是先想到该方法再想到 dp 的),详见 16 年 Ⅱ 卷的选择题第五题。本题是 16 年 Ⅲ 卷的选择题,这解法上微妙的巧合,不得不让人兴奋。

首先的首先,需要画一个坐标系。如图:
Clipboard - 2020-04-19 16.10.56

然后就做完了。

看到$(8, 0)$的点,其对应的值是$14$,此题答案$14$。每一个点$(i, j)$对应的横坐标的意义是,这个数列长度为$i$,而$j$的意义是,此时前缀和为$j$。则$(8, 0)$表示,长度为$8$的数列,其中$0, 1$个数(计算过程中的$0, -1$)相等。每一个点,其值都等于其左上的点与左下点值的和,因为数列长度增长一,要不然前缀和加$1$,要不然$-1$。