Question

【題目】給定平面上的點集，中任三點均不共線。將中所有的點任意分成83組，使得每組至少有3個點，且每點恰好屬于一組，然后將在同一組的任兩點用一條線段相連，不在同一組的兩點不連線段，這樣得到一個圖案。不同的分組方式得到不同的圖案。將圖案中所含的以中的點為頂點的三角形的個數記為。

（1）求的最小值；

（2）設是使的一個圖案，若將中的線段（指以的點為端點的線段）用4種顏色染色，每條線段恰好染一種顏色。證明存在一個染色方案，使染色后不含以的點為頂點的三邊顏色相同的三角形。

Answer 1

【答案】（1）168544；（2）見解析

【解析】

顯然，每個圖案由的點的分組方法唯一確定.

（1）設，由分組，，…，得到，其中為第組的點構成的集合，，2，…，83.

令，則有，且.

下證當時，有.

事實上，若存在，使得，不妨設，則作的點的分組，，…，（為第組的點構成的集合，），使得

這樣的分組顯然存在.于是，對于由分組，，…，得到的圖案，有

.

而

.

∵.

∴.

∴.這與的最小性相矛盾.

∵，

∴.

（2）設圖案由分組，，…，得到，這里表示第組的點構成的集合.由（1）不妨設，.下面給出的一個染色方法，使得用四種不同顏色染后不含三邊顏色相同的三角形.

我們將集合及所連線段構成的圖形稱為的第塊，記為，，2，…，83.對于，令，使得，.將每個子集中任兩點所連線段用圖（1）所示的方法去染，將不同子集與之間所連線段用途（2）所示的方法去染，圖中，，，分別代表四種不同的顏色，這樣染后的顯然不含三邊顏色相同的三角形.

對于，可用染的方法去染，至于的染法，可先加一點并將該點與原來的24點各連一條線段，染后按的染法染好后，再把加的一點及與該點所連的線段去掉，這樣染后的也不含三邊顏色相同的三角形.

綜上可知，結論成立.