当ＨＰがいつもお世話になっているＨＮ「ａｔ」さんからの出題です。
（平成２６年４月１８日付け）
気が向いたら次の問題を考えてみてください。
問題 4022個の数 1，1，2，2，3，3，・・・，2011，2011 をうまく一列に並べると、1≦ｎ≦2011
を満たす全ての自然数 ｎ に対して、２つの ｎ の間には ｎ 個の数があるようにすること
が出来ることを示してください。
（答） ＧＡＩ さんが考察されました。（平成２６年４月１８日付け）
1,1,2,2,3,3 なら、例えば、3,1,2,1,3,2 1のように並ぶときということですか？（1,1,2,2の場合
はどのように並べても無理ですね。）
1,1,2,2,3,3,4,4 なら、4,1,3,1,2,4,3,2
1,1,2,2,3,3,4,4,5,5 は作れませんでした。
1,1,2,2,3,3,4,4,5,5,6,6 も無理のような気がします。
1,1,2,2,3,3,4,4,5,5,6,6,7,7 なら、1,4,1,5,6,7,4,2,3,5,2,6,3,7 1,6,1,3,5,7,4,3,6,2,5,4,2,7
2,3,6,2,7,3,4,5,1,6,1,4,7,5 ･････
でも、これを、1,1,2,2,3,3,･････,2011,2011 までやってみる意欲は出てきません。
ａｔ さんからのコメントです。（平成２６年４月１８日付け）
GAIさんの上げられた例は、すべて条件を満たしていますね。
DD++ さんからのコメントです。（平成２６年４月１８日付け）
Twitterの数学botの投稿問題ですよね。以前に投稿問題を全部抽出して解答を作ったの
ですが、10問ほどどうにも解けなかったうちの1つです。最大数≡0、3 (mod 4 ) が必要条件
であることはすぐ証明できますが、十分性はどう証明したものかまったくわからず投げました。
解ける方がいたら私も答えを知りたいです。
ａｔ さんからのコメントです。（平成２６年４月１９日付け）
問題文の条件をみたすような2n個の整数の並びは、Langford pairing (Langford sequence)
と呼ばれているようです。
ｎ≡０ or ３ (mod ４) の場合に限り、Langford pairing が存在することが知られています。
したがって、ｎ＝２０１１の場合には、Langford pairing が存在します。
以下に、この問題の答えを書いておきます。この解答は、「組合せ論の精選 102問」という
本の114頁に書いてあるものと同じものです。
(解答) ｎ＝４ｍ−１ (ｍは２以上の整数) とかけるとき、２ｎ個の整数を次のように並べれば
よい。
(4m-4, 4m-6, ・・・, 2m), 4m-2, (2m-3, 2m-5, ・・・, 1), 4m-1,(1, 3, ・・・, 2m-3),
(2m, 2m+2, ・・・, 4m-4), 2m-1,(4m-3, 4m-5, ・・・, 2m+1), 4m-2, (2m-2, 2m-4, ・・・, 2),
2m-1,4m-1, (2, 4, ・・・, 2m-2), (2m+1,2m+3, ・・・, 4m-3)
（コメント） ｎ＝２０１１のとき、ｍ＝５０３なので、
2008,2006,・・・,1006,2010,1003,1001,・・・,3,1,2011,1,3,・・・,1003,1006,1008,・・・,2008,1005,
2009,2007,・・・,1007,2010,1004,1002,・・・,4,2,1005,2011,2,4,・・・,1004,1007,1009,・・・,2009
構造的には、「1005（=[2011/2]、2010、2011」が別扱いで、
（1006〜2008の偶数（降順で502個））、
2010、
（1〜1003の奇数（昇順で502個））、2011、（1〜1003の奇数（降順で502個））、
（1006〜2008の偶数（昇順で502個））、
1005、
（1007〜2009の奇数（降順で502個））、
2010、
（2〜1004の偶数（降順で502個））、1005、2011、（2〜1004の偶数（昇順で502個））、
（1007〜2009の奇数（昇順で502個）
実に巧妙な配置ですね．．．！
DD++ さんからのコメントです。（平成２６年４月１９日付け）
なるほど、そんな並べ方がありましたか。ご教示いただきありがとうございます。ｎ＝４ｍの
ときも同じように並べ方の実例をあげられるのでしょうか？
ａｔ さんからのコメントです。（平成２６年４月２０日付け）
n=4m (mは2以上の整数)のときは、次のような並べ方があります。
(4m-2, 4m-4, ・・・, 2m), 4m-1, (2m-3, 2m-5, ・・・, 1), 4m,(1, 3, ・・・, 2m-3),
(2m, 2m+2, ・・・, 4m-2), 2m-1,(4m-3, 4m-5, ・・・, 2m+1), 4m-1, (2m-2, 2m-4, ・・・, 2),
2m-1,4m, (2, 4, ・・・, 2m-2), (2m+1, 2m+3, ・・・, 4m-3)
ＧＡＩ さんからのコメントです。（平成２６年４月２０日付け）
この並び方について調べてみたら、「1,1,2,2,3,3,4,4,5,5,6,6,7,7」を例のような条件で並べられ
る総数（同型を除く）を、L(2,7)で表すとき、L(2,7)=26 とあった。
そこで、これを探し出すと、
1:{73625324765141} 、2:{72632453764151} 、3:{72462354736151} 、4:{73161345726425}
5:{71416354732652} 、6:{71316435724625} 、7:{74151643752362} 、8:{72452634753161}
9:{57263254376141} 、10:{37463254276151} 、11:{57416154372632} 、12:{57236253471614}
13:{17126425374635} 、14:{57141653472362} 、15:{17125623475364} 、16:{27423564371516}
17:{62742356437151} 、18:{26721514637543} 、19:{36713145627425} 、20:{51716254237643}
21:{23726351417654} 、22:{41716425327635} 、23:{52732653417164} 、24:{35743625427161}
25:{35723625417164} 、26:{24723645317165}
となった。また、「1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9」で条件に合う並び方が
L(3,9)=3 とあったので、調べたら、
1:{191618257269258476354938743} 、2:{191218246279458634753968357}
3:{181915267285296475384639743}
と、ま〜見事に並べられるものですね。
さらに、L(4,24)=3 らしいので、即ち、「1,1,1,1,2,2,2,2,････,24,24,24,24」を条件に合う並びを探
し出そうとコンピュータを走らせ続けてはいますが、いつ終わりがくるともしれず結果をまだ手
に入れられずにいます。どなたかご協力願います。
ＧＡＩ さんからのコメントです。（平成２６年４月２１日付け）
何時終わるとも知れぬ計算を放棄して、すでに誰かが計算しているという確信で、いろいろ
なリンクを手がかりにサイトを探し回ったら、ある論文に、１９７９年に、
Sadao SAITO & Takanori HAYASAKAなる人物が、
L(4,16) 、L(4,18) 、L(4,19)（４通り） 、L(4,20)（１４通り）
の結果を発表されていた。
L(4,16) (異なる16個が４ずつあり、その数をそれぞれの数飛びで配置する）
{3,8,15,16,3,17,18,1,3,1,8,1,3,1,12,13,4,14,15,8,16,4,7,17,11,18,4,12,8,13,7,4,14,5,15,6,11,16,7,5,
12,17,6,13,18,5,7,14,11,6,15,5,2,12,16,2,6,13,2,17,11,2,14,18}
＜１〜１８のうち９と１０を使用されていない。＞
L(4,18)では
{5,13,17,15,21,8,5,2,16,11,2,18,5,2,8,13,2,10,5,15,17,11,14,8,9,16,21,12,10,13,18,4,8,11,9,15,4,14,
17,10,12,4,16,13,9,11,4,7,21,18,10,15,14,12,9,7,17,3,1,16,1,3,1,7,1,3,12,14,18,3,21,7}
＜１〜２１のうち６，１９，２０を使用されていない。＞
以下一部の情報のみ
L(4,19)での４種類で使用されている数
タイプ１：{5,20,13,23,21,17,1,15,4,18,14,9,16,2,10,8,7,6,3}
タイプ２：{5,22,13,17,4,9,12,20,15,16,8,18,14,6,10,11,7,3,2}
タイプ３：{17,5,8,6,18,22,20,12,21,19,11,9,13,16,7,2,4,3,1}
タイプ４：{21,5,12,14,3,l8,22,17,15,19,2,16,13,1,10,11,9,8,4}
L(4,20)での１４種類で使用されている数
タイプ１：{3,21,24,18,14,9,20,1,6,15,19,17,10,16,4,13,12,7.5,2}
タイプ２：{5,25,8,19,17,13,2,22,15,9,16,18,6,11,14,10,12,4,3,1}
タイプ３：{8,13,21,15,23,17,9,4,12,22,20,11,16,18,14,1,6,7,5,2}
タイプ４：{9,12,20,2,24,22,11,16,4,10,18,14,19,13,3,8,5,7,6,1}
タイプ５：{9,14,4,22,24,18,20,13,1,8,19,15,17,16,11,10,12,7,6,2}
タイプ６：{10,5,15,20,24,17,9,1,21,4,14,16,11,13,12,2,7,8,6,3}
タイプ７：{10,19,20,21,4,22,23,2,8,14,18,13,15,6,9,12,7,11,3,1}
タイプ８：{11,14,20,24,10,2,22,19,3,9,15,18,16,17,12,8,13,6,4,1}
タイプ９：{12,21,16,2,24,4,8,19,15,7,14,18,9,17,10,13,5,6,3,1}
タイプ10：{12,21,16,2.24,4,8,19,15,7,14,18,13,17,9,10,5,6,3,1}
タイプ11：{23,3,4,21,18,15,10,22,20,1,19,7,16,11,5,12,13,8,6,2}
タイプ12：{23,11,24,17,7,2,12,10,6,15,19,16,18,14,9,13,8,4,3,1}
タイプ13：{25,6,15,16,18,10,12,22,7,17,9,11,21,14,3,8,4,5,2,1}
タイプ14：{25,20,18,20,1,11,23,8,13,2,15,17,16,14,5,12,6,9,4,3}
であるという。これだけの結果を出すために、どれだけの計算時間を要したか想像するだけ
でもたいへんなことだと思った。現在世の中はコピペが話題になっていますが、過去の埋も
れた成果を再認識するためにはコピペは私にとっては大切なツールです。
しかし、１〜２４の連続した２４個でのL(4,24)については今の私の調査ではまだ未発見です。
らすかるさんからのコメントです。（平成２６年４月２１日付け）
普通に、L(4,24)の全通り探索のプログラムを作ってみたら、探索終了までに数か月〜１年
以上かかりそうでしたので、工夫してなんとか４日間程度で全探索するプログラムを作りまし
た。まだ全体の1/3程度しか探索していませんが、とりあえず見つかった１通りを書きます。
1:{ 4 22 9 24 14 4 6 18 20 7 4 23 9 6 15 4 21 7 12 14 6 19 9 13 22 7 18 6
24 20 15 12 9 7 14 23 5 13 21 16 17 19 5 11 12 18 15 22 5 14 20 13 10 24 5 11
16 12 17 23 21 19 15 10 18 13 2 11 8 2 22 20 2 16 10 2 17 8 24 11 3 19 21 23
3 10 8 1 3 1 16 1 3 1 17 8 }
ＧＡＩ さんからのコメントです。（平成２６年４月２１日付け）
らすかるさんすごい！私も３日間ほど走らせ続けていますが、一向に引っ掛かる気配はあ
りません。せめて一つでも見つけてみたいですが、何ヶ月もかかるのかな〜？
L(4,24)そのものではないのですが、
S = {14; 23; 24; 2; 4; 2; 7; 2; 4; 2; 12; 6; 4; 7; 14; 10; 4; 6; 22; 20; 7; 16; 12; 6; 23;
10; 24; 7; 14; 6; 21; 18; 11; 15; 12; 10; 8; 16; 19; 20; 22; 17; 14; 11; 8; 10; 12; 23; 15;
18; 24; 21; 8; 16; 11; 13; 5; 19; 17; 20; 8; 5; 22; 15; 9; 11; 5; 18; 13; 16; 23; 5; 21; 9;
24; 17; 19; 3; 15; 20; 3; 13; 9; 3; 22; 18; 3; 1; 1; 1; 1; 9; 17; 21; 13; 19}
のバージョンを見つけました。
らすかるさんからのコメントです。（平成２６年４月２２日付け）
２個目が見つかりました。
2:{ 22 3 16 18 6 3 24 20 12 3 1 6 1 3 1 23 1 8 6 16 21 12 18 22 2 6 8 2 20 10 2
24 19 2 12 8 16 17 9 23 10 18 21 13 8 15 22 12 9 20 14 10 19 16 11 17 24 13 9 7 18
15 10 23 21 14 11 7 9 22 20 13 19 17 4 7 5 15 11 4 14 24 5 7 4 13 21 23 5 4 11
17 19 15 5 14 }
現在全体の4/5程度終わったところです。プログラムが正しければ、残りの1/5の中に最後
の1個があるはずなので、ちゃんとあと1個見つかることを祈っています。
ＧＡＩ さんからのコメントです。（平成２６年４月２２日付け）
単純に考えて、(24*4)!/(4!)^24通りの中から３つを探し出そうとしている行為なのですから、
（=7435340283162161415580255141006698819585865618347014285044941
25044273186416150540173484790704310000000000000000000000）
家族全員が同じ誕生日である人が同じ誕生日の人と結婚をして子供１０人がみんな女の子
で年末ジャンボ宝くじに毎年最高額を射止め、雷に打たれて死んでしまうようなあり得ないこ
とを探していることと同じです。らすかるさん最後まで頑張って下さい。このあり得ない３つ子
を見とどけたい！
らすかるさんからのコメントです。（平成２６年４月２３日付け）
探索終了！予定通り３個目も見つかり、この３個以外にないことも確認できました。
3:{ 10 12 13 19 16 14 1 18 1 24 1 10 1 17 12 20 13 23 6 8 14 16 10 19 22 6 18 12 8
21 13 17 6 10 24 14 20 8 16 6 12 23 15 19 13 18 8 22 5 17 14 21 9 7 5 16 11 20 15
24 5 7 9 19 18 23 5 17 11 7 22 4 9 21 15 3 4 7 20 3 11 4 9 3 24 2 4 3 2 23
15 2 11 22 2 21 }
ＧＡＩ さんからのコメントです。（平成２６年４月２３日付け）
お疲れ様でした。この探索にかかった総時間数はわかりますか？サイトで探索にかかった
時間の表を眺めていたら、１年とか３年とかのそら恐ろしいような日数を目にします。もし、こ
れが４日位で済んだことになれば、世界は驚くと思います。ぜひ何かの形で公に発表して下
さい。
クヌース(Knuth)という人がこのプログラミングについてのコンテストを実施しているというの
を読んだ記憶があります。よくはわからないんですがP≠NP問題の例にも使われるとか？
いずれにしてもこの３つ子は大切にコピペさせて貰い、わたしのノートに永久に保存させて
頂きます。
この３つ子を分析していたら、３つとも、一般にceil(96/k)行k列(k=2,3,4,･･･,25)に整理し直し
て観察すると、４つの数字"k"が行列 ceil(96/(k+1))行(k+1)列のマトリックスのある列に４つ
きれいに並んでいるんですね。これがどこの列になるかの分析はまだですが、ここからなに
か手懸かりが出てきそうです。
＜反省＞ 当たり前ですね。大発見をしたと勘違いしてしまいました。（笑）
らすかるさんからのコメントです。（平成２６年４月２３日付け）
探索にかかった総時間数は記録していたので一応わかりますが、性能の異なる2台のPC
で実行しましたので、そのまま時間を足してもあまり意味がない時間になります。2006年購入
のPCで、約50.4時間、2009年購入のPCで、約53.1時間。単純に足すと103.5時間 ← これが
実際にかかった時間の合計。もし、2009年購入のPCで全部実行していたら90時間ぐらい。
最近の速いPCならば、48時間を切れるかも知れませんね。１年とか３年とか書いてあるサイ
トってどこですか？
ＧＡＩ さんからのコメントです。（平成２６年４月２３日付け）
Ｗｅｂサイト「Langford's Problem」のContributors部分に書いてあります。
らすかるさんからのコメントです。（平成２６年４月２３日付け）
表の見方がよくわからないのですが、L(4,24)は、1979年までに、Saito&Hayaskaさんが
18.5分で求めていて、2004年にRichard Nobleさんが2年かかって求めているということです
か？1979年までに18.5分で求められているなら、私は100時間もかかっていますので全然
ダメですね。
ＧＡＩ さんからのコメントです。（平成２６年４月２３日付け）
この「m」はmonthではないでしょうか？18.5ヵ月=1.54年。1979年当時、18.5分はないですよ。
らすかるさんからのコメントです。（平成２６年４月２３日付け）
上から3行目の「5m,40m」というのは多分「分」ですよね。そして、下の方の「2 mo」と
「3 months」は、「分」と間違えないように「mo」とか「months」とか書いてあります。その規則を
当てはめると、「18.5m」は「18.5分」になるんですけどね。「COMPUTER」が「custom」になって
るんで、何でもありですよね。いや、私も時代を考えると「月」の可能性の方が高いとは思っ
ているのですが、この表だけでは確定できないですね。実際、L(2,19)で2年半かかる人もい
れば6時間以内で終わる人もいて、プログラムの組み方で桁違いの時間になるわけで、そう
考えると、L(4,24)も何か特別にうまい方法があったり、理論的に、例えば、「23が偶数番目に
なる方の端から数えて、最初の24の位置は、3n+1番目に限定される」などを証明して、非常
に短時間にできたりとか、可能性としてはいろいろ考えられます。
# 上の「例」は実際に成り立っている規則ですが、もしこれが最初からわかっていれば、計算
時間は1/3になりました。同等の規則が10個あれば、6秒ぐらいで終わる計算になります。
ＧＡＩ さんからのコメントです。（平成２６年４月２５日付け）
Langford's sequence で切りがよいものでの構成：L(2,100)の一つ
98 96 94 92 90 88 86 84 82 80 78 76 74 72 70 68 66 64 62 60 58 56 54 52 50 99 47 45 43 41
39 37 35 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1 100 1 3 5 7 9 11 13 15 17
19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78
80 82 84 86 88 90 92 94 96 98 49 97 95 93 91 89 87 85 83 81 79 77 75 73 71 69 67 65 63 61
59 57 55 53 51 99 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
49 100 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 51 53 55 57
59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97
ＧＡＩ さんからのコメントです。（平成２６年４月２６日付け）
ついに4022の配列 L(2,2011) が完成しました。
ａｔ さんからのコメントです。（平成２６年４月２６日付け）
この並びは、私が４月１９日に書いた (解答)
(4m-4, 4m-6, ・・・, 2m), 4m-2, (2m-3, 2m-5, ・・・, 1), 4m-1,(1, 3, ・・・, 2m-3),
(2m, 2m+2, ・・・, 4m-4), 2m-1,(4m-3, 4m-5, ・・・, 2m+1), 4m-2, (2m-2, 2m-4, ・・・, 2),
2m-1,4m-1, (2, 4, ・・・, 2m-2), (2m+1,2m+3, ・・・, 4m-3)
において、m=503 としたものになっています。