『最も遠い塗り分け方とは?』


【問題】

平面上にN個の点Pi(i=1〜N)があります。

【問題1】

これらをK色すべて使って塗り分ける方法は何通りありますか。
ただし、1点につき1色しか塗れないとし、K色はすべて異なるとします。

【問題2】

点Pi(i=1〜N)を相異なるK色の色Cj(j=1〜K)で塗ることを
Pi∈Cjと書くとします。

【問題1】のある塗り方MKに対して

Pi∈Ck かつ Pj∈Ckならばq(i,j)=0
Pi∈Ck かつ Pj∈Cかつk≠k´ならばq(i,j)=1
q(i,i)=0

を満たすq(i,j)をi行j列に持つ行列Q(MK)を考えます。
Kを固定するときこのような行列Q(MK)は何通り作れますか。

【問題3】

塗り方MKが与えられた時、
K色すべてを使う塗り方MのMKに対する一致度を

Co(MK,M) = A´+cB´
A + cB

と定義するならば、
Co(MK,M)が最小となるような塗り方Mとはどのような塗り方でしょうか?

またKを固定する時、
Co(MK,M)が最小となるようなMK,Mはどのような塗り方でしょうか。

ただし
A ・・・ i<jでかつq(i,j)=0となるような行列Q(MK)の成分の数
B ・・・ i<jでかつq(i,j)=1となるような行列Q(MK)の成分の数
A´・・・ i<jでかつq(i,j)=0、q´(i,j)=0となるような行列Q(M)の成分の数
B´・・・ i<jでかつq(i,j)=1、q´(i,j)=1となるような行列Q(M)の成分の数

とします。
もちろんq´(i,j)とは行列Q(M)のi行j列の成分です。
またcは定数で
K-1
とします。

Ps.

当たり前ですがA+B+N=N2が成立しています。
この問題はある分類が与えられた時にそれとは最も隔たりのある分類とはどのような分類でしょうかというものです。


 解答用紙はこちらです。


 ◆図形問題へもどる

 数学の部屋へもどる