ランフォード問題（Langford's Problem）

 投稿者：山中和義  投稿日：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

 		 

Re: ランフォード問題（Langford's Problem）

 投稿者：山中和義  投稿日：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 )

 		 

Re: ランフォード問題（Langford's Problem）

 投稿者：山中和義  投稿日：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

 		 

Re: ランフォード問題（Langford's Problem）

 投稿者：山中和義  投稿日：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
？？？？？？？？？？？？？？？？？？？？？


 		 

戻る