图结构中硬币“好分配”数量的求解问询

问题描述 #

在图1的每个顶点上都有一名学生，总共有 n = 60k 枚硬币分配给这些学生。硬币会按以下规则重新分配：

• 每个学生同时给每个邻居分相同数量的硬币。举个例子，中心顶点的学生要把自己硬币的五分之一分给每个邻居。

我们把满足以下两个条件的硬币分配叫做好分配：

1. 每个学生分给每个邻居的硬币数都是整数；
2. 所有学生完成分配后，每个人手里的硬币数和分配前完全一样。

想问问这样的“好分配”一共有多少种？

来源：这个问题是基于2012年AIME I的第7题改编的

我自己的尝试思路 #

我先简化了变量，没有给每个顶点单独设变量，而是按距离中心的层级来汇总：

• 用 a 表示中心顶点学生的硬币数；
• b 是距离中心1层的所有学生的硬币总数；
• c 是距离中心2层的所有学生的硬币总数；
• d 是距离中心3层的所有学生的硬币总数。

根据分配规则列了方程组：
$$a = b/3$$
$$b = a + c/2$$
$$c = (2/3)b + d/2$$
$$d = c/2 + d/2$$

解出来的结果是：c = 4a = d，b = 3a，而且 a = k。

我找到了一种很直观的分配方式：距离中心0、1、2、3层的每个学生分别拿 5k、3k、4k、4k 枚硬币，这个是符合“好分配”要求的。但现在我卡壳了——如果不给每个顶点单独设变量、不搞出一套复杂的方程组的话，我不知道怎么找其他可能的分配方式，也不确定到底有多少种这样的好分配。

备注：内容来源于stack exchange，提问作者user1127