教授在每個人腦門上貼了一張紙條
每個人的紙條上都寫了一個正整數，且某兩個數的和等于第三個數
每個人可以看見另兩個數，但看不見自己的
每個人自己的數只能是另兩數之和或者之差，所以每個人都有2種可能。
每個人都無法確認自己到底是哪一個，也不能從其他人那里得到更多信息。
再回到問題描述，“每個人的紙條上都寫了一個正整數”，這就是最關鍵的信息，它暗示了很多其它信息。如果有一個人計算出來的數不是正整數，那這一種情況就被排除。
這個數不可能是負數，因為2個不相等的數，一定是用大的減去小的，那剩下的非正整數就只能是0，也就是有2個數相等的情況。
如果2個數相等，抽象一下，不就是一個最簡單的1+1=2的問題嗎？
如果小A看到的場景剛好是這樣，(2,y,1)，那y不是1，肯定就是3了呀。
第2輪第1人能猜出的情況如下：
正確的解有5個：(3,1,4)，(1,3,4)，(2,7,9)，(4,5,9)，(3,5,8)。
對應的另外兩個數分別是：(108,36)，(36,108)，(32,112)，(64,80)，(54,90)。
3個數要先約掉公約數，等比例的情況都是相同的
任意情況，都會在有限輪次之后被某個人猜出來
最先猜出來的人，一定是數字最大的人
所有邏輯推理的根基都是1+1=2 每多一輪，解的個數以斐波那契數列遞增
struct Node {
int x, y, z, level;
};
Node f[10000];
int last1, last2, tail;
void init() {
f[0] = Node{2, 1, 1, 1};
f[1] = Node{1, 2, 1, 2};
f[2] = Node{2, 3, 1, 2};
f[3] = Node{1, 1, 2, 3};
f[4] = Node{2, 1, 3, 3};
f[5] = Node{1, 2, 3, 3};
f[6] = Node{2, 3, 5, 3};
last1 = 3;
last2 = 1;
tail = 7;
}
// 第round輪，第person人，猜出自己是x
void solve(int round, int person, int x) {
int n = (round - 2) * 3 + person, total;
for (int i = 0; i < n; ++i) {
total = tail;
for (int j = last2; j < total; ++j) {
if (i % 3 == 0) {
f[tail++] = Node{f[j].y + f[j].z, f[j].y, f[j].z, 4 + i};
} else if (i % 3 == 1) {
f[tail++] = Node{f[j].x, f[j].x + f[j].z, f[j].z, 4 + i};
} else {
f[tail++] = Node{f[j].x, f[j].y, f[j].x + f[j].y, 4 + i};
}
}
last2 = last1;
last1 = total;
}
for (int i = last1; i < tail; ++i) {
int temp = 0;
switch (person) {
case 1:
temp = f[i].x;
break;
case 2:
temp = f[i].y;
break;
case 3:
temp = f[i].z;
break;
}
if (x % temp == 0) {
int s = x / f[i].z;
printf("(%d, %d, %d), level=%d\n", f[i].x * s, f[i].y * s, f[i].z * s, f[i].level);
}
}
}
int main() {
init();
solve(2, 3, 144);
return 0;
}
(108, 36, 144), level=6
(36, 108, 144), level=6
(32, 112, 144), level=6
(64, 80, 144), level=6
(54, 90, 144), level=6
文章首發平臺：微信公眾號【小K算法】。
