面白い問題おしえて～な十三問目

面白い問題おしえて～ ..

371:１３２人目の素数さん
07/12/31 23:31:38
自作問題投下。

無限に広がる平面があって、同じ大きさの正方形のマス目に区切られているとする(碁盤の目のように)。
これらのマスのうち有限個のマスを黒で塗りつぶす。n個のマスを塗りつぶしたとする。
塗りつぶしたマス目に、1からnまでの自然数を1つずつ書き込む(順番はどうでもよい)。
各項が0と1のみから成る、n次の正方行列Aを次のように定める。

・Aの(i,j)成分＝(iが書いてある黒マスとjが書いてある黒マスが隣接しているとき) 1 , (それ以外のとき) 0

ただし、i＝jのときは、iが書いてある黒マスとjが書いてある黒マスは隣接していると
定義しておく(従って、Aの対角成分は全て1である)。このAについて、次が成り立つ
ことを示せ。

・A^(n^2)の成分が全て正ならば、塗りつぶしたn個の黒マスから成る図形は連結である。
・A^(n^2)の成分のうち0のものがあるならば、塗りつぶしたn個の黒マスから成る図形は連結でない。

次ページ

続きを表示

1を表示