如何从集合{1,2,…,12}中选取最多元素，满足任意三元素乘积非自然数立方？

步骤1：质因数分解与立方剩余向量映射 #

对于集合{1,2,…,12}中的每个元素，将其分解为无立方因子部分×立方数的形式，然后将无立方因子部分的质因数指数对3取模，得到一个向量（仅考虑2,3,5,7,11这几个质因数，因为更大的质因数在1-12中只出现一次）：

• 1,8 → 无立方因子部分为1 → 向量(0,0,0,0,0)
• 2 → 向量(1,0,0,0,0)
• 4 → 向量(2,0,0,0,0)
• 3 → 向量(0,1,0,0,0)
• 9 → 向量(0,2,0,0,0)
• 5 → 向量(0,0,1,0,0)
• 6 → 向量(1,1,0,0,0)
• 7 → 向量(0,0,0,1,0)
• 10 → 向量(1,0,1,0,0)
• 11 → 向量(0,0,0,0,1)
• 12 → 向量(2,1,0,0,0)

步骤2：识别冲突三元组 #

三个元素的乘积为立方数，等价于它们的向量相加模3等于零向量。据此找出所有冲突的三元组：

• {1,2,4}, {8,2,4}（向量和为(0,0,0,...)）
• {1,3,9}, {8,3,9}
• {4,6,9}
• {2,9,12}
• {3,6,12}

步骤3：筛选安全元素 #

观察发现，元素5,7,10,11的向量无法与其他两个元素的向量相加得到零向量（不存在对应的补向量），因此它们与任何两个元素的乘积都不会是立方数，这4个元素可以全部选入子集。

步骤4：最大化剩余元素的选择 #

剩余元素为{1,2,3,4,6,8,9,12}，需避开冲突三元组，同时选择最多元素：

• 优先选择向量为(0,0,0,...)的元素1和8（共2个），它们之间无冲突，且只要不与冲突三元组中的其他元素同时出现即可。
• 从{2,6,12}中选择全部3个元素：这三个元素的向量和为(1+1+2,1+0+1)=(4,2)≡(1,2)≠(0,0)，乘积2×6×12=144不是立方数，且它们与1、8的组合中，没有冲突三元组（缺少4、3、9等元素）。

此时选中的剩余元素为{1,2,6,8,12}（共5个），加上安全元素4个，总共有9个元素。

步骤5：验证最大性 #

尝试添加任何剩余元素（3,4,9）都会触发冲突：

• 添加3：子集包含{3,6,12}，乘积为216=6³，违反条件；
• 添加4：子集包含{1,2,4}，乘积为8=2³，违反条件；
• 添加9：子集包含{2,9,12}，乘积为216=6³，违反条件；

因此无法选出10个符合条件的元素，最大数量为9。

示例符合条件的最大子集 #

{1,2,5,6,7,8,10,11,12}

内容的提问来源于stack exchange，提问作者G. Amber