淡白鸽羽 发布于
因为计算量太大。
比如R(6,6)，上界是4^6=4096。
简单来说，只要作出4096个点，然后各点之间两两作线段，就能满足Ramsey条件。——但这题问的是“最少几个点”。
所以就要从4096减下去，比如4095（穷举法肯定只能一个个来嘛）。
那么，4095个点，一共有几条线段？答案是C(4095,2)=8,382,465。
这八百万条线段，分别涂成红蓝色，一共有多少种涂法？（当然这里可以用对称性简化。）
虽然，只要找出“4095的某一种涂法满足Ramsey条件”，就可以开始计算下一种情况（4094），但别忘了，题目问的是“至少”。
——也即，我们迟早必须遍历某个确定点数的每一种可能性，得出“是的，该情况下的所有涂法均无法满足Ramsey条件”这一结论，才能说“我们找到最小值了！”（+1就行）。
就结果看，就算从宇宙大爆炸开始计算4095，调动人类现有的全部算力，一直算到今天为止，恐怕连4000都算不到。