|
投稿者：山中和義
投稿日：2014年 4月24日(木)09時58分14秒
|
|
|
|
問題
4024個の数 1,1,2,2,3,3,…,2012,2012 をうまく一列に並べると、
1≦n≦2012を満たす全ての自然数nに対して、
2つのnの間には(n-1)個の数があるようにすることが出来ることを示してください。
また、2013,2014,2015ではどうでしょうか。
考察
L(2,0)=00より、V(2,1)=11
L(2,3)=31213200より、それぞれの数を＋１する。
V(2,4)=42324311
L(2,4)=4131243200より、
V(2,5)=5242354311
参考サイト
クイズ＆パズル
問題
4022個の数 1,1,2,2,3,3,…,2011,2011 をうまく一列に並べると、
1≦n≦2011を満たす全ての自然数nに対して、
2つのnの間にはn個の数があるようにすることが出来ることを示してください。
答え
L(2,n)で、kが2以上の整数ならn=4k-1とn=4kのそれぞれの1つの解が示される。下記のプログラムを参照のこと。
（終り）
なので、
よって、V(2,n+1)も示される。
（終り）
類題
問題
1～8の数字の書かれたカードがある。
2枚ずつペアを作り、カードの数字の差がそれぞれ1,2,3,4になるような組合わせを求めよ。
問題
1～2nの数字の書かれたカードがある。
2枚ずつペアを作り、カードの数字の差がそれぞれ1～nになる組み合わせの総数を求めよ。
LET n=7
PRINT "N="; n
LET k=CEIL(n/4)
PRINT k !debug
IF k>1 AND MOD(n,4)=3 THEN !4k-1の場合
FOR i=4*k-4 TO 2*k STEP -2
PRINT i;
NEXT i
PRINT 4*k-2;
FOR i=2*k-3 TO 1 STEP -2
PRINT i;
NEXT i
PRINT 4*k-1;
FOR i=1 TO 2*k-3 STEP 2
PRINT i;
NEXT i
FOR i=2*k TO 4*k-4 STEP 2
PRINT i;
NEXT i
PRINT 2*k-1;
FOR i=4*k-3 TO 2*k+1 STEP -2
PRINT i;
NEXT i
PRINT 4*k-2;
FOR i=2*k-2 TO 2 STEP -2
PRINT i;
NEXT i
PRINT 2*k-1;
PRINT 4*k-1;
FOR i=2 TO 2*k-2 STEP 2
PRINT i;
NEXT i
FOR i=2*k+1 TO 4*k-3 STEP 2
PRINT i;
NEXT i
PRINT
ELSEIF k>1 AND MOD(n,4)=0 THEN !4kの場合
FOR i=4*k-2 TO 2*k STEP -2
PRINT i;
NEXT i
PRINT 4*k-1;
FOR i=2*k-3 TO 1 STEP -2
PRINT i;
NEXT i
PRINT 4*k;
FOR i=1 TO 2*k-3 STEP 2
PRINT i;
NEXT i
FOR i=2*k TO 4*k-2 STEP 2
PRINT i;
NEXT i
PRINT 2*k-1;
FOR i=4*k-3 TO 2*k+1 STEP -2
PRINT i;
NEXT i
PRINT 4*k-1;
FOR i=2*k-2 TO 2 STEP -2
PRINT i;
NEXT i
PRINT 2*k-1;
PRINT 4*k;
FOR i=2 TO 2*k-2 STEP 2
PRINT i;
NEXT i
FOR i=2*k+1 TO 4*k-3 STEP 2
PRINT i;
NEXT i
ELSE
PRINT "ありません。"
END IF
END
|
|
|
|
投稿者：山中和義
投稿日：2014年 4月24日(木)19時21分30秒
|
|
|
|
> No.3365[元記事へ]
> 問題
> 8個の数 1,1,2,2,3,3,…,4,4 をうまく一列に並べると、
> 1≦n≦4を満たす全ての自然数nに対して、
> 2つのnの間には(n-1)個の数があるようにすることが出来ることを示してください。
> 類題
> 1～8の数字の書かれたカードがある。
> 2枚ずつペアを作り、カードの数字の差がそれぞれ1,2,3,4になるような組合わせを求めよ。
参考サイト
お茶の時間
クイズ＆パズル
差が4の場合
xが空きとすると、4通りの位置に置ける
12345678←位置
4xxx4xxx
x4xxx4xx
xx4xxx4x
xxx4xxx4
より、
1から2nまでの数を扱うので、計算量O( (2n)!/(n-1)! )
LET t0=TIME
LET N=4
PUBLIC NUMERIC C !解の個数
LET C=0
DIM F(2*N) !数字1～2n
MAT F=ZER
CALL try(N, N,F) !差がn,…,3,2,1 ※N+1
IF C=0 THEN PRINT "解なし"
PRINT TIME-t0
END
EXTERNAL SUB try(P, N,F()) !バックトラック法で検索する
FOR i=1 TO 2*N-P !未使用の数字が候補である
IF F(i)=0 AND F(i+P)=0 THEN !組(i,i+p)は条件を満たす
LET F(i)=P !使用中 ※P-1
LET F(i+P)=P !※P-1
IF P=1 THEN !すべて並んだなら ※2
LET C=C+1
PRINT "No.";C
MAT PRINT F;
FOR s=1 TO N !差が1～nの順に
FOR x=1 TO 2*N
IF F(x)=s THEN
PRINT "(";x;",";x+s;") "; !ペア
EXIT FOR
END IF
NEXT x
NEXT s
PRINT
ELSE
CALL try(P-1, N,F) !次へ
END IF
LET F(i)=0 !元に戻す
LET F(i+P)=0
END IF
NEXT i
END SUB
実行結果
No. 1
4 2 3 2 4 3 1 1
( 7 , 8 ) ( 2 , 4 ) ( 3 , 6 ) ( 1 , 5 )
No. 2
4 1 1 3 4 2 3 2
( 2 , 3 ) ( 6 , 8 ) ( 4 , 7 ) ( 1 , 5 )
No. 3
3 4 2 3 2 4 1 1
( 7 , 8 ) ( 3 , 5 ) ( 1 , 4 ) ( 2 , 6 )
No. 4
1 1 4 2 3 2 4 3
( 1 , 2 ) ( 4 , 6 ) ( 5 , 8 ) ( 3 , 7 )
No. 5
2 3 2 4 3 1 1 4
( 6 , 7 ) ( 1 , 3 ) ( 2 , 5 ) ( 4 , 8 )
No. 6
1 1 3 4 2 3 2 4
( 1 , 2 ) ( 5 , 7 ) ( 3 , 6 ) ( 4 , 8 )
|
|
|
|
投稿者：山中和義
投稿日：2014年 4月24日(木)19時56分48秒
|
|
|
|
> No.3366[元記事へ]
問題 L(2,n)
2n個の数 1,1,2,2,3,3,…,n,n をうまく一列に並べると、
1≦k≦nを満たす全ての自然数kに対して、
2つのkの間にはk個の数があるようにすることが出来ることを示してください。
考察
n≡0, 3 mod 4 の場合に限る。
http://oeis.org/A176127
（終り）
問題 V(2,n)
2n個の数 1,1,2,2,3,3,…,n,n をうまく一列に並べると、
1≦k≦nを満たす全ての自然数kに対して、
2つのkの間には(k-1)個の数があるようにすることが出来ることを示してください。
考察
1からnまでのn個の数の並べ方は、n!通り。
この数字の並びを左から見て、その順番に左詰めに並べていく。
例 n=4で、並びが1234の場合
4×2=8個の枠○○○○○○○○について、
1は、１○１○○○○○
2は、１２１○２○○○
3は、１２１３２○○３
4は、並べられない
（終り）
計算量O( n!)
!L(m,n)、V(m,n)
!赤字部分の t+1 を t に置き換えると、V(m,n)となる。
LET t0=TIME
PUBLIC NUMERIC m,n, mn !L(m,n)
LET m=2
LET n=7
DIM a(n)
FOR i=1 TO n !最初の並び 1,2,3,…,n
LET a(i)=i
NEXT i
PUBLIC NUMERIC d(1000) !L(m,n)の並び
LET mn=m*n
MAT d=ZER(mn)
PUBLIC NUMERIC ANSWER_COUNT !場合の数
LET ANSWER_COUNT=0
CALL perm(a,1, 1)
IF ANSWER_COUNT=0 THEN PRINT "解なし"
PRINT "計算時間=";TIME-t0
END
EXTERNAL SUB perm(a(),k, P) !辞書順序ではなくn-順列（n!通り）を生成する
FOR i=k TO n
LET t=a(i) !a[i]とa[k]を入れ替える
LET W=P+(t+1) !左詰め位置pに数字tが埋められるか ※
FOR J=1 TO m-1 !1つ目は可能なので、2つ目以降を確認する
IF W>mn OR d(W)<>0 THEN EXIT FOR
LET W=W+(t+1) !※
NEXT J
IF J=m THEN !埋められるなら
FOR W=P+(t+1)*(m-1) TO P STEP -(t+1) !set it ※
LET d(W)=t
NEXT W
IF k=n THEN !すべて並んだなら
LET ANSWER_COUNT=ANSWER_COUNT+1 !並びを表示する
PRINT "No."; ANSWER_COUNT
MAT PRINT d;
ELSE
LET a(i)=a(k) !!!!
LET a(k)=t
FOR J=P+1 TO mn !空き位置を探す
IF d(J)=0 THEN EXIT FOR
NEXT J
CALL perm(a,k+1, J) !次へ
LET tt=a(k) !元に戻す ※t
LET a(k)=a(i)
LET a(i)=tt
END IF
FOR W=P+(t+1)*(m-1) TO P STEP -(t+1) !restore it ※
LET d(W)=0
NEXT W
ELSE !※※枝刈りの状況を表示する
! FOR X=1 TO k-1
! PRINT a(X);
! NEXT X
! PRINT t
END IF
NEXT i
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2014年 4月25日(金)11時28分46秒
|
|
|
|
> No.3367[元記事へ]
きれいな並びがないか。。。
L(2,4k+3)とL(2,4k+4)の関係
次のような並びにすると、半分の数の検索で済む。パズルとしては楽になる。
k=0,1,2,3,…とする。
n=4k+3のとき
[(n+1)/2]からnまでの[(n+1)/2]個の数を順に並べる。
残りの数（1から[(n+1)/2]-1まで）を埋める。
例 n=7のとき
４５６７○４○５○６○７○○として、１～３を考える。
n=4k+4のとき
同様に、上半分の数を埋める。
下半分の数（残りの数）は、上記の右半分の並びを右へ1枠ずらせばよい。
例 n=8のとき
４５６７○４○５○６○７○○
＼ ＼ ＼ ＼ ＼＼
４５６７８４○５○６○７○８○○
N=3
2 3 1 2 1 3
N=4
2 3 4 2 1 3 1 4
N=7
4 5 6 7 1 4 1 5 3 6 2 7 3 2
N=8
4 5 6 7 8 4 1 5 1 6 3 7 2 8 3 2
N=11
6 7 8 9 10 11 5 6 1 7 1 8 5 9 4 10 3 11 2 4 3 2
N=12
6 7 8 9 10 11 12 6 5 7 1 8 1 9 5 10 4 11 3 12 2 4 3 2
以下、n=4k+3のみ
N= 15
8 9 10 11 12 13 14 15 7 8 1 9 1 10 5 11 7 12 6 13 5 14 4 15 3 6 2 4 3 2
N= 19
10 11 12 13 14 15 16 17 18 19 9 10 5 11 1 12 1 13 5 14 9 15 7 16 8 17 4 18 6 19 7 4 3 8 2 6 3 2
N= 23
12 13 14 15 16 17 18 19 20 21 22 23 11 12 7 13 3 14 9 15 3 16 7 17 11 18 10 19 9 20 5 21 8 22 4 23 5 10 6 4 2 8 1 2 1 6
N= 27
14 15 16 17 18 19 20 21 22 23 24 25 26 27 13 14 7 15 3 16 11 17 3 18 7 19 9 20 13 21 12 22 11 23 10 24 9 25 5 26 8 27 4 12 5 10 6 4 2 8 1 2 1 6
N= 31
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 15 16 11 17 7 18 13 19 1 20 1 21 7 22 11 23 15 24 14 25 13 26 12 27 5 28 10 29 9 30 5 31 8 14 4 12 6 10 9 4 3 8 2 6 3 2
N= 35
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 17 18 13 19 7 20 15 21 1 22 1 23 7 24 11 25 13 26 17 27 16 28 15 29 14 30 11 31 12 32 5 33 10 34 9 35 5 16 8 14 4 12 6 10 9 4 3 8 2 6 3 2
N= 39
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 19 20 15 21 11 22 17 23 5 24 1 25 1 26 5 27 11 28 15 29 19 30 18 31 17 32 16 33 13 34 14 35 3 36 12 37 3 38 9 39 10 18 13 16 7 14 8 12 9 4 6 10 7 2 4 8 2 6
N= 43
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 21 22 17 23 13 24 19 25 7 26 1 27 1 28 15 29 7 30 13 31 17 32 21 33 20 34 19 35 18 36 15 37 16 38 11 39 14 40 3 41 12 42 3 43 10 20 11 18 9 16 8 14 4 12 6 10 5 4 9 8 2 6 5 2
N= 47
24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 23 24 19 25 13 26 21 27 7 28 1 29 1 30 17 31 7 32 13 33 15 34 19 35 23 36 22 37 21 38 20 39 17 40 18 41 15 42 16 43 11 44 14 45 3 46 12 47 3 22 10 20 11 18 9 16 8 14 4 12 6 10 5 4 9 8 2 6 5 2
N= 51
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 25 26 21 27 17 28 23 29 9 30 5 31 7 32 19 33 5 34 9 35 7 36 17 37 21 38 25 39 24 40 23 41 22 42 19 43 20 44 15 45 18 46 13 47 16 48 3 49 14 50 3 51 12 24 15 22 13 20 11 18 10 16 4 14 8 12 2 4 6 2 11 10 1 8 1 6
N= 55
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 27 28 23 29 19 30 25 31 9 32 5 33 7 34 21 35 5 36 9 37 7 38 17 39 19 40 23 41 27 42 26 43 25 44 24 45 21 46 22 47 17 48 20 49 15 50 18 51 13 52 16 53 3 54 14 55 3 26 12 24 15 22 13 20 11 18 10 16 4 14 8 12 2 4 6 2 11 10 1 8 1 6
N= 59
？？？？？？？？？？？？？？？？？？？？？
N= 63
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 31 32 27 33 23 34 29 35 17 36 13 37 3 38 25 39 3 40 1 41 1 42 21 43 13 44 17 45 23 46 27 47 31 48 30 49 29 50 28 51 25 52 26 53 21 54 24 55 19 56 22 57 7 58 20 59 15 60 18 61 7 62 16 63 11 30 14 28 19 26 12 24 15 22 10 20 11 18 9 16 8 14 4 12 6 10 5 4 9 8 2 6 5 2
N= 67
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 33 34 29 35 25 36 31 37 17 38 13 39 3 40 27 41 3 42 1 43 1 44 23 45 13 46 17 47 21 48 25 49 29 50 33 51 32 52 31 53 30 54 27 55 28 56 23 57 26 58 21 59 24 60 19 61 22 62 7 63 20 64 15 65 18 66 7 67 16 32 11 30 14 28 19 26 12 24 15 22 10 20 11 18 9 16 8 14 4 12 6 10 5 4 9 8 2 6 5 2
N= 71
？？？？？？？？？？？？？？？？？？？？？
N= 75
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 37 38 33 39 29 40 35 41 23 42 19 43 13 44 31 45 7 46 1 47 1 48 27 49 7 50 13 51 25 52 19 53 23 54 29 55 33 56 37 57 36 58 35 59 34 60 31 61 32 62 27 63 30 64 25 65 28 66 21 67 26 68 15 69 24 70 17 71 22 72 3 73 20 74 3 75 18 36 15 34 21 32 16 30 17 28 14 26 11 24 12 22 4 20 10 18 9 4 8 16 11 14 6 12 5 10 9 8 2 6 5 2
N= 79
？？？？？？？？？？？？？？？？？？？？？
N= 83
42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 41 42 37 43 33 44 39 45 27 46 23 47 19 48 35 49 13 50 7 51 3 52 31 53 3 54 7 55 29 56 13 57 19 58 23 59 27 60 33 61 37 62 41 63 40 64 39 65 38 66 35 67 36 68 31 69 34 70 29 71 32 72 25 73 30 74 15 75 28 76 21 77 26 78 11 79 24 80 17 81 22 82 15 83 20 40 11 38 25 36 18 34 21 32 16 30 17 28 14 26 9 24 12 22 1 20 1 8 10 18 9 16 5 14 6 12 8 4 5 10 2 6 4 2
N= 87
44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 43 44 39 45 35 46 41 47 29 48 23 49 19 50 37 51 13 52 7 53 3 54 33 55 3 56 7 57 31 58 13 59 19 60 23 61 27 62 29 63 35 64 39 65 43 66 42 67 41 68 40 69 37 70 38 71 33 72 36 73 31 74 34 75 27 76 32 77 25 78 30 79 15 80 28 81 21 82 26 83 11 84 24 85 17 86 22 87 15 42 20 40 11 38 25 36 18 34 21 32 16 30 17 28 14 26 9 24 12 22 1 20 1 8 10 18 9 16 5 14 6 12 8 4 5 10 2 6 4 2
N= 91
？？？？？？？？？？？？？？？？？？？？？
N= 95
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 47 48 43 49 39 50 45 51 33 52 29 53 25 54 41 55 17 56 13 57 9 58 37 59 1 60 1 61 35 62 9 63 13 64 17 65 31 66 25 67 29 68 33 69 39 70 43 71 47 72 46 73 45 74 44 75 41 76 42 77 37 78 40 79 35 80 38 81 31 82 36 83 27 84 34 85 19 86 32 87 23 88 30 89 21 90 28 91 3 92 26 93 3 94 24 95 19 46 22 44 27 42 20 40 23 38 21 36 18 34 15 32 16 30 7 28 14 26 6 24 12 22 7 20 10 6 15 18 11 16 8 14 5 12 2 10 4 2 5 8 11 4
N= 99
？？？？？？？？？？？？？？？？？？？？？
N= 103
？？？？？？？？？？？？？？？？？？？？？
|
|
|
戻る