Question

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

Answer 1

【答案】

【解析】

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

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

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

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

.

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

注意到，2017為素?cái)?shù).

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

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

對(duì)于頂點(diǎn)和 ，當(dāng) 時(shí)，

若，

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

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

由2017為素?cái)?shù)，知染色方式唯一確定.

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

對(duì)于任意三個(gè)頂點(diǎn)、、，若、與 、之間的連邊同色，則、之間的連邊也必為此種顏色.

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

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

則，.

故 .

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

綜上，滿足條件的.