数学

2022 TACA 数学二 T3

一个正方形内有 $2022$ 个点，且无三点共线(包括正方形顶点)，在这些点(包括正方形顶点) 中连一些仅相交于端点的线段，将正方形划分为若干个三角形，求所连线段的个数.

SOL 设正方形被分为$x$ 个三角形，所连线段数为 $y$，则

$$\{\begin{array}{l}2022+4+(x+1)-(y+4)=2\\ \\ 3x+4=2(y+4)\end{array}$$$$\text{解得}\{\begin{array}{l}x=4046\\ y=6067\end{array},\text{故线段数为}6067.$$

P.S. 欧拉图论公式：一个连通的可平面化图，设点数为 $n$，边数为 $e$，面或者区域的数量为 $f$, 则有

$$f+n-e=2$$

2022 TACA 数学二 T10

设 $A$ 是一个 $10\times 10$ 的方格表，元素全为 $1$，将某行或某列的元素全部反号称为一次操作， 若经过若干次操作后有 $n$ 个元素为 $-1$，称 $n$ 为“好数”，求“好数”共有几个.

SOL 记初值状态对应的元素全为 $1$ 的 $10$ 阶矩阵 $A$， 则可以用初等矩阵表示所有的操作：

记 $J_i(i=1,2,\cdots ,10)$ 表示第 $i$ 行对角线元素为 $-1$， 其余对角线元素均为 $1$ 的对角矩阵， 则对第 i 行操作相当于左乘 $J_i$ ， 对第 $j$ 列操作相当于右乘 $J_j$ .

于是有限次操作之后的表格对应的矩阵可表示为 $LAR$， 其中 $L,R$ 可表示为一系列 $J_i(i=1,2,\cdots ,10)$ 的乘积.

易知所有可能的 $L,R$ 即为对角线元素为 $\pm 1$ 的全部对角矩阵， 且 $L,R$ 的选择是互相独立的， 故有限次操作后可得到的矩阵即为所有可能的 $LAR$.

注意到最终的数表的元素只有 $1$ 和 $-1$， 于是 $-1$ 的个数与表中元素总和一一对应，于是只需考虑 $x(LAR)x^{\prime }$ 的可能取值即可， 其中 $x=(1,1,1,1,1,1,1,1,1,1)$.

注意到 $R{x}^{\prime }$ 和 $xL$ 的元素也只有 $1$ 和 $-1$， 其元素和取值构成的集合为 $M=0,\pm 2,\pm 4,\pm 6,\pm 8,\pm 10$ , 而 $x(LAR)x^{\prime }$ 即为 $R{x}^{\prime }$ 元素之和与 $xL$ 元素之和之积， 所以 $x(LAR)x^{\prime }$ 的所有可能取值即为

$$\begin{array}{rl}T& =\{ab|a,b\in M\}\\ & =\{0,\pm 4,\pm 8,\pm 12,\pm 16,\pm 20,\pm 24,\pm 32,\pm 40,\pm 36,\pm 48,\pm 60,\pm 64,\pm 80,\pm 100\}\end{array}$$

故 $|T|=29$.

Ebert's version and Hamming codes of Hat Pazzle

有 $n$ 个人组队挑战，每个人有白色或黑色帽子，只能看到别人的，要猜自己的颜色

每个人进行选择：猜白，猜黑，不猜

同时猜测，也就是说不能依赖别人的选择来猜

如果至少一个人猜了，而且猜的人都对，他们获胜

给他们指定策略，使得获胜概率最大（$2^n$ 种可能中获胜的最多）

SOL 神秘论文

把情况当作点, 两个点之间有边当且仅当它们之间的二进制只相差 $1$ 位, 当 $n=2^k-1$ 时, 可以找出 $\frac{2^n}{n+1}$ 个二进制下 $1$ 的位置下标异或和为 $0$ 的点, 我们指定它们为输状态, 可以推出和这些点直接相连的点都可以获胜, 所以获胜的概率为 $2^n-\frac{2^n}{n+1}$.

然后考虑有 $q$ 种颜色, $n$ 不一定为 $2^k-1$ 的情况, 此时没有完美策略， n 趋于无穷时正确率能趋于

$$P_L\le \frac{(q-1)\log n+1}{n}+(1-q^{-1}{)}^n$$

证明见论文

无标号竞赛图计数

求有 $x$ 个点的无标号竞赛图数

SOL A000568

下面介绍 $x=5$ 的解法

设 $\mathcal{A}$ 为顶点集 $\{1,2,\dots ,5\}$ 上的有标号竞赛图集合。我们知道 $$|\mathcal{A}|=2^{\binom{5}{2}}=1024$$ 因为每条边可以独立任意选择自己的方向。对称群 $S_5$ 通过置换顶点编号来对 $\mathcal{A}$ 进行作用。

Burnside 引理 给出了群作用下同构类的计数公式。然而，要使用它，我们需要找到一种计算每个$\alpha \in S_5$下"固定"的竞赛图$T$的数量的方法。

• 如果$\alpha (T)=T$，则称$\alpha$是$T$的一个自同构。（或者我们可以说$\alpha$固定了$T$。）这就是我们对"固定"的理解。

因此，为了使用 Burnside引理，对于每个$\alpha \in S_5$，我们需要找到集合 $F_{\alpha }:=\{T\in \mathcal{A}:\alpha (T)=T\}$ 的大小，它给出了同构类（非同构竞赛图）的计数公式为：$\frac{1}{|S_5|}\sum _{\alpha \in S_5}|F_{\alpha }|.$

通过观察我们发现$|F_{\alpha }|$只与$\alpha$的循环结构有关，这使得计算变得容易得多。

可能的循环结构有：

$(1,1,1,1,1)$

$(2,1,1,1)$

$(2,2,1)$

$(3,1,1)$

$(3,2)$

$(4,1)$

$(5)$

对于每个循环结构，例如(2,2,1)，我们可以选择一个代表，例如$\beta =(12)(34)(5)$，并找到$|F_{\beta }|$。

Trick 具有 $a_k$ 个大小为 $k$ 的循环结构的排列的数量:

$$\frac{n!}{\prod a_k!k^{a_k}}$$

因此，求出 $|F_{(1)(2)(3)(4)(5)}|=1024$，$|F_{(123)(4)(5)}|$和$|F_{(12345)}|$的值即可。

Mathematica 代码:

permcount[v_] := 
  Module[{m = 1, s = 0, k = 0, t}, 
   For[i = 1, i <= Length[v], i++, t = v[[i]]; 
    k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; 
   s!/m];
edges[v_] := 
  Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + 
   Sum[Quotient[v[[i]], 2], {i, 1, Length[v]}];
oddp[v_] := (For[i = 1, i <= Length[v], i++, 
    If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1);
a[n_] := 
  a[n] = (s = 0; 
    Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]], {p, 
      IntegerPartitions[n]}]; s/n!);
Table[Print["a(", n, ") = ", a[n]];