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

【問題】

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

【問題１】

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

【問題２】

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

【問題１】のある塗り方M^Kに対して

P_i∈C_k かつ P_j∈C_kならばq(i,j)=0
P_i∈C_k かつ P_j∈C_k´かつk≠k´ならばq(i,j)=1
q(i,i)=0

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

【問題３】

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

Co(MK,MK´) =

A´+cB´ A + cB

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

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

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

とします。
もちろんq´(i,j)とは行列Q(M^K´)のi行j列の成分です。

またcは定数で

１ K-1

とします。

Ps.

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

　解答用紙はこちらです。

　◆図形問題へもどる

　数学の部屋へもどる