Question

【題目】已知一個正多邊形的每條邊和對角線恰各染成2018種顏色之一，且所有邊及對角線不全同色.若正多邊形中不存在兩色三角形（即三角形的三邊恰被染成兩種顏色），則稱該多邊形的染色是“和諧的”.求最大的正整數(shù) ，使得存在一個和諧的染色正邊形.

Answer 1

【答案】

【解析】

先考慮和諧染色的正邊形的任意一個頂點 .可證明：對于每種顏色，由至多可以引出2016條該種顏色的邊.

否則，設(shè)與頂點相連的邊有相同的顏色（記為 ），于是，兩兩之間連邊的顏色均為.

令頂點為與相連的邊異于顏色的一個頂點（此頂點必然存在，否則，正邊形的所有邊均為顏色 ，與條件矛盾）.此時，頂點與的連邊兩兩不同色，且均不為顏色 ，這樣至少有2019種顏色，與條件矛盾.

從而，在和諧染色的正多邊形中，任一頂點引出的邊數(shù)為

.

再證明：存在和諧的染色正邊形.

注意到，2017為素數(shù).

故對任意整數(shù) ，及任意整數(shù)，均存在唯一的 ，使得.

用表示個頂點，其中，、，數(shù)字0,1，…，2017表示2018種顏色.

對于頂點和 ，當(dāng) 時，

若，

則將 與 之間的連邊染顏色；

若 ，則將與 之間的連邊染色顏色2017.

由2017為素數(shù)，知染色方式唯一確定.

下面證明：這樣的染色方式是和諧的.

對于任意三個頂點、、，若、與 、之間的連邊同色，則、之間的連邊也必為此種顏色.

事實上，若、與、之間的連邊同為顏色2017，則.故、 之間的連邊也為顏色2017.

若、 與、之間的連邊同為顏色，

則，.

故 .

從而，、 之間的連邊也為顏色 .

綜上，滿足條件的.