下面是零音在第五届 AGMC 数学竞赛的二试部分的参赛解答。这是零音向主办方提交的答案，并非主办方给出的官方答案，零音的做法与官方答案有很大的不同，在部分题目的处理上似乎更加灵活（当然可能失了一部分严谨性），请读者带着谨慎的心态阅读，因为零音也不知道自己写的对不对。（

Problem 11

被 $63$ 绝对整除的最小正整数

一个正整数可以被 $63$ 绝对整除，等价于该正整数的任意排列可以被 $9$ 和 $7$ 整除。其中被 $9$ 整除仅取决于数位和，即所有数字的和都是 $9$ 的倍数；但被 $7$ 整除则依赖于排列。

考虑正整数 $m$ 可被 $7$ 绝对整除，即我们任意调换 $m$ 中的两个相邻的数位，得到的数应当依然能被 $7$ 整除。对于不相邻的数位，可以视为若干次相邻数位的连续调换。我们假设 $m$ 的一个排列 $\dots a b \dots$ 经过调换后变成了 $\dots b a \dots$，于是两个数的差为

$$
9 \times (a-b) \times 10^k
$$

须有

$$
9 \times (a-b) \times 10^k \equiv 0 \pmod{7}
$$

因为 $\gcd(9 \times 10^k, 7) = 1$，所以必然有 $a-b \equiv 0 \pmod{7}$。遍历 $a, b \in {1, 2, \dots, 9}$，从而只有 $a=b$ 或 ${a,b} = {1,8}, {2,9}$ 时条件满足。这就是说，$m$ 的所有数字除以 $7$ 的余数必须完全相同。

编写 C++ 脚本枚举得到

$$
\boxed{111888.}
$$

枚举最小正整数的 C++ 脚本

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
49
#include <bits/stdc++.h>
using namespace std;

int main() {
    auto repunit_mod7 = 0; // repunit(k) mod 7
    for (int k = 1; ; ++k) {
        repunit_mod7 = (repunit_mod7 * 10 + 1) % 7;
        string best = "";

        for (int r = 0; r <= 6; ++r) {
            // For absolute divisibility by 7, all digits must be congruent mod 7.
            // r=0 => only digit 7 (0 not allowed). r=1,2 have two digits: r and r+7.
            int d1 = (r == 0) ? 7 : r;
            int d2 = (r == 1 || r == 2) ? r + 7 : -1;

            // Condition for divisibility by 7: either r==0 or repunit(k)≡0 (mod 7).
            if (r != 0 && repunit_mod7 != 0) continue;

            string candidate;
            if (d2 == -1) {
                if ((d1 * k) % 9 != 0) continue;
                candidate.assign(k, char('0' + d1));
            } else {
                // sum = k*d1 + 7*t, where t is count of d2
                int mod = (k * d1) % 9;
                int t0 = (-4 * mod) % 9; // inverse of 7 mod 9 is 4
                if (t0 < 0) t0 += 9;
                int t = -1;
                for (int x = t0; x <= k; x += 9) {
                    t = x;
                    break;
                }
                if (t == -1) continue;
                candidate.assign(k - t, char('0' + d1));
                candidate.append(t, char('0' + d2));
            }

            if (best.empty() || candidate.size() < best.size() ||
                (candidate.size() == best.size() && candidate < best)) {
                best = candidate;
            }
        }

        if (!best.empty()) {
            cout << best << "\n";
            return 0;
        }
    }
}

可绝对整除的正整数 $n$

假设存在符合条件的，不含 $0$ 的正整数 $m$，使得 $m$ 的任意排列都是 $n$ 的倍数。显然 $n$ 不能是 $10$ 的倍数，因为 $m$ 的各数位不能为 $0$。下面我们对 $m$ 分两种情况考虑。

必要性

首先考虑这样的 $m$，它有至少 2 个相异的数字 $x$ 和 $y$。我们构造这样两个排列 $N_1 = \dots x y$、$N_2 = \dots y x$，即它们仅在最后两个数位上对调，从而因为有 $n \mid N_1$ 和 $n \mid N_2$，则必须有 $n$ 整除它们的差：

$$
N_1 - N_2 = 10x + y - (10y + x) = 9(x-y)
$$

因为 $x, y \in {1, \dots, 9}$，从而 $x-y$ 的绝对值最大为 $8$。注意到 $n$ 不能为 $16$ 和 $25$ 的倍数，因为 $9(x-y)$ 不可能被 $16$ 和 $25$ 整除。

其次考虑 $m = d d d \dots d = 111 \dots 1 \times d$，其中 $1 \le d \le 9$，即 $m$ 是一个纯数字数。因为 $111 \dots 1$ 本身是奇数，它不含有素因子 $2$ 和 $5$，从而 $m$ 中的素因子 $2$ 和 $5$，如果有，都应当是 $d$ 贡献的。最大情况下，$d = 8 = 2^3$ 和 $d = 5 = 5^1$，从而 $m$ 中的素因子 $2$ 和 $5$ 亦不能整除 $16$ 和 $25$。

综上我们证明了，符合条件的 $n$ 不能是 $10, 16, 25$ 的倍数。从而我们证明了必要性。

充分性

仅考虑纯数字数的 $m$。下面我们证明：所有不是 $10, 16, 25$ 倍数的 $n$ 都存在被它整除的不含 $0$ 的纯数字数 $m$。

设 $n = 2^a \cdot 5^b \cdot w$ 其中 $\gcd(w, 10) = 1$。由于 $n$ 不是 $10$ 的倍数，从而 $a, b$ 不能同时 $> 0$。由必要性，又有 $a \le 3$ 和 $b \le 1$。

由 Euler 定理，因为 $\gcd(9w, 10) = 1$ 从而必存在 $k = \varphi(9w)$ 使得

$$
10^k \equiv 1 \pmod{9w} \Rightarrow w \mid \frac{10^k - 1}{9}
$$

而 $\frac{10^k - 1}{9} = 111 \dots 1$（含 $k$ 个 $1$）。

  • 倘若 $n$ 含有 $5$，此时 $a = 0, b \le 1$，则 $n = 5w$ 或 $n = w$。选取 $d = 5$ 从而 $m = 5 \times 111 \dots 1$，从而 $w \mid 111 \dots 1$，又因 $5 \mid 5$，从而 $n \mid m$。
  • 倘若 $n$ 不含 $5$，此时 $b = 0, a \le 3$，所以 $n = 2^a \cdot w$。选取 $d = 2^a$，由 $a \le 3$ 保证了 $d \in {1, 2, 4, 8}$ 在 $1 \sim 9$ 内。设 $m = 2^a \times 111 \dots 1$，此时 $w \mid 111 \dots 1$ 和 $2^a \mid d$，从而 $n \mid m$。

这些纯数字数的所有排列均相同，从而若它们被 $n$ 整除，则它们被 $n$ 绝对整除。从而我们证明了充分性。

所有不被 $10, 16, 25$ 中任何一个数整除的正整数 $n$ 均符合条件。

Problem 13

确定期望的最小值

设 $U = X - Y, V = Y - Z, W = Z - X$，则 $U + V + W = 0$。从而

$$
\mathbb{E}(U^2 + V^2 + W^2) = \mathbb{E}[(X-Y)^2 + (Y-Z)^2 + (Z-X)^2] = 2\mathbb{E}[X^2 + Y^2 + Z^2] - 2\mathbb{E}[XY + YZ + ZX].
$$

又 $\mathbb{V}[X] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 = 1$ 且 $\mathbb{E}[X] = 0$，应用于 $X, Y, Z$ 即得

$$
\mathbb{E}[X^2] = \mathbb{E}[Y^2] = \mathbb{E}[Z^2] = 1.
$$

又因为交叉项的期望均为 $0$，从而

$$
\mathbb{E}[U^2 + V^2 + W^2] = 2(1+1+1) - 0 = 6.
$$

从而我们要求 $\mathbb{E}(U^{2n} + V^{2n} + W^{2n})$ 的最小值，当 $\mathbb{E}[U^2 + V^2 + W^2] = 6$ 时。这即在条件 $u + v + w = 0$ 且 $u^2 + v^2 + w^2 = Q$（固定）下考察 $u^{2n} + v^{2n} + w^{2n}$（$n \ge 1$）的最小值。略去证明过程，有 $u^{2n} + v^{2n} + w^{2n} \ge \frac{Q^n}{2^{n-1}}$。从而

$$
\mathbb{E}[U^{2n} + V^{2n} + W^{2n}] \ge 2(\mathbb{E}[Q/2])^n = 2 \cdot 3^n.
$$

分析期望的最大值

该期望应当是存在上限但可以任意大的。

设定 $X, Y, Z$ 之间相互独立且同分布。为了使 $(X - Y)^{2n}$ 变得非常大，我们可以让 $X, Y, Z$ 有很小的概率取一个极大的正值，以很大的概率取一个较小的负值。这即，设常数 $p \in (0, 1)$ 是一个非常小的概率，令 $X$ 以概率 $p$ 取正值 $M$，以概率 $1 - p$ 取负值 $-a$，并保证有期望符合题意

$$
\mathbb{E}[X] = pM - (1-p)a = 0 \Rightarrow a = \frac{pM}{1-p}
$$

对于方差，由于期望为 $0$，即要求 $\mathbb{E}[X^2] = 1$，从而

$$
\mathbb{E}[X^2] = pM^2 + (1-p) a^2 = 1
$$

将 $a$ 代入上式，化简得

$$
\frac{pM^2}{1-p} = 1
$$

从而有

$$
M = \sqrt{\frac{1-p}{p}}, \quad -a = -\sqrt{\frac{p}{1-p}}.
$$

对 $X, Y, Z$ 的处理类似。由于它们的期望均为 $0$，从而交叉乘积期望也为 $0$，待求的目标期望是

$$
\mathbb{E}_{\text{obj}} = \mathbb{E}[(X - Y)^{2n} + (Y - Z)^{2n} + (Z - X)^{2n}].
$$

在 $\mathbb{E}_{\text{obj}}$ 中仅保留情况 $(X - Y)^{2n}$ 以放缩其下界，具体地，令

$$
\begin{aligned}
\mathbb{E}[(X-Y)^{2n}] &\ge \mathbb{P}(X = M, Y = -a) \cdot (M - (-a))^{2n} \\
&= p(1-p)(M+a)^{2n} > p(1-p)M^{2n} \\
&= p(1-p)\left(\frac{1-p}{p}\right)^n \\
&= p^{1-n}(1-p)^{n+1}.
\end{aligned}
$$

当 $n \ge 2$ 时 $p^{1-n} = \frac{1}{p^{n-1}}$，而 $p \to 0^+$ 时 $(1 - p)^{n + 1} \to 1$ 且 $\frac{1}{p^{n-1}} \to +\infty$，从而 $\mathbb{E}[\dots]$ 可以变得无限大。（$n = 1$ 时，目标期望趋于 $6$，这是因为方差固定条件。）

综上

$$
\boxed{\mathbb{E}[\dots] \in [2 \cdot 3^n, +\infty).}
$$

Problem 14

下界

给出下界的构造：对方格表中的任意格子 $(x, y)$，当且仅当 $x + y \equiv 0 \pmod{3}$ 时填入 V，否则填入 E。

取某一个不位于边缘的 V，以它为中心，横着和竖着读均可以读到 EEVEE。位于 $(x, y)$ 的 V 的主对角线方向上，与它相距为 $\pm 1$ 和 $\pm 2$ 的坐标的和与它本身的坐标的和（即 $x + y$）的差为 $\pm 2$ 或 $\pm 4$，模 $3$ 均不为 $0$，从而这些格子上均为 E，又构成了 EEVEE。副对角线上因为格子的坐标和为常量，对应字母均为 V，故无法形成 EEVEE。

在这样的构造下，V 的分布密度为 $1/3$，即总共有 $\frac{n^2}{3} + O(n)$ 个 V。每一个 V 可以读出 $3$ 个单词，从而整个方格表中可以读出的单词数量为

$$
3 \times \left(\frac{1}{3} n^2 + O(n)\right) = n^2 + O(n).
$$

因此，单词数量的下界

$$
\boxed{f(x) \ge n^2 + O(n).}
$$

上界

我们要证明单词不可能过度密集。将 $n \times n$ 的整个方格划分为若干个互不重叠的 $3 \times 3$ 的小正方形区块，这样的区块大约有 $\frac{n^2}{9}$ 个。取其中一个区块 $A$，考察中心点（这里指 EEVEE 中的 V）落在区块 $A$ 内部的全体 EEVEE 单词的最大数量 $W(A)$。

考虑 $3 \times 3$ 的区域 $A$。

  • 假使这个单词是横向排布的。若单词的中心落在了区域 $A$ 中某行的某个格子中，为了确保单词 EEVEE 的排布，V 的左右两侧两个格子都必须是 E。也就是说，在 $A$ 的某一行中，只要该行存在一个 V，那么该行剩下的格子就必须是 E。
  • 纵向排布的单词同理。
  • $A$ 内部的对角线（主对角线和副对角线）各有 $5$ 条，长度分别为 $1, 2, 3, 2, 1$，任何一条对角线位于区域 $A$ 内部的距离的最大值为 $2$。从而，对于一个斜向排布的单词，若单词的中心落在了区域 $A$，则其对应方向的整条对角线的位于区域内部的格子也不能出现 V。

从而：位于区域 $A$ 内的横向排布的单词的数量，应当小于等于区域 $A$ 内部的恰好只有 1 个 V 的行的数量；位于区域 $A$ 内的纵向排布的单词的数量，应当小于等于区域 $A$ 内部的恰好只有 1 个 V 的列的数量；位于区域 $A$ 内的某个方向上的所有对角线上的单词的数量，应当小于等于区域 $A$ 内该方向上恰好只有 1 个 V 的对角线的数量。

现在，我们假设在区域 $A$ 的 9 个格子中填入了 $v$ 个 V。由上可知：中心落在区域 $A$ 内的 EEVEE 单词的数量，小于等于区域 $A$ 内部的恰好只有 1 个 V 的行的数量、区域 $A$ 内部的恰好只有 1 个 V 的列的数量、和区域 $A$ 内两个对角线方向上恰好只有 1 个 V 的对角线的数量的总和。对 $v$ 进行枚举：首先考虑 $v = 0$ 和 $v = 1$ 和 $v = 2$ 的情况，前两者分别最多激活 $0$ 和 $4$ 条线，后者通过非对角的错位排布可以激活 $8$ 条线。但对于 $v \ge 3$ 的情况，因为可能会导致单词的重叠，手动统计是痛苦的。我们编写 C++ 脚本，可以统计得到最大的可能性是 11 个单词。但不可能在每一个这样的区域都取到最大值。所以……

（艹怎么证不出来了 o(TヘTo) 已放弃。好难啊）

赛后补充：这是什么个事呢，如果零音枚举完发现最大的可能性是 $10$ 个单词，那题目的上界就非常松了，零音的上界直接可以够到得分最高档。只可惜最大值是 $11$，当然，我们所有人都知道不可能每一个区域都取到这个最大值，但这是无法说明的，零音这个上界只能得 45 分中的至多 15 分，哭泣中😭

枚举单词数量最大可能性的 C++ 脚本

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

int main() {
    int best = 0;
    int bestMask = 0;

    auto check = [&](int mask) {
        int a[3][3] = {};
        for (int i = 0; i < 9; ++i) {
            a[i/3][i%3] = (mask >> i) & 1;
        }

        set<int> counted;

        int cnt = 0;
        for (int r = 0; r < 3; ++r) for (int c = 0; c < 3; ++c) {
            if (!a[r][c]) continue;

            int sumRow = a[r][0] + a[r][1] + a[r][2];
            if (sumRow == 1 && !counted.count(r)) {
                counted.insert(r);
                cnt++;
            }

            int sumCol = a[0][c] + a[1][c] + a[2][c];
            if (sumCol == 1 && !counted.count(3 + c)) {
                counted.insert(3 + c);
                cnt++;
            }

            int d = r - c; // -2..2
            int sumDiag = 0;
            for (int i = 0; i < 3; ++i) {
                int j = i - d;
                if (0 <= j && j < 3) sumDiag += a[i][j];
            }
            int idDiag = 6 + (d + 2); // 6..10
            if (sumDiag == 1 && !counted.count(idDiag)) {
                counted.insert(idDiag);
                cnt++;
            }

            int s = r + c; // 0..4
            int sumAnti = 0;
            for (int i = 0; i < 3; ++i) {
                int j = s - i;
                if (0 <= j && j < 3) sumAnti += a[i][j];
            }
            int idAnti = 11 + s; // 11..15
            if (sumAnti == 1 && !counted.count(idAnti)) {
                counted.insert(idAnti);
                cnt++;
            }
        }

        return cnt;
    };

    for (int mask = 0; mask < (1<<9); ++mask) {
        int val = check(mask);
        if (val > best) {
            best = val;
            bestMask = mask;
        }
    }

    cout << best << "\n";
    // Print one example achieving the maximum
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            int bit = (bestMask >> (r * 3 + c)) & 1;
            cout << bit << (c == 2 ? '\n' : ' ');
        }
    }
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~