2024年新高考一卷压轴题。
数学解
这道题颇有线性Dp的思想，通过构造递推式求解。
对于无论是case 2还是case 3，S(m-1) 都不是解的所有情况，因为我们只是特殊地选取了一种分法，所以最后递推式一定要取 ”$\geq$“ 。
解答中提到case 1恰好只有 2 种选法，没有给出证明，但是是经过代码验证的，大概率是正确的。（当然不影响以下证明的完备性，因为取 ”$\geq$“ ）
代码分析
接下来，让我们用代码跑一跑S(m)实际值的结果。（dfs暴搜，效率比较低，跑到 m=13 ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
bool dfs(vector<int>& v, int m) {
int flag = 0;
for (int k = 1; k <= 4 * m + 2; k++) {
if (v[k]) {
flag = k;
break;
}
}
if (!flag) return 1;
for (int delta = 1; flag + 3 * delta <= 4 * m + 2; delta++) {
if (v[flag] & v[flag + delta] & v[flag + 2 * delta] & v[flag + 3 * delta]) {
v[flag] = v[flag + delta] = v[flag + 2 * delta] = v[flag + 3 * delta] = 0;
if (dfs(v, m)) return 1;
v[flag] = v[flag + delta] = v[flag + 2 * delta] = v[flag + 3 * delta] = 1;
}
}
return 0;
}
bool check(int i, int j, int m) {
vector<int> v(4 * m + 3, 1);
v[i] = v[j] = 0;
return dfs(v, m);
}
void solve(int m) {
int cnt = 0;
for (int i = 1; i <= 4 * m + 1; i++) {
for (int j = i + 1; j <= 4 * m + 2; j++) {
cnt += check(i, j, m);
}
}
printf("m = %2d : cnt = %3d, m^2 + m + 1 = %3d, m^2 + 2m + 1 = %3d\n",
m, cnt, m * m + m + 1, m * m + 2 * m + 1);
}
int main() {
for (int m = 2; m <= 13; m++) {
solve(m);
}
return 0;
}
|
对每一个 $m$ 同时计算了 $m^2+m+1$ 和 $(m+1)^2$ 的值。因为发现 cnt 似乎总在这两个值之间，而且在$m\geq9$之后cnt就稳定在$(m+1)^2$了，也许是S(m)的上确界。运行结果：
UPD 6/11
有幸看到了一个视频，验证了我先前根据程序结果作出的猜想。视频链接：命题人可能都没找到的构造！？24高考数学压轴精确结果。
得出的最终结果是：$S(m) = (m+1)^2-F(m)$
其中$F(m) = m(m\leq5)$，$F(6)=4$，$F(7)=2$，$F(m)=0(m\geq8)$