2024 高三海淀一模数学压轴题

EXODUS · 2024-12-22 00:17:13 · 学习·文化课

其实是沙布尔题，但我的确没办法把脑子里想的东西用很简洁的形式落到纸面上。

问题描述：有 m 个长为 m 的排列组成一个长度为 n=m^2 的数列 Q:a_1,a_2,\cdots,a_n．其中令数列 b 满足 b_1=1，b_k 是 p>b_{k-1} 且 a_p\geq k 的最小的 p，也就是在 a_{b_{k-1}} 往右找第一个值 \geq k 的位置。

当 m=2024 时，证明，对于所有的 Q，均有 b_{2023}\leq 20240。

记号约定：

• 长为 m 的排列定义为长度为 m，且 1,2,\cdots,m 均出现的数列。

问题分析（思考内容，不落纸面）

相当于第一次找 \geq 1 的数，再往后找最近的 \geq 2 的数，再往后找最近的 \geq 3 的数，证明一定能在 20240 之前找到 \geq 2023。如果想要推翻这个命题，需要尽可能地让每次找到的位置靠后一些。换句话说，就是需要构造一个 a 使得到 a_{20240} 时，找到的数的个数尽可能少（如果 <2023 就说明 2023 是在 a_{20240} 之后找到的，就推翻了结论），我们记这个找到的数为 F(a)。

如果把 a 分为 m 组，每组都是一个长为 m 的排列，对于排列和排列之间应该是没有很大影响的，那么先观察在一组内怎样构造才能让《经过完这个组之后找到的数尽可能少》，画一画能猜出来倒序排列一定是最优的情况。

这里我们称一个情况是优的，意思是它能让 F(a) 尽可能小。

一，问题转化

如果将找数策略从《在它后面的第一个 \geq k 的》改为找《在它后面的任意一个 \geq k 的》，记 F'(a) 为在 a 中可能能找到的最大的数，那么 F(a)=F'(a)。

这里的思路是，原先的过程太死板，性质并不太好挖掘，可以将限制适当放宽，发现和原问题等价，于是可以对新的这个限制更松的问题进行分析。

证明：

记 F(a) 中找到的下标序列为 b（也就是原题目中的 b），其长度为 |b|，F'(a) 中找到的下标序列为 b'，其长度为 |b'|。

由于 b 肯定是 b' 的一种可能，那么显然有 |b|\leq |b'|。

如果 |b|<|b'|，找到最大的 i 使得 b_i=b'_i（假设 b_0=b'_0=0）。

• 如果 i=|b|， i+1\leq a[b_{i+1}]，与 F(a) 的定义矛盾（它也可以找到 a[b_{i+1}]）；
• 此时按照定义，一定有 b_{i+1}<b'_{i+1}（b' 是不遵循 “找接下来第一个” 策略的），即可推出 b_{i+2}<b'_{i+2}（同理，b_{i+2} 是从更靠前的位置开始找，并且遵循找最靠前的策略）...... 最终可推出 b_{|b|}<b'_{|b|}，而 b'_{|b|}<b'_{|b|+1}，与 F(a) 的定义矛盾（它也可以找到 a[b_{i+1}]）．

综上，现在问题转化为：对于所有的 Q，和它能找出的 b，均有 b_{2023}\leq 20240．

二，性质剖析

引理一：对于 p:p_1,p_2,\cdots,p_{km} 和 q:q_1,q_2,\cdots,q_{km}，若此时它们一路找到位置 km，已经找到的数分别为 P 和 Q 且 P\leq Q，此时 p,q 之后的 (m-k) 组排列还未确定，那么 p 不劣于 q ．

因为之后 km+1\sim n 这些数，q 能构造出的来的，p 也能构造出来，由于 P\geq Q，那么对于 q 之后找到的那些数，p 也能找到，所以 p 不劣于 q。

推论：仅需要构造使得在每一组中找到的数尽可能少，在 10 组之后确保至多找到 2023。

性质：假设从第 k 组开始找时，已经找到了 1,2,\cdots,t-1，需要从 t 开始找，那么在第 k 组排列中，<t 的部分怎么排顺序对答案是没有影响的，所以可以忽略掉 <t 的数，并将所有数都减去 (t-1)，那么问题就变成了要在长为 m-t 的序列中从 1 开始找数。

现在我们成功的将问题从多组长为 m 的排列简化为仅需考虑一组长为 m 的排列。

三，调整

结论：倒序排列一定能使得找到的数最小。

调整法：

• 对于任意的排列 q，找到两个位置 q_x<q_y,x<y，将 q_x 和 q_y 的值交换，答案不会变得更大，即对于交换后的排列 q' 有 F(q')\leq F(q)；
• 而对于任意的排列 q 均能在有限次数的交换之后调整为倒序的排列 p:m,m-1,\cdots,1，由此即可证明 F(p)\leq F(q)．

现在我们反过来证明由 q' 交换一组 q'_x>q'_y,x<y 得到 q，得到的答案不会变得更小：

这里我们称一个 b 对于 q 合法，意思为从 q 按某顺序找出来的位置所构成的数列，也就是需要仅满足 b_{i}<q[b_{i}]．

• 对于 q' 的任意的可能的合法的 b'：
  • 若 b' 中不存在 x,y：那么在 q 中这个 b' 也是合法的（仍满足 b_i<q[b_i]）；
  • 若 b' 中同时存在 x,y：那么有 x<y\leq q'_y<q'_x，在 q 中就是 x<y\leq q_x<q_y，所以 x<q_x,y<q_y，那么在 q 中这个 b' 依然是合法的；
  • 若 b' 中仅存在 y：那么 y<q_y'<q'_x=q_y，即 y<q_y，那么在 q 中这个 b' 依然是合法的；
  • 若 b' 中仅存在 x：b' 中挑选出在 [x,y] 之间的位置是 b'_l<b'_{l+1}<b'_{l+2}<\cdots <b'_{r}，其中 b'_l=x,b'_r<y．在 b' 中 b'_r 之后插入一个 y 并且删掉 b'_l=x，得到一个对于 q 而言合法的 b，且长度不变。(1)

对于 (1) 合法性的说明：

综上，对于 q' 中任意可能的合法的 b'，在 q 中总存在一个 b 使得 |b|=|b'| 并且 b 对于 q 合法，而 q 还可能存在其它更大的 b，所以 F(q')\leq F(q)，至此，结论得到证明。

我猜最后这段有笔误并且有地方没说清楚但我懒得改了

本来想写完给学校老师看的但是写完发现是臭婆娘的裹脚于是就拉到这里来了

因为你没兴趣看长篇大论一路划到了这里，所以看到了我放了一则趣事，趣事是 anecdote。

用了下生成函数的思想构造了一个遗传多选题，给生物老师看想让她扔到作业里面（因为隔壁班有人改编的生物题上作业卷了）

生物老师面对未知的生成函数力量奋战无果，大败，遂言要拿走搞进什么论文里（估计是老师评选还是啥要写的文章）