整数的最大乘积分拆

hbghlyj

原文:
blog.tanyakhovanova.com/2009/03/my-most-memorable-math-mistake/

我已经忘记了我参加的数学奥林匹克的所有问题，除了一个。这个问题让我损失了一分，结果我没有得到满分。这是 1976 年 IMO 的第 4 题：

        将$1976$表示为一些正整数之和，求这些数的乘积的最大值。

解法：考虑 $1976$ 的一个分拆。如果分拆中有一个 $≥5$ 的整数 $x$，则将其替换为 $x-2$ 和 $2$ 会增大乘积，因为 $2(x-2) > x$。将分拆中的 $4$ 替换为 $2$ 和 $2$ 不会改变乘积。如果分拆中有 $1$，则将它加到任何其他数 $x$ 会增大乘积：将 $1$ 和 $x$ 替换为 $x+1$。

这意味着大于 $1$ 的整数的最大乘积分拆仅含$2$和$3$。如果分拆中有$3$个$2$，我们可以用两个$3$替换它们，因为$3^2>2^3$。这意味着我们的分拆仅含$2$和$3$，并且$2$的数量不多于三个。

我当年在计算 1976 模 3 的余数时犯了一个基本的算术错误，而失去了一分。

这个问题可推广到任何正整数 $n$，我们得到OEIS中的序列 A000792。如果我们向 $n$ 的分拆添加一些结构，就会出现这个序列的其他有趣的定义：

我们可以根据 $n$ 的任何分拆将 $n$ 元集划分为不交的子集，并将每个子集中的元素写成循环，这些循环生成的子群是一个阿贝尔子群，这个子群的阶就是循环的阶的乘积。因此，$a(n)$ 是对称群 $S_n$ 中最大的阿贝尔子群的阶。

我们也可以根据 $n$ 的任何分拆将 $n$ 个顶点划分为不交的组，再连接每对属于不同组的顶点，形成一个图。如果我们从每组中取一个顶点，那么导出的子图就是一个团。我们可以看到它是一个极大团，因为属于同一组的两个顶点不相连接，从而我们不能再添加任何顶点。这种大小的团的数量是每组中顶点数量的乘积。于是 $a(n)$ 是具有 $n$ 个顶点的图中的极大团数的最大值。

尽管我无法回到 1976 年来纠正我的愚蠢错误，但我喜欢这个问题和相应的序列。

isee

机翻？

hbghlyj

$6$的最大乘积分拆为$3+3$，$3×3=9$。 $\updownarrow$ $\updownarrow$ $S_6$的最大的阿贝尔子群的阶为9，例如$⟨ (123), (456) ⟩$。 $\updownarrow$ $\updownarrow$ $6$阶图中的极大团数的最大值为$9$。

上图: $K_{3,3}$(将6个顶点分成3+3的组并连接每对属于不同组的顶点)

hbghlyj

顶点集$C$被称为无向图 $G=(V,E)$ 的团，如果$C$是顶点集$V$的子集($C⊆V$)，而且任意两个$C$中的顶点都有边连接。等价的说法是，由$C$诱导的子图是完全图 （有时也用“团”来指这样的子图）。

极大团是指增加任一顶点都不再符合团定义的团，也就是说，极大团不能被任何一个更大的团所包含。

hbghlyj

isee 发表于 2022-6-5 17:07
机翻？

差不多...捋得通顺了