【DDL热身活动】一个看起来很难很热门的高考数学题：24年新高考1卷19题解析
看到24年高考题的时候我真的很感兴趣，所以就想找时间做一做这道题...现在todo感觉有点多，但是什么都不太想做, 想拿这道题热热身（之后会赶赶现在的ddl），而且这道题也是我整张试卷中最感兴趣的题了。
下面尝试来做一下这道题：
- 设m为正整数，数列a_1,a_2,...,a_{4m+2}是公差不为0的等差数列。若从中删去两项a_i,a_j(i < j)以后，剩下的4m项平分为m组，每组的4个数都成等差数列，则称数列a_{4m+2}是(i,j)可分数列。
（1）写出所有i,j 1 \leq i < j \leq 6, 使数列a_1,a_2....a_6是(i,j)可分数列。（3分）
（2）当m \geq 3时，证明a_1, a_2,....,a_{4m+2}是(2,13)可分数列。（5分）
（3）从1,2,...4m+2中任取两个数i,j(i < j)，记数列a_1, a_2,....,a_{4m+2}是(i,j)可分数列的概率为P_m, 证明P_m > \frac{1}{8}.（9分）
解：
（1）观察可知，如果a_1,a_2,...a_n成等差数列，那么它们的下标1,2,...n也一定成等差数列，所以我们在之后的阐述中不妨设a_n = n, 在1,2,3,4,5,6中删去2个数使之成为(i,j)可分数列的方法不难找出:
(1,2),(1,6),(5,6).
（2）
我们不妨尝试m = 3的情况。当m = 3的时候，4m + 2 = 14，那么去掉2和13后，和1数值最靠近的数是3，和14数值最靠近的数是12。假设我们考虑能让公差最小的分组情况，那么有一个组一定包含1,3,5,7;另外有一个组一定包含8,10,12,14。剩下的4个数分别为4,6,9,11并不满足要求。
通过上述分组发现，包含1的组公差至少为2，包含14的组的公差至少为2。
如果包含14的组公差d = 3，包含1的组公差d = 2，那么两个组会包含一个重复的数5，不符合题意。
尝试两个组公差都等于3的情况，那么包含1的组应该是1,4,7,10; 包含14的组应该是14,11,8,5.剩下的一个组是3,6,9,12，这种情况是符合要求的，因此m = 3时原结论成立。
当m > 3时，将每增加的14之后的相邻的4个数分成1组即可满足题目要求，所以m > 3时原结论也成立。
（3）
（正常人能想到第2问估计就是极限了，这才是我们的主菜）
首先，在一个数列中选择2个数的种数是C(4m+2,2)，设f(m)为所有(i,j)可分数列的种数，那么P_m = f(m)/C(4m+2,2).
假设m = 3, 如果去掉的不是2和13，而是...
/............../
x x
1 4 7 10
3 6 9 12
5 8 11 14
我们可以按照其对应组的编号将其编码为14位四进制数:
[10213213213201]
其中具有相同位值的被分为相同的组
不难发现这个新构造序列的性质：
[00123123123123]
这种情况一定可分，说明i,j在序列边缘的时候可以“忽略”，那么如果'0'在最后两位肯定也可分。
[010?1??1?212?2]
[010?1??1??1??2]
[0101?1?1?2?2?2]
[0101?1?1??2??2]
这种情况的话是不可分的，因为发现第2位和其下一个相同位之间的间隔为1(d=2)和为2(d=3)的时候都没办法分
那么类似的由对称性，如果"0"处在最后一位和倒数第三位也不可分。
[0??0??????????]
[02?02??2?121?1]
[02?02??2??2??1]
我们可以发现如果包含第1组的公差一定是3，此时最后一组无论取d=2还是d=3都没法可分，所以这个也不行。
那么如果相差4呢？
[01210121??2???]
发现组"1"公差只能等于2,此时组"2"的公差只能等于"4"，超过了数列的上限，因此不可分。
如果相差5呢？
[01111022223333]
Yes!这个时候是一定可分的！
如果相差6及以上呢？
[01?1?101??????] 组1的d=2时，从第3位开始的组2没法定义.
[01??1?01?212?2] 组1的d=3时，从最后一组开始定义组2，那么组2只能有d=2,可惜仍然不能成组.
因此相差6也不行.
如果是相差7呢？
[0??????0??????]第2位和第14位不可能在同一组，所以一定在2组当中。从第2位开始的组d=2和d=3都不行，从第14位开始的组d=2和d=3都不行.
如果有一个组d=1
[011112?02??2??] 发现第2组仍然不可分.
回顾下我们之前的操作，我们是怎么尝试让剩余位可分的？
我们设计一个算法试试看:
def generate_arithmetic_sequence(n, d):
return [i * d for i in range(n)]
def is_arithmetic_sequence(seq):
if len(seq) < 2:
return True
diff = seq[1] - seq[0]
for i in range(1, len(seq)):
if seq[i] - seq[i-1] != diff:
return False
return True
def dfs(sequence, groups, m, index):
if index == len(sequence):
for group in groups:
if not is_arithmetic_sequence(group):
return False
return True
for i in range(m):
if len(groups[i]) < 4:
groups[i].append(sequence[index])
if dfs(sequence, groups, m, index + 1):
return True
groups[i].pop()
return False
def can_be_grouped(sequence, m):
groups = [[] for _ in range(m)]
return dfs(sequence, groups, m, 0)
def find_ij_combinations(sequence):
n = len(sequence)
results = []
for i in range(n):
for j in range(i + 1, n):
remaining_sequence = sequence[:i] + sequence[i + 1:j] + sequence[j + 1:]
if can_be_grouped(remaining_sequence, len(sequence) // 4 - 1):
results.append((i + 1, j + 1)) # Convert to 1-based indexing
return results
# Part (1)
m = 1
d = 1
sequence = generate_arithmetic_sequence(4 * m + 2, d)
ij_combinations = find_ij_combinations(sequence)
print("Part (1):", ij_combinations)
# Part (2)
m = 3
sequence = generate_arithmetic_sequence(4 * m + 2, d)
remaining_sequence = sequence[:1] + sequence[2:12] + sequence[13:]
print("Part (2):", can_be_grouped(remaining_sequence, m))
# Part (3)
from math import comb
def count_valid_combinations(sequence, m):
n = len(sequence)
count = 0
for i in range(n):
for j in range(i + 1, n):
remaining_sequence = sequence[:i] + sequence[i + 1:j] + sequence[j + 1:]
if can_be_grouped(remaining_sequence, m):
count += 1
result1.append((i + 1,j + 1))
else:
result2.append((i + 1,j + 1))
return count,result1,result2
m = int(input("input m:"))
sequence = generate_arithmetic_sequence(4 * m + 2, d)
total_combinations = comb(4 * m + 2, 2)
result1 = []
result2 = []
valid_combinations,result1,result2 = count_valid_combinations(sequence, m)
P_m = valid_combinations / total_combinations
print("Part (3): P_m =", P_m, ">", 1 / 8, ":", P_m > 1 / 8)
print(f"Can be parted:{result1};\n\nCannot be parted:{result2}")
我们可以考虑一下m <= 3时的所有情况:
当m = 1时:
Can be parted:[(1, 2), (1, 6), (5, 6)];
Cannot be parted:[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6)]
这个可以看成是一个基础情况，如果只有6个相邻的数没有分组，那么从中找到符合条件的1个组，当且仅当它们相邻。
当m = 2时:
Can be parted:[(1, 2), (1, 6), (1, 10), (2, 9), (5, 6), (5, 10), (9, 10)];
Cannot be parted:[(1, 3), (1, 4), (1, 5), (1, 7), (1, 8), (1, 9), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 10), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9), (6, 10), (7, 8), (7, 9), (7, 10), (8, 9), (8, 10)]
可以看成是m = 1递推出来的情况，其中我们发现[(1,2),(1,6),(5,6)]是前6个数应用m = 1时的情况，[5,6],[5,10],[9,10]由于构造序列的对称性也加入了进去，本质上是后6个元素应用m = 1时的情况。唯一需要关注的是中间的这个 (1, 10)和(2,9)，这个是怎么分的呢？
?0??????0?
我们可以发现:
1012121202
真的可以分组诶~！
如果是(1,10)呢？
0111122220
这个毋庸置疑了
观察发现，我们可以把m=2的情况分成两个m=1的子问题的情况，根据0的不同位置，我们可以分成两种不同的情况。
（1）当两个0在同一个子序列中，那么其中有一个数列有4项，另一个数列有6项，此时第一个数列一定可分，第二个数列可分有3种情况，由于对称性，第一个数列有6项，第二个有4项，也有3种情况。
（2）当两个0不在同一个子序列中，那么每个子序列都有5项且有1个0。此时两个子序列必须要借助彼此才能可分。
观察其中唯一能成立的序列，发现这个序列中的0是对称分布的:
10121,21202
而且每个子序列中，分到同一组的元素个数不同:
在唯一可分的序列中:
组1: 3 1
组2: 1 3
因此我们可以推知f(2) = 2 * f(1)（情况1考虑对称） - 1（重复的部分） + 2（情况II） = 7种.
类似的，我们可以把m=3的情况分成m=1和m=2两个子问题.
（1）两个0在同一子序列中，在第一个子序列中，那么就是6+8，有3种情况；在第二个子序列中，那么就是4+10，有7种情况（假设我们已知f(2)）。这里不需要考虑对称性，因为f(2)的情况之前已经全都考虑到了.
[(1,2),(1,6),(5,6)] + [(5,6),(5,10),(9,10),(9,14),(13,14),(5,14),(6,13)].
但也可以拆成m=2+m=1两个子问题
[(1,2),(1,6),(5,6),(5,10),(9,10),(1,10),(2,9)] + [(9,10),(9,14),(13,14)].
重复的部分:
[(1,2),(1,6),(5,6),(5,10),(9,10),(9,14),(13,14)]
在同一种情况出现两次的情况:
[(5,6),(9,10)]（说明它们既可以看成包含在第一个子序列中，也可以看成包含在第二个子序列中）
考虑到它们重复的次数，可以把重复部分写成一个多重集合：
[(1,2),(1,6),(5,6),(5,6),(5,10),(9,10),(9,10),(9,14),(13,14)]
没有重复的部分
[(1,10),(2,9),(5,14),(6,13)]
如果它们在不同侧:
[(1,14),(2,13)]
f(3) = 2 * (f(1) + f(2))（1+2和2+1两种情况） - 3 * f(1)（减去上边重复计算的部分） + 2（在两侧对称的时候，固定的2种情况） = 2 * 10 - 3 * 3 + 2 = 13.
我们也可以将其变成一个合并问题，假设m = 3时，我们首先将子序列分成3个小部分，先计算序列内两个数可能被去掉的情况，共有3 * f(1) - 2种，也就是上面的[(1,2),(1,6),(5,6),(5,10),(9,10),(9,14),(13,14)]，每两个相邻但不同的部分合并时，种数就增加2（即对称的部分）[(1,10),(2,9),(5,14),(6,13)]，这里前两个元素是第1部分和第2部分合并产生的，后两个元素是第2部分和第3部分合并产生的；同理，123这三个部分合并也会产生2个新的元素，也就是[(1,14),(2,13)]。
基础情况是 m * f(1) - (m - 1).
比如说m = 4: 4 * 3 - 3 = 9种.
1 2 3 4
可以有3种合并方式:12,23,34 -> 增加6种
然后是123,234 -> 增加4种
最后是1234 -> 增加2种
因此m = 4的时候应该是9 + 6 + 4 + 2 = 21种?试试看！
反正m = 1,2,3的时候似乎都成立
m = 1:1 * 3 - 0 = 3
m = 2:2 * 3 - 1 + 2 = 7
m = 3:3 * 3 - 2 + 4 + 2 = 13
m = 4:4 * 3 - 3 + 6 + 4 + 2 = 21
m = k:k * f(1) - (k - 1) + k * (k - 1)
我们不能说这覆盖了所有情况，但至少是必要条件.
即f(k) > 3k + (k-1)^2. = k^2 + k + 1.
而所有的情况共有C(4k+2,2)种，这个情况有(4k+2)(4k+1)/2种
所以P_m = (k^2 + k + 1)/(8(k+1/2)(k+1/4)) = 1/8 * (k^2 + k + 1)/(k^2 + 3/4 * k + 1/8)
由于k > 0，所以k > 3/4k, 1 > 1/8，所以*(k^2 + k + 1)/(k^2 + 3/4 * k + 1/8) > 1,因此P_m > 1/8.
到这里已经结束了，但是还有没有别的情况呢？
以下思路来自B站up天使猫猫酱：
Extension Part
首先，在数列0,1,2,...4k+2当中，对4取模，余数为0和为3的数有k个，余数为1和为2的数有k+1个。无论公差是多少，我们可以发现，对每一组的序列取mod 4运算，可以发现余数为0和2的个数之差相差为4的倍数，而余数为1和3的个数之差也相差4的倍数。
如果要满足上面的性质，那么去掉的两个数一定是余数为1和余数为2的。
那么，如果去掉的数不相邻，考虑4k+2和4k+5的情况可以吗？
我们可以从m = 2开始看看情况:
??0??0?????
显然这种情况是不行的;
m = 3也是不行的
第一个4k+2~4k+5形式的特殊解是m = 6, i = 10, j = 13, 划分序列可以是这样的:
12324232103405351545666614
m = 6, i = 14, j = 17也同理。
利用同样的方法可以搜索出m = 7,i = 6,j = 9的时候也是可分的。
那么，在两边都有预留空间的情况下，所有情况的分组都找到啦！
如果只在一侧有预留空间怎么样呢？（比如i = 2, j = 5？ - 仍然是不可分的）
——可以建模为精确覆盖问题，有一族集合，从其中选出一些不交的集合，使得它们加起来等于我们想要的一个大集合。
其中一个改良的方案是采用DLX算法，可以找到m = 8时的特殊解（是一个非常巧妙的数据结构）
那么利用DLX算法可以实现对m = 8时数列划分的求解：
class Node:
def __init__(self, row=None, col=None):
self.left = self
self.right = self
self.up = self
self.down = self
self.column = col
self.row = row
class ColumnNode(Node):
def __init__(self, name):
super().__init__()
self.size = 0
self.name = name
class DancingLinks:
def __init__(self):
self.header = ColumnNode("header")
self.columns = {}
def add_column(self, name):
col = ColumnNode(name)
col.left = self.header.left
col.right = self.header
self.header.left.right = col
self.header.left = col
self.columns[name] = col
return col
def add_node(self, row, col):
node = Node(row, col)
node.up = col.up
node.down = col
col.up.down = node
col.up = node
col.size += 1
return node
def cover(self, col):
col.right.left = col.left
col.left.right = col.right
i = col.down
while i != col:
j = i.right
while j != i:
j.down.up = j.up
j.up.down = j.down
j.column.size -= 1
j = j.right
i = i.down
def uncover(self, col):
i = col.up
while i != col:
j = i.left
while j != i:
j.column.size += 1
j.down.up = j
j.up.down = j
j = j.left
i = i.up
col.right.left = col
col.left.right = col
def search(self, k, result, solutions):
if self.header.right == self.header:
solutions.append(result.copy())
return
col = self.header.right
for c in self.iterate_columns():
if c.size < col.size:
col = c
self.cover(col)
r = col.down
while r != col:
result.append(r.row)
j = r.right
while j != r:
self.cover(j.column)
j = j.right
self.search(k + 1, result, solutions)
result.pop()
j = r.left
while j != r:
self.uncover(j.column)
j = j.left
r = r.down
self.uncover(col)
def iterate_columns(self):
c = self.header.right
while c != self.header:
yield c
c = c.right
# 使用上述DLX类来建模和解决问题
def setup_dlx(m):
dlx = DancingLinks()
n = 4 * m + 2
sequence = list(range(n + 1))
# 添加列
for i in range(n + 1):
dlx.add_column(i)
# 添加行
for combo in combinations(sequence, 4):
valid = True
diff = combo[1] - combo[0]
for i in range(1, 4):
if combo[i] - combo[i - 1] != diff:
valid = False
break
if valid:
row_nodes = []
for num in combo:
row_nodes.append(dlx.add_node(combo, dlx.columns[num]))
return dlx
def solve_dlx(m):
dlx = setup_dlx(m)
solutions = []
dlx.search(0, [], solutions)
return solutions
# 测试m = 6
m = 6
solutions = solve_dlx(m)
print(f"Solved for m = {m}, Number of solutions: {len(solutions)}")
for solution in solutions:
print(solution)
用这一算法证明，m = 6时具有36 + 6 + 1 + 2 = 45种情况（其中有两种特殊情况）
也可以用这个方法找到m=8时，(2,5)形式的方案
1021031431432435466665277775888825
（因此这两种情况也是可分的！）
即4k+2和4k+5这种情况也是一定可分的！
最终答案采用了一种从全集相减的形式，即
f(m) = (m + 1)^2 - F(m).
F(m)表示(4k+2,4k+5)型不可分的部分
其中F(m) = m(m <= 5), F(6) = 6 - 2 = 4, F(7) = 7 - 2 * 2 + 1 - 2 = 2, F(m) = 0(m >= 8).
总结: m = 6开始(9,13)可分;m = 7开始(6,9)可分;m >= 8以后(2,5)可分!
那么这个被誉为高考巅峰之作的压轴题解析终于可以告一段落啦！如果想看后一部分原视频的话，可以跳转参考链接：https://b23.tv/5Gk85xu