塗り分け

 投稿者:山中和義  投稿日:2014年 8月 5日(火)18時55分31秒
  問題
3×3の各マス目に、赤か青の何れかの色を無作為に塗るとする。
(1) 何通りの塗り分け方ができるか。
(2) この中で、どこかの2×2の正方形には同色で塗られるものが存在する。それは何通りあるか。

 ■■□  □□□  ■■■ など
 ■■□  ■■□  ■■■
 □□□  ■■□  □□□

答え  (1) 2^9=512通り  (2) 190通り

考察
n種類の色を塗るとする。色を0,1,2,3,…,n-1と番号付ける。
中央は0とする。順にA,B,C,Dと塗っていく。
その過程で、E,F,G,Hの箇所で同色になる場合の数を求める。
  EAH
  B0D
  FCG
他の色1,2,3,…,n-1も同数である。
(終り)


!その1 シミュレーション

LET N=2 !色数

LET S=0 !場合の数

FOR A=0 TO N-1
   FOR B=0 TO N-1
      FOR E=0 TO N-1
         IF A+B+E=0 THEN !この箇所で同色になる場合
            LET S=S+N^3*N^2 !残りF,G,Hは、何色でもよい。また、C,Dも何色でもよい。
         ELSE

            FOR C=0 TO N-1
               FOR F=0 TO N-1
                  IF B+C+F=0 THEN
                     LET S=S+N^2*N^1 !残りG,Hは、何色でもよい。また、Dも何色でもよい。
                  ELSE

                     FOR D=0 TO N-1
                        FOR G=0 TO N-1
                           IF C+D+G=0 THEN
                              LET S=S+N^1 !残りHは、何色でもよい。
                           ELSE
                              IF D+A=0 THEN LET S=S+1 !D+A+H=0の1通り
                              !!FOR H=0 TO N-1
                              !!   IF D+A+H=0 THEN
                              !!      LET S=S+N^0
                              !!   ELSE
                              !!   END IF
                              !!NEXT H
                           END IF
                        NEXT G
                     NEXT D

                  END IF
               NEXT F
            NEXT C

         END IF
      NEXT E
   NEXT B
NEXT A

PRINT S; N*S; "通り"


!その2

!中央でも角でもない4マスについて、
!中央マスとの色の関係であり得るパターンは、次の6通りである。
!これより、中央の色を固定して、2×2の同色がないものは、
LET T=0
!(1) 4マスすべてが中央マスと異なる色
LET T=T+(N-1)^4*N^4 !  1*( (N-1)^4 * N^4 )
!(2) 4マスのうち1マスだけ中央マスと同じ色
LET T=T+4*(N-1)^3*N^4 !  4*( 1*(N-1)^3 * N^4 )
!(3) 4マスのうち向い合う2マスだけ中央マスと同じ色
LET T=T+2*(N-1)^2*N^4 !  2*( 1^2*(N-1)^2 * N^4 )
!(4) 4マスのうち隣接する2マスだけ中央マスと同じ色
LET T=T+4*(N-1)^3*N^3 !  4*( 1^2*(N-1)^2 * (N-1)*N^3 )
!(5) 4マスのうち3マスが中央マスと同じ色
LET T=T+4*(N-1)^3*N^2 !  4*( 1^3*(N-1) * (N-1)^2*N^2 )
!(6) 4マス全部が中央マスと同じ色
LET T=T+(N-1)^4 !  1*( 1^4 * (N-1)^4 )
!他の色でも同数となる。
!よって、求める場合の数は、余事象なので、
LET S=N^9-N*T

PRINT S; "通り"

END

 

戻る