离心机的配平问题 - 知乎
k个试管能否配平一个n孔的离心机 (0≤k≤n0\le k\le n )？
这是一个非常有趣的问题，YouTube上的Numberphile频道有介绍（以下链接为B站搬运）。
Matt Baker的博客也详细介绍了这个问题，并给出了数学上的描述。
这个问题有个现在已被证明的解答：
当且仅当k和n-k均可写成n的质因数的线性组合且系数非负时，k个试管可以配平一个n孔的离心机。
- *
2022-04-21更新此部分：这个问题只是由配平离心机引出的，请不要只局限在离心机上。事实上这个问题的解的证明也是non-trivial的。而这个解可以应用到其它地方也不一定。比如潜艇螺旋桨叶片一般都是单数甚至质数来减少共振和噪音。如果有些叶片损坏了，我们是不是可以选择性地主动放弃若干叶片来恢复平衡（质数叶片就不行了）。再比如轰炸机旋转弹药架，我们是不是可以按照一定次序来投弹来最大程度保持弹药架的平衡。。。当然我不是专业人士，只是觉得这个问题很有趣就随便想了想。
- *
举例来说，一个6孔的离心机可以用2个、3个、4个或6个试管来配平：
6的质因数是{2，3}：
- 2个试管(k=2)：2=2, (6-2)=2+2
- 3个试管(k=2)：3=3, (6-3)=3
- 4个试管(k=4)：4=2+2, (6-4)=2
- 5个试管(k=5)不可行：虽然5=2+3，但是(6-5)不能写作2和3的线性组合（非负系数）
- 6个试管(k=6)：6=2+2+2, (6-6)=2x0+3x0
6孔的例子非常简单，直观地我们也能想出配平方式。12孔的例子可能会更有意思，尤其是k=5，k=7这两个情况，如下图。12的质因数也为{2，3}。
- k=5时，5=2+3，(12-5)=2+2+3：我们可以组合一个2管的配平方式和一个3管的配平方式。
- k=7时，7=2+2+3，(12-7)=2+3：我们可以组合两个2管的配平方式和一个3管的配平方式。
另外，由于5+7=12，当我们配平了k=5后，k=7不过就是反转所有孔而已：原来空置的现在放试管，原来放试管的位置现在空置。
再举个例子，26孔的离心机。质因数为{2，13}
商用的离心机孔数n因此最好是2和3的公倍数，这样_几乎_任意数量的试管都可以配平（除去k=1和k=n-1。不讨论带自动配平功能的机器哈）。最坏的情况下n是个质数，这样的离心机除了放满试管没法配平。
- *
2022-04-20更新此部分：关于这个问题的数学描述。考虑n=8的情况。我们可以在复平面的单位圆上均匀地放置8个点，记为 zk,k∈{0,1,...,7}z^k, k\in \{0,1,...,7\} ，其中 z=e2πniz=e^{\frac{2\pi}{n}i} 为unity的8次方根。问题就转化为能否找出若干个 zkz^k 使得它们的和为零（质心在圆心）。
- *
编程求解这个问题我在我的博客里讨论了。
Centrifuge Problemmingze-gao.com/posts/centrifuge-problem/
生成以上图片的Python代码如下：
from functools import lru_cache
import numpy as np
import matplotlib.pyplot as plt
@lru_cache(maxsize=None)
def prime_divisors(n):
"""Return list of n's prime divisors"""
primes = []
p = 2
while p**2 <= n:
if n % p == 0:
primes.append(p)
n //= p
else:
p += 1 if p % 2 == 0 else 2
if n > 1:
primes.append(n)
return primes
def centrifuge(n):
"""Return a list of which the k-th element represents if k tubes can balance the n-hole centrifuge"""
F = [True] + [False] * n
for p in prime_divisors(n):
for i in range(p, n + 1):
F[i] = F[i] or F[i - p]
return [F[k] and F[n - k] for k in range(n + 1)]
def factorize(k: int, nums: list) -> list:
"""Given k, return the list of numbers from the given numbers which add up to k.
The given numbers are guaranteed to be able to generate k via a linear combination.
Examples:
>>> factorize(5, [2, 3])
[2, 3]
>>> factorize(6, [2, 3])
[2, 2, 2]
>>> factorize(7, [2, 3])
[2, 2, 3]
"""
def _factorize(k, nums, res: list):
for p in nums:
if k % p == 0:
res.extend([p] * (k // p))
return True
else:
for i in range(1, k // p):
if _factorize(k - p * i, [n for n in nums if n != p], res):
res.extend([p] * i)
return True
return False
res = []
_factorize(k, nums, res)
return res
@lru_cache(maxsize=None)
def centrifuge_k(n, k):
"""Given (n, k) and that k balances a n-hole centrifuge, find the positions of k tubes"""
if n == k:
return [True] * n
factors = factorize(k, prime_divisors(n))
pos = [False] * n
def c(factors: list, pos: list) -> bool:
if sum(pos) == k:
return True
if not factors:
return False
p = factors.pop(0)
pos_wanted = [n // p * i for i in range(p)]
for offset in range(n):
pos_rotated = [(i + offset) % n for i in pos_wanted]
# the intended positions of the p tubes are all available
if not any(pos[i] for i in pos_rotated):
# claim the positions
for i in pos_rotated:
pos[i] = True
if not c(factors, pos):
# unclaim the positions
for i in pos_rotated:
pos[i] = False
else:
return True
# all rotated positions failed, add p back to factors to place later
factors.append(p)
c(factors, pos)
return pos
def plot_centrifuge(n, figname="centrifuge.svg"):
ncols = max(int(n**0.5), 1) # minimum 1 column
nrows = n // ncols if n % ncols == 0 else n // ncols + 1
height = 3 if nrows == ncols else 2
width = 2
fig, axes = plt.subplots(nrows, ncols, figsize=(height * nrows, width * ncols))
z = np.exp(2 * np.pi * 1j / n)
theta = np.linspace(0, 2 * np.pi, 20)
radius = 1 / (ncols + nrows)
a = radius * np.cos(theta)
b = radius * np.sin(theta)
cent = centrifuge(n)
for nr in range(nrows):
for nc in range(ncols):
k = nr * ncols + nc + 1
axis = axes[nr, nc] if ncols > 1 else axes[nr]
if k > n:
axis.axis("off")
continue
# draw the n-holes
for i in [z**i for i in range(n)]:
axis.plot(a + i.real, b + i.imag, color="b" if cent[k] else "gray")
# draw the k tubes
if cent[k]:
if k > n // 2:
pos = [not b for b in centrifuge_k(n, n - k)]
else:
pos = centrifuge_k(n, k)
for i, ok in enumerate(pos):
i = z**i
if ok:
axis.fill(a + i.real, b + i.imag, color="r")
axis.set_aspect(1)
axis.set(xticklabels=[], yticklabels=[])
axis.set(xlabel=None)
axis.set_ylabel(f"k={k}", rotation=0, labelpad=10)
axis.tick_params(bottom=False, left=False)
fig.suptitle(f"$k$ Test Tubes to Balance a {n}-Hole Centrifuge")
fig.text(0.1, 0.05, "Red dot represents the position of test tubes.")
plt.savefig(figname)
plt.close(fig)
if __name__ == "__main__":
for n in range(6, 51):
print(f"Balancing {n}-hole centrifuge...")
plot_centrifuge(n, f"{n}-hole-centrifuge.png")下载 6≤n≤506\le n\le 50 时候的配平方式（图片）和以上代码（链接为zip文件）：
https://mingze-gao.com/posts/centrifuge-problem/centrifuge-problem.zip
- *
2022-04-20更新：以下为生成复平面示意图的代码：
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams.update({
"text.usetex": True,
"font.family": "sans-serif",
"font.sans-serif": ["Helvetica"]})
n = 8
z = np.exp(2 * np.pi * 1j / n)
theta = np.linspace(0, 2 * np.pi, 20)
radius = 0.03
a = radius * np.cos(theta)
b = radius * np.sin(theta)
fig = plt.figure(figsize=(9,9))
axis = fig.add_subplot()
for idx, i in enumerate([z**i for i in range(n)]):
axis.fill(a + i.real, b + i.imag, color="b")
if idx == 1:
plt.annotate(r"""$z=e^{\frac{2\pi}{n}i}$""",(i.real, i.imag), (i.real, i.imag+0.1), color="black", fontsize=20)
else:
plt.annotate(f"$z^{idx}$",(i.real, i.imag), (i.real, i.imag+0.1), color="black", fontsize=20)
plt.plot(np.linspace(-1.5,1.5,10), np.linspace(0,0,10), color='black')
plt.plot(np.linspace(0,0,10), np.linspace(-1.5,1.5,10), color='black')
plt.annotate(f"$real$",(1.5,0), fontsize=16, color='black')
plt.annotate(f"$imag$",(0,1.5), fontsize=16, color='black')
plt.annotate(f"$n=8$",(-1.5,1.5), fontsize=22, color='black')
plt.annotate(f"$z$ is the $n$-th root of unity",(-1.4,1.2), fontsize=15, color='black')
axis.set_aspect(1)
axis.axis('off')原网址: 访问
创建于: 2023-06-01 14:55:17
目录: default
标签: 无
未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到
- 上一篇： 打造学习型IPad——考研/持续学习 - 知乎
- 下一篇： 普及离心技术知识及分类 - 知乎
最新评论