|
|
問題
1から8までの8個の異なる数を、2つの集まりAとBに振り分けるとき、
「どんな3つの数を選んでも互いの差は全て異なる」
ようにするためにはどのように振り分けたら良いか？
答え
{ 1, 2, 5, 6 } { 3, 4, 7, 8 }
{ 1, 3, 6, 8 } { 2, 4, 5, 7 }
{ 1, 4, 5, 8 } { 2, 3, 6, 7 }
以上、3通り
（終わり）
類題
タイルが1列に並んでいる。それらに2種類の色を塗っていく。
ただし、等間隔に3つ以上同じ色を塗らないようにする。
何枚まで塗ることができるか。
答え
1種類では、2枚まで
2種類では、8枚まで
3種類では、26枚まで
4種類では、75枚まで ※ここから処理困難になる
：
：
（終わり）
参考サイト
ファン・デル・ヴェルデン数（Van der Waerden number）
http://oeis.org/A005346
参考サイト
お茶の時間
パズル＆クイズ
LET R=2 !r種類
LET K=3 !長さk
DIM A(8) !並び ※※※W(r,k)-1の値
LET A(1)=1 !※対称性
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(2,R,K,A)
PRINT C; "通り"
END
EXTERNAL SUB try(P,R,K,A())
FOR i=1 TO R
LET D=1 !間隔（公差）
DO
LET T=P
FOR J=1 TO K-1 !等間隔に3つ並ぶ（等差数列）かどうか確認する
LET T=T-D
IF T<1 THEN EXIT DO !これ以降は可能性なし
IF A(T)<>i THEN EXIT FOR
NEXT J
IF J>K-1 THEN EXIT DO !NGの場合
LET D=D+1 !次へ
LOOP
IF J<K THEN !題意を満たすなら
LET A(P)=i
IF P=UBOUND(A) THEN !すべて埋まったなら
LET C=C+1 !結果を表示する
MAT PRINT A;
FOR x=1 TO R !集合ごとに
PRINT " {";
LET FLG=0 !継続フラグ
FOR y=1 TO UBOUND(A)
IF A(y)=x THEN
IF FLG=1 THEN PRINT ","; !最初ならカンマはつけない
PRINT STR$(y);
LET FLG=1
END IF
NEXT y
PRINT "}";
NEXT x
PRINT
ELSE
CALL try(P+1,R,K,A) !次へ
END IF
END IF
NEXT i
END SUB
実行結果
1 1 2 2 1 1 2 2
{1,2,5,6} {3,4,7,8}
1 2 1 2 2 1 2 1
{1,3,6,8} {2,4,5,7}
1 2 2 1 1 2 2 1
{1,4,5,8} {2,3,6,7}
3 通り
|
|