組合せの問題 　　　　　　　　　　　　　　　　　　　　

　思わず手を出したくなる骨太な問題ということで、当ＨＰの掲示板「出会いの泉」に、ＨＮ
「Ｈ．Ｉ．」さんが次のような問題を出題された。（平成２２年２月２４日付け）

　　最近であった問題でなかなか骨のあると思ったものがありました。見た目は簡単で、
　２・３分もあれば答えが出ると思ったのですが・・・。

　　１〜８ の数字の書かれたカードがある。二枚ずつペアを作り、カードの数字の差
　がそれぞれ １、２、３、４ になるような組合わせを求めよ。

　　解答に必要な知識は小学生でも十分ですが、条件をきちんと見極めないと漏れが発生
　します。見た目のシンプルさに比べ、解答に必要な手順はしっかりした道順が必要で、小
　学生には難しいが、中学生なら時間はかかっても解答が得られると思います。
































（答）　当ＨＰがいつもお世話になっている ＧＡＩ さんの解答です。（平成２２年２月２５日付け）

　　　　　差　　 ４　　　　　　３　　　　　　　２　　　　　　１

　　　　　　　（１，５）　　　（４，７）　　　（６，８）　　　（２，３）

　　　　　　　（１，５）　　　（３，６）　　　（２，４）　　　（７，８）

　　　　　　　（２，６）　　　（１，４）　　　（３，５）　　　（７，８）

　　　　　　　（３，７）　　　（５，８）　　　（４，６）　　　（１，２）

　　　　　　　（４，８）　　　（２，５）　　　（１，３）　　　（６，７）

　　　　　　　（４，８）　　　（３，６）　　　（５，７）　　　（１，２）

　　　　一個を探し出して安心していました。全部の組合せが

　　　　　　₈Ｃ₂×₆Ｃ₂×₄Ｃ₂/４！＝１０５（通り）あるので、４組の差が１〜４でグループ分け

　　　出来る確率が、６/１０５＝２/３５＝０．０５７・・・　だから、ちょっとした運試しに手頃なカ
　　　ードゲームになりそうですね。

　　ＧＡＩ さんに触発されて別な視点で考えてみた。

　４組の２数の対のうち大きい方の数を、それぞれ　Ａ、Ｂ、Ｃ、Ｄ　とすると、

　　　Ａ＋Ｂ＋Ｃ＋Ｄ＝｛（１＋２＋３＋４＋５＋６＋７＋８）＋（１＋２＋３＋４）｝/２＝２３

であり、よって、４組の２数の対のうち小さい方の数を、それぞれ　ａ、ｂ、ｃ、ｄ　とすると、

　　　ａ＋ｂ＋ｃ＋ｄ＝２３−（１＋２＋３＋４）＝１３

となる。このとき、　ａ＜ｂ＜ｃ＜ｄ　として、

　　　（ａ，ｂ，ｃ，ｄ）＝（１，２，３，７）、（１，２，４，６）、（１，３，４，５）

の３通りしかない。

　これらの４数に、１２３４の順列

　１２３４　１２４３　１３２４　１３４２　１４２３　１４３２　２１３４　２１４３　２３１４　２３４１

　２４１３　２４３１　３１２４　３１４２　３２１４　３２４１　３４１２　３４２１　４１２３　４１３２

　４２１３　４２３１　４３１２　４３２１

を順次加えて、題意に適するものを探せばよい。

　　（ａ，ｂ，ｃ，ｄ）＝（１，２，３，７）　の場合

　　　　（Ａ，Ｂ，Ｃ，Ｄ）＝（４，６，５，８）　←３４２１

　　　　（Ａ，Ｂ，Ｃ，Ｄ）＝（５，４，６，８）　←４２３１

　　よって、　（１，４）（２，６）（３，５）（７，８）　、　（１，５）（２，４）（３，６）（７，８）

　　（ａ，ｂ，ｃ，ｄ）＝（１，２，４，６）　の場合

　　　　（Ａ，Ｂ，Ｃ，Ｄ）＝（３，５，８，７）　←２３４１

　　　　（Ａ，Ｂ，Ｃ，Ｄ）＝（５，３，７，８）　←４１３２

　　よって、　（１，３）（２，５）（４，８）（６，７）　、　（１，５）（２，３）（４，７）（６，８）

　　（ａ，ｂ，ｃ，ｄ）＝（１，３，４，５）　の場合

　　　　（Ａ，Ｂ，Ｃ，Ｄ）＝（２，６，８，７）　←１３４２

　　　　（Ａ，Ｂ，Ｃ，Ｄ）＝（２，７，６，８）　←１４２３

　　よって、　（１，２）（３，６）（４，８）（５，７）　、　（１，２）（３，７）（４，６）（５，８）

（コメント）　手当たり次第ではなかなか見つけられないようです。順列組合せの問題として
　　　　　　良問と考えられますね！上記では全ての場合を探索しましたが、計算で求める
　　　　　　方法はないのかな？

　出題者のＨＮ「Ｈ．Ｉ．」さんより解答をお寄せいただいた。（平成２２年２月２７日付け）

　まず、適当にペアを作ったと仮定して、

　　ペアの小さい方の数字だけを集めたグループの総和を Ａ
　　ペアの大きい方の数字だけを集めたグループの総和を Ｂ

とすると、　Ｂ＋Ａ＝３６ 　(=1+2+3+4+5+6+7+8)　、　Ｂ−Ａ＝１０　 (=1+2+3+4)　　から

　　　　　　　Ａ＝１３　、　Ｂ＝２３

　この時点でＡの中には１が、Ｂの中には８が必ず含まれていることを見ぬくことも重要です。
Ａ’＝Ａ−１＝１２　とすると、２以上７以下の３つの自然数の和の組み合わせで、１２になる
ものを求めればよいことになり、Ａの組み合わせは、

　　（１）　（１，２，３，７）　　（２）　（１，２，４，６）　　（３）　（１，３，４，５）

　Ｂの組み合わせは、当たり前ですが、Ａに入らなかったものに決まっているので、以下の
ように、一意的に決まります。

　　（１）　｛４，５，６，８｝　　（２）　｛３，５，７，８｝　　（３）　｛２，６，７，８｝

　（１）を見ると、７より大きいものは８しかないので、８−７＝１。あとはそれぞれ２通りのペ
アが考えられます。

　（３）を見ると、２より小さいものは１しかないので、２−１＝１。あとはそれぞれ２通りのペ
アが考えられます。

　（２）は、（１）（３）のような必然のペアはありませんが、例えば６より大きいものは７か８し
かなく、それぞれの場合でペアを考えると結局２通りとなります。

　以上から、６通りで、GAI さんの書かれたような組み合わせとなります。

　問題をさらに一般化すれば、

　１〜２ｎの数の書かれたカードでペアを作り、その差が１〜ｎになる組み合わせの総
数を求めよ。

となるはずですが、今のところ考えてみる予定はありません（；＾＾）。

（コメント）　なるほど！　Ｈ．Ｉ．さんのように考えると、７２通り探索しなくて済みますね。
　　　　　　ＨＮ「Ｈ．Ｉ．」さんに感謝します。

　ｎ＝５　の場合について、ＧＡＩ さんが挑戦された。（平成２２年２月２７日付け）

　　（参考）　ＨＮ「ＦＮ」さんからご教示いただきました。（平成２２年２月２７日付け）

　　　　　　ＨＮ「Ｈ．Ｉ．」さんの議論をそのままｎの場合に適用すれば、
　　　　　　　Ｂ＋Ａ＝ｎ(２ｎ＋１)　、　Ｂ−Ａ＝ｎ(ｎ＋１)/２
　　　　　より、　　Ａ＝ｎ(３ｎ＋１)/４　、　Ｂ＝ｎ(５ｎ＋３)/４　となる。
　　　　　　ｎ＝６、７ の場合は、Ａ、Ｂは整数とならず、したがって、題意を満たす組合せは
　　　　　存在しない。
　　　　　　ｎ＝８　のとき、　Ａ＝５０　、　Ｂ＝８６　なので、題意を満たす組合せがあるかも
　　　　　しれない。（→　ＧＡＩ さんの結果）


　数字を、１〜１０ にして、２枚ずつ５組のセットを作り、その２数の差が １，２，３，４，５ を
構成する組合せを調べると、

　　　　　差　　　５　　　　　　４　　　　　　　３　　　　　　２　　　　　　１
　　　　　　　（１，　６）　　（３，　７）　　（５，　８）　　（２，　４）　　（９，１０）

　　　　　　　（１，　６）　　（５，　９）　　（４，　７）　　（８，１０）　　（２，　３）

　　　　　　　（２，　７）　　（１，　５）　　（６，　９）　　（８，１０）　　（３，　４）

　　　　　　　（２，　７）　　（６，１０）　　（１，　４）　　（３，　５）　　（８，　９）

　　　　　　　（３，　８）　　（２，　６）　　（１，　４）　　（５，　７）　　（９，１０）

　　　　　　　（３，　８）　　（５，　９）　　（７，１０）　　（４，　６）　　（１，　２）

　　　　　　　（４，　９）　　（６，１０）　　（２，　５）　　（１，　３）　　（７，　８）

　　　　　　　（４，　９）　　（１，　５）　　（７，１０）　　（６，　８）　　（２，　３）

　　　　　　　（５，１０）　　（２，　６）　　（４，　７）　　（１，　３）　　（８，　９）

　　　　　　　（５，１０）　　（４，　８）　　（３，　６）　　（７，　９）　　（１，　２）

の１０組が存在する。

　また、数字を　０〜９　のもので考えると
　　　　　差　　　５　　　　　　４　　　　　３　　 　　　２　 　　　　１
　　　　　　　　（１，６）　　（０，４）　　（５，８）　　（７，９）　　（２，３）

　　　　　　　　（１，６）　　（５，９）　　（０，３）　　（２，４）　　（７，８）

　　　　　　　　（２，７）　　（１，５）　　（０，３）　　（４，６）　　（８，９）

　　　　　　　　（２，７）　　（４，８）　　（６，９）　　（３，５）　　（０，１）

　　　　　　　　（３，８）　　（０，４）　　（６，９）　　（４，６）　　（８，９）

　　　　　　　　（３，８）　　（５，９）　　（１，４）　　（０，２）　　（６，７）

　　　　　　　　（４，９）　　（１，５）　　（３，６）　　（０，２）　　（７，８）

　　　　　　　　（４，９）　　（３，７）　　（２，５）　　（６，８）　　（０，１）

　　　　　　　　（０，５）　　（４，８）　　（３，６）　　（７，９）　　（１，２）

　　　　　　　　（０，５）　　（２，６）　　（４，７）　　（１，３）　　（８，９）

の１０組がある。

（コメント）　ＧＡＩ さん、ありがとうございます。ＨＮ「Ｈ．Ｉ．」さんの手法で検証してみました。

　まず、適当にペアを作ったと仮定して、

　　ペアの小さい方の数字だけを集めたグループの総和を Ａ
　　ペアの大きい方の数字だけを集めたグループの総和を Ｂ

とすると、　Ｂ＋Ａ＝５５ 　(=1+2+3+4+5+6+7+8+9+10)　、Ｂ−Ａ＝１５　 (=1+2+3+4+5)　　から

　　　　　　　Ａ＝２０　、　Ｂ＝３５

　この時点でＡの中には１が、Ｂの中には１０が必ず含まれている。
Ａ’＝Ａ−１＝１９　とすると、２以上９以下の４つの自然数の和の組み合わせで、１９になる
ものを求めればよいことになり、Ａの組み合わせは、

　　（１）　（１，２，３，５，９）　　（２）　（１，２，３，６，８）　　（３）　（１，２，４，５，８）

　　（４）　（１，２，４，６，７）　　（５）　（１，３，４，５，７）

　これに対して、Ｂの組み合わせは、

　　（１）　｛４，６，７，８，１０｝　　（２）　｛４，５，７，９，１０｝　　（３）　｛３，６，７，９，１０｝

　　（４）　｛３，５，８，９，１０｝　　（５）　｛２，６，８，９，１０｝

　ここで、

（１）　（１，２，３，５，９）　と　｛４，６，７，８，１０｝　について、まず、１０−９＝１　の場合

　６−１＝５　とした場合、　４＝７−３　、３＝８−５　、　２＝４−２　しかありえない。

　７−２＝５　とした場合、　４＝６−２　だが、これはありえない。

　８−３＝５　とした場合、　４＝６−２　、３＝４−１　、　２＝７−５　しかありえない。

　　以上から、　（１，６）（２，４）（３，７）（５，８）（９，１０）
　　　　　　　　　 （１，４）（２，６）（３，８）（５，７）（９，１０）

（１）　（１，２，３，５，９）　と　｛４，６，７，８，１０｝　について、まず、９−８＝１　の場合

（１）　（１，２，３，５，９）　と　｛４，６，７，８，１０｝　について、まず、６−５＝１　の場合

（１）　（１，２，３，５，９）　と　｛４，６，７，８，１０｝　について、まず、４−３＝１　の場合

（２）　（１，２，３，６，８）　と　｛４，５，７，９，１０｝　について、まず、９−８＝１　の場合

　４＝１０−６　で、　５＝７−２　、３＝４−１　、　２＝５−３　しかありえない。

　　以上から、　（１，４）（２，７）（３，５）（６，１０）（８，９）

（２）　（１，２，３，６，８）　と　｛４，５，７，９，１０｝　について、まず、８−７＝１　の場合

（２）　（１，２，３，６，８）　と　｛４，５，７，９，１０｝　について、まず、７−６＝１　の場合

（２）　（１，２，３，６，８）　と　｛４，５，７，９，１０｝　について、まず、６−５＝１　の場合

（２）　（１，２，３，６，８）　と　｛４，５，７，９，１０｝　について、まず、４−３＝１　の場合

　２＝１０−８　で、　４＝５−１　、５＝７−２　、　３＝９−６　しかありえない。

　　以上から、　（１，５）（２，７）（３，４）（６，９）（８，１０）

（３）　（１，２，４，５，８）　と　｛３，６，７，９，１０｝　について、まず、９−８＝１　の場合

　５＝１０−５　で、　４＝６−２　、３＝７−４　、　２＝３−１　しかありえない。

　　以上から、　（１，３）（２，６）（４，７）（５，１０）（８，９）

（３）　（１，２，４，５，８）　と　｛３，６，７，９，１０｝　について、まず、８−７＝１　の場合

（３）　（１，２，４，５，８）　と　｛３，６，７，９，１０｝　について、まず、６−５＝１　の場合

（３）　（１，２，４，５，８）　と　｛３，６，７，９，１０｝　について、まず、４−３＝１　の場合

（３）　（１，２，４，５，８）　と　｛３，６，７，９，１０｝　について、まず、３−２＝１　の場合

　６−１＝５　とした場合、　４＝９−５　、３＝７−４　、　２＝１０−８　しかありえない。

　９−４＝５　とした場合は起こり得ない。

　１０−５＝５　とした場合は起こり得ない。

　　以上から、　（１，６）（２，３）（４，７）（５，９）（８，１０）

（４）　（１，２，４，６，７）　と　｛３，５，８，９，１０｝　について、まず、８−７＝１　の場合

　５＝９−４　で、　４＝１０−６　、３＝５−２　、　２＝３−１　しかありえない。

　　以上から、　（１，３）（２，５）（４，９）（６，１０）（７，８）

（４）　（１，２，４，６，７）　と　｛３，５，８，９，１０｝　について、まず、６−５＝１　の場合

（４）　（１，２，４，６，７）　と　｛３，５，８，９，１０｝　について、まず、５−４＝１　の場合

（４）　（１，２，４，６，７）　と　｛３，５，８，９，１０｝　について、まず、４−３＝１　の場合

（４）　（１，２，４，６，７）　と　｛３，５，８，９，１０｝　について、まず、３−２＝１　の場合

　５＝９−４　で、　３＝１０−７　、４＝５−１　、　２＝８−６　しかありえない。

　　以上から、　（１，５）（２，３）（４，９）（６，８）（７，１０）

（５）　（１，３，４，５，７）　と　｛２，６，８，９，１０｝　について、まず、８−７＝１　の場合

（５）　（１，３，４，５，７）　と　｛２，６，８，９，１０｝　について、まず、７−６＝１　の場合

（５）　（１，３，４，５，７）　と　｛２，６，８，９，１０｝　について、まず、６−５＝１　の場合

（５）　（１，３，４，５，７）　と　｛２，６，８，９，１０｝　について、まず、３−２＝１　の場合

（５）　（１，３，４，５，７）　と　｛２，６，８，９，１０｝　について、まず、２−１＝１　の場合

　８−３＝５　とした場合、　３＝１０−７　、４＝９−５　、　２＝６−４　しかありえない。

　９−４＝５　とした場合は起こり得ない。

　１０−５＝５　とした場合、　４＝８−４　、３＝６−３　、　２＝９−７　しかありえない。

　　以上から、　（１，２）（３，８）（４，６）（５，９）（７，１０）
　　　　　　　　　 （１，２）（３，６）（４，８）（５，１０）（７，９）

したがって、求める組合せは、

　　（１，６）（２，４）（３，７）（５，８）（９，１０）　、　 （１，４）（２，６）（３，８）（５，７）（９，１０）

　　（１，４）（２，７）（３，５）（６，１０）（８，９）　、　　（１，５）（２，７）（３，４）（６，９）（８，１０）

　　（１，３）（２，６）（４，７）（５，１０）（８，９）　、　　（１，６）（２，３）（４，７）（５，９）（８，１０）

　　（１，３）（２，５）（４，９）（６，１０）（７，８）　、　　（１，５）（２，３）（４，９）（６，８）（７，１０）

　　（１，２）（３，８）（４，６）（５，９）（７，１０）　、　　 （１，２）（３，６）（４，８）（５，１０）（７，９）

の１０組ある。この結果は、ＧＡＩ さんのものと一致する。

（追記）　平成２２年２月２８日付け

　ＧＡＩ さんが、ＦＮさんの指摘を受け、ｎ＝８の場合を調べられたとのこと。５０４通りの組合
せが存在するとのことである。

　ただし、以下の表で、A=10、B=11、C=12、D=13、E=14、F=15　と置き直し、すべての表で
「＋１」する。

（組合せの一部）
　　　　　差　１　　２　　３　　４　　５　　６　　７　　８
------------------------------------------------
No. 1　　　(0,1) (2,4) (9,C) (A,E) (3,8) (5,B) (6,D) (7,F)
No. 2　　　(0,1) (2,4) (A,D) (7,B) (3,8) (9,F) (5,C) (6,E)
No. 3　　　(0,1) (2,4) (B,E) (8,C) (5,A) (3,9) (6,D) (7,F)
No. 4　　　(0,1) (2,4) (B,E) (6,A) (8,D) (3,9) (5,C) (7,F)
No. 5　　　(0,1) (2,4) (7,A) (B,F) (8,D) (3,9) (5,C) (6,E)
No. 6　　　(0,1) (2,4) (B,E) (6,A) (7,C) (3,9) (8,F) (5,D)
No. 7　　　(0,1) (2,4) (B,E) (5,9) (8,D) (6,C) (3,A) (7,F)
No. 8　　　(0,1) (2,4) (6,9) (B,F) (7,C) (8,E) (3,A) (5,D)
No. 9　　　(0,1) (2,4) (5,8) (9,D) (A,F) (6,C) (7,E) (3,B)
No. 10　　(0,1) (2,4) (5,8) (A,E) (7,C) (9,F) (6,D) (3,B)
　　　　　　・・・・・・・・・・・・・・・・・・
　　　　　　・・・・・・・・・・・・・・・・・・
　　　　　　・・・・・・・・・・・・・・・・・・
No. 495　(D,E) (A,C) (2,5) (3,7) (1,6) (9,F) (4,B) (0,8)
No. 496　(D,E) (3,5) (C,F) (7,B) (1,6) (4,A) (2,9) (0,8)
No. 497　(2,3) (4,6) (B,E) (9,D) (A,F) (1,7) (5,C) (0,8)
No. 498　(2,3) (4,6) (A,D) (B,F) (9,E) (1,7) (5,C) (0,8)
No. 499　(2,3) (D,F) (B,E) (6,A) (4,9) (1,7) (5,C) (0,8)
No. 500　(D,E) (2,4) (C,F) (5,9) (6,B) (1,7) (3,A) (0,8)
No. 501　(3,4) (A,C) (2,5) (B,F) (9,E) (1,7) (6,D) (0,8)
No. 502　(C,D) (4,6) (2,5) (B,F) (9,E) (1,7) (3,A) (0,8)
No. 503　(D,E) (3,5) (9,C) (2,6) (A,F) (1,7) (4,B) (0,8)
No. 504　(4,5) (B,D) (C,F) (2,6) (9,E) (1,7) (3,A) (0,8)

　さらに、プログラムに詳しい方に組んでもらい調査したところ、ｎ＝９　のときは、２６５６組
存在することが分かったとのことである。


　この話題について、ＨＮ「ＭｓＭａ」さんより、新たな視点の情報提供があった。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年２月２８日付け）

　Ｈ．Ｉ．さんが提供していただいた問題についてなのですが、今までのことを踏まえると、
１〜２ｎ の数の書かれたカードでペアを作り、その差が１〜ｎになる組み合わせの総数を
Ａ_ｎ とした時、

Ａ₁＝１　、Ａ₂＝０　、Ａ₃＝０　、Ａ₄＝６　、Ａ₅＝１０　、Ａ₆＝０　、Ａ₇＝０　、Ａ₈＝５０４　、・・・

となりますよね。この結果の中で、以前私が自分の中で求めた Ａ₁からＡ₅までの結果を
オンライン整数列大辞典（A059106）で検索したとき、偶然すべて一致するものが見つか
りました。Ａ₆からＡ₈の結果も確か一致していたと思います。果たして本当に偶然でしょう
か・・・。

次のサイトをみると、Ｖ（２，ｎ）の ｎ＝１ 以外の時の数字を２倍にすると今までの結果と
一致します。
　　　　　　　　　http://legacy.lclark.edu/~miller/langford.html

ここでは、「Ｌａｎｇｆｏｒｄ’ｓ　Ｐｒｏｂｌｅｍ」と呼ばれていて、Ｖ（２，ｎ）というものは、１から
ｎまでの数字が書かれたカードが２枚ずつあって、それら２ｎ枚のカードを次の条件で並
べる組合せの数として紹介されています。

　これはＬａｎｇｆｏｒｄ’ｓ　Ｐｒｏｂｌｅｍの特殊な場合の組み合わせのようですね。

　　　ｋ（ｋ＝１、２、・・・、ｎ）の数字が書かれているカードはそのカードの間に
　　ｋ−１枚のカードを挟む

たとえば、ｎ＝４　の時は、　４２３２４３１１　　、　　４１１３４２３２　　、　　３４２３２４１１

の３通りで、もしも裏返しを区別すると、６通りになります。ここからうまく元の問題に帰着
できないでしょうか。

　このＭｓＭａさんの疑問に対して、当ＨＰがいつもお世話になっているＨＮ「らすかる」さんに
よると、次のように考えれば同じになるとのことである。（平成２２年２月２８日付け）

１２３４５６７８
４２３２４３１１ → (1,5)(2,4)(3,6)(7,8)
４１１３４２３２ → (1,5)(2,3)(4,7)(6,8)
３４２３２４１１ → (1,3)(2,6)(3,5)(7,8)

　さらに、らすかるさんはプログラムを作って次の結果を示された。

Ａ₁＝１　、Ａ₂＝０　、Ａ₃＝０　、Ａ₄＝６　、Ａ₅＝１０　、Ａ₆＝０　、Ａ₇＝０　、Ａ₈＝５０４

Ａ₉＝２６５６　、Ａ₁₀＝０　、Ａ₁₁＝０　、Ａ₁₂＝４５５９３６（２秒）　、Ａ₁₃＝３０４０５６０（１５秒）

Ａ₁₄＝０　、Ａ₁₅＝０　、Ａ₁₆＝１４００１５６７６８（３時間半）

（コメント）　Ｈ．Ｉ．さん、ＧＡＩ さん、ＦＮさん、ＭｓＭａさん、らすかるさん、ありがとうございます。
　　　　　　何か奥が深そうな問題でしたね！