19743：正n角形のすべての辺と対角線を共有点を持つどの2線分も異なる色であるように塗るためには最低何色必要？

花壇って...時とともに移ろう絵画の描かれたるキャンバスなり♪

問題19743(友人問)

正n角形のすべての辺と対角線を、共有点をもつどの2つの線分も

異なる色であるように、色を塗りたい。最低何色必要か。

解答

・わたしの...

例えば...6角形

1点目からは、1,2,3,4,5

2点目は、1以外で、2345-4532

3点目は、2,4以外で、345-153

4点目は、3,5,1以外で、45-24

5点目は、5,2,3,4以外で、5-1 しか残らないが、1点目には1があるので、

第６番目が必要...

so...6色は必要...

頂点(1)からの直線はn-1種類

(2)からは、n-2種類で入れ替えればn-2点と結べる

(3)...n-3で入れ替えてn-3を結ぶ

...

(n-2)...n-1-(n-2)=1で残り2点のうち(n-1)1点と入れ替えられないので結べない

so...n-1+1=n種類必要

でいいかいなぁ ^^

・鍵コメT様からのエレガントな解法 Orz～☆

結論は正しいと思いますが，理由は読み取れませんでした．

「ある頂点Aから出るn-1本の辺や対角線」と
「Aの両隣りの頂点を結ぶ線分(n=3のときは辺，それ以外のときは対角線)」
の合計n本は，どの2本も共有点を持つから，すべて違う色にする必要がある．
よって，n色は必要である．

すべての辺，対角線は，上記のn本のいずれかに平行だから，
平行なものは同じ色にすることにより，n色で実際に塗り分け可能である．

以上より，結論はn色．

既視感があったので検索したところ，問題10857(https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=10857&sk=0)でした．

*正多角形内のすべての直線は、上記のものですべてであとは平行のものだけって事実には今更ながらになりますけど...考えたこともなかったので...感無量 ^^♪