Question

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

（1）求的最小值；

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

Answer 1

【答案】（1）168544；（2）見(jiàn)解析

【解析】

顯然，每個(gè)圖案由的點(diǎn)的分組方法唯一確定.

（1）設(shè)，由分組，，…，得到，其中為第組的點(diǎn)構(gòu)成的集合，，2，…，83.

令，則有，且.

下證當(dāng)時(shí)，有.

事實(shí)上，若存在，使得，不妨設(shè)，則作的點(diǎn)的分組，，…，（為第組的點(diǎn)構(gòu)成的集合，），使得

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

.

而

.

∵.

∴.

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

∵，

∴.

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

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

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

綜上可知，結(jié)論成立.