問題概略
6 枚のカードにそれぞれ異なる 1 以上の整数が書かれています。
この 6 枚から 2 枚を取り出す方法は 15 通りありますが，それらすべてについて 2 つの数の差が異なっていました。6 枚のカードに書かれた数の最大値と最小値の差は最も小さい場合でいくつでしょうか。
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
基本方針
最大値と最小値の差がわかれば十分なので，最小値を 1 とします。
6 個の数を小さい方から順に並べたときの階差を ,
,
,
,
とすると，6 個の数は次のように表せます。
最大値と最小値の差を とおきます。これは
から
までの総和です。
は
以上です。
これを初期値として，条件をみたす がある
の最小値を探します。
「 を 5 つの数の和に分解」→「15 通りの差がすべて異なるかどうか調べる」という手順になります。
15 通りの差とは次のようなものです。差分の最大値 は明らかに他とダブらないので除きました。
\begin{align*}
&a,\, a + b,\, a + b + c,\, a + b + c + d,\\
&b,\, b + c,\, b + c + d,\, b + c + d + e,\\
&c,\, c + d,\, c + d + e, \\
&d,\, d + e,\\
&e
\end{align*}
答えは「17」なので「 は不可」「
はOK」を示せばいいのですが，これを手計算でやるのはかなり非現実的です。
「 は OK」は実例を 1 つあげるだけなので，そんなに難しくありません。
しかし，「 は不適」を言うにはすべての
を否定しなければなりません。
それぞれを相異なる 5 つの数の和に分割する方法は
と
で各 1 通りです。
これだけ聞くと楽そうですが，置換が 通りずつあります。
合計 240 通りの階差を全部否定しないと「 は不適」は言えません。
そういうわけでプログラムを組んで解きました。言語は mathematica です。
mathematicaで解く
次の手順で解きました。
- IntegerPartitions[ n, {5}] で
を相異なる 5 つの数の和に分解する
- 並べ替えたものを
とする（コード中の f）
- 差がすべて異なるかどうか調べる（コード中の g）
からはじめて，条件をみたす
が出るまで
を増やしていきます。
In[]:= AbsoluteTiming[
f[n_] := Module[{lst},
lst = Select[IntegerPartitions[n, {5}], DuplicateFreeQ];
Flatten[Permutations /@ lst, 1]];
g[{a_, b_, c_, d_, e_}] := Module[{lst},
lst = {a, a + b, a + b + c, a + b + c + d,
b, b + c, b + c + d, b + c + d + e,
c, c + d, c + d + e, d, d + e, e};
DuplicateFreeQ@lst];
ans = NestWhile[# + 1 &, 15, NoneTrue[f@#, g] &]]
Out[]= {0.0022146, 17}答えは 17 で，カードに書かれた数字の組み合わせは 8 通りありました。
\begin{align*}
&(1, 5, 7, 10, 17, 18),\, (1, 4, 6, 10, 17, 18),\, (1, 2, 9, 13, 15, 18)\\
&(1, 2, 9, 12, 14, 18),\, (1, 6, 8, 14, 17, 18),\, (1, 3, 8, 14, 17, 18)\\
&(1, 2, 5, 11, 16, 18),\, (1, 2, 5, 11, 13, 18)
\end{align*}
