趣题

2023-08-12 | 题解 | 阅读 | 1.1k 字 | 4 分钟

文章目录

1. 数学

数学

2022 TACA 数学二 T3

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

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

$解得故线段数为$

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

2022 TACA 数学二 T10

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

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

记表示第行对角线元素为，其余对角线元素均为的对角矩阵，则对第 i 行操作相当于左乘，对第列操作相当于右乘 .

于是有限次操作之后的表格对应的矩阵可表示为，其中可表示为一系列的乘积.

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

注意到最终的数表的元素只有和，于是的个数与表中元素总和一一对应，于是只需考虑的可能取值即可，其中 .

注意到和的元素也只有和，其元素和取值构成的集合为 , 而即为元素之和与元素之和之积，所以的所有可能取值即为

故 .

Ebert's version and Hamming codes of Hat Pazzle

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

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

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

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

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

SOL 神秘论文

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

然后考虑有种颜色, 不一定为的情况, 此时没有完美策略， n 趋于无穷时正确率能趋于证明见论文

无标号竞赛图计数

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

SOL A000568

下面介绍的解法

设为顶点集上的有标号竞赛图集合。我们知道因为每条边可以独立任意选择自己的方向。对称群通过置换顶点编号来对进行作用。

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

如果，则称是的一个自同构。（或者我们可以说固定了。）这就是我们对"固定"的理解。

因此，为了使用 Burnside引理，对于每个，我们需要找到集合的大小，它给出了同构类（非同构竞赛图）的计数公式为：

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

可能的循环结构有：

对于每个循环结构，例如(2,2,1)，我们可以选择一个代表，例如，并找到。

Trick 具有个大小为的循环结构的排列的数量: 因此，求出，和的值即可。

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]];