・異なる部分和の構成                     GAI 氏

 最大7までの異なる自然数を4個集めたとき、どの部分和も異なる値になる組み合わせと
して、[3,5,6,7] がただ一組取れる。

 確かに、

  3+5=8 、3+6=9 、3+7=10 、5+6=11 、5+7=12 、6+7=13 、3+5+6=14 、3+5+7=15
  5+6+7=18 、3+5+6+7=21

とすべて異なる和を作る。これに対し、[2,3,6,7] なら、2+7=9、3+6=9 と同じ和をなす部分和が
発生する。

 そこで、最大数13までの異なる自然数を5個集めたとき、どの部分和もすべて異なる値を
持つようになる組み合わせはどんなものになるか?


 moonlight さんからのコメントです。(平成30年10月11日付け)

 なるほど、かの有名な森 博嗣さんの「笑わない数学者」に出てくる番号付き球の輪っか問
題の輪っか抜きな問題にも似てる。ふーむ、楽しそう。


 らすかるさんからのコメントです。(平成30年10月11日付け)

 [3,5,6,7]の各数字に6ずつ足せば、

 3,5,6,7 では、 2個:8〜13 、3個:14,15,16,18 、4個:21 だったので、

 9,11,12,13 では、 2個:20〜25 、3個:32,33,34,36 、4個:45 となる。

 よって、残り1個を6にすれば、

 6+「1個」は、15〜19 、6+「2個」は、26〜31 、6+「3個」は、38〜42 なのでうまくいく。

 従って、[6,9,11,12,13] は解。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月11日付け)

 [6,9,11,12,13] は、[k,k+3,k+5,k+6,k+7] の形だということですね。「3と15の饗宴」に関連す
る情報があります。

 ところで、[k,k+3,k+5,k+6,k+7] の形にあてはまらない解があることを思い出しました。
[3,6,11,12,13] です。

 直接的に手計算で確認するのは面倒ですので、今夜の私はズルをして、数式を展開して
くれるサイトを利用しました。このサイトのページ「式の計算」において、評価する式を次のよ
うに入力しました。

 (x^3+1)*(x^6+1)*(x^11+1)*(x^12+1)*(x^13+1)

 この式の展開結果は次のようになります。

 x^45+x^42+x^39+x^36+x^34+x^33+x^32+x^31+x^30+x^29+x^28+x^27+x^26+x^25+x^24
+x^23+x^22+x^21+x^20+x^19+x^18+x^17+x^16+x^15+x^14+x^13+x^12+x^11+x^9+x^6+x^3+1

 各項の係数が1であることを確認して、《異なる部分和の構成》についてオーケイと判断で
きました。


(コメント) 面白い判定法ですね![3,5,6,7] について追認してみました。

 (x^3+1)*(x^5+1)*(x^6+1)*(x^7+1)
=x^21+x^18+x^16+x^15+x^14+x^13+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^3+1

で、確かに係数が1となり、条件を満たすことが確認できますね!分かり易いです。
ハンニバル・フォーチュンさんに感謝します。


 GAI さんからのコメントです。(平成30年10月13日付け)

 最大値(M)を13、集める数(N)を5とした場合の部分集合の和をすべて異なるものにするパ
ターンは、

 [3,6,11,12,13] と [6,9,11,12,13]

の2つあるということになるわけですよね。

 「A096858」にある例を見てみると、最大値7、集める数が4なら、[3,5,6,7]の唯一つ。
(一応コンピューター全検索で確認)

 では、その先にある

M=24、N=6 -> [11,17,20,22,23,24]
M=44、N=7 -> [20,31,37,40,42,43,44]
M=84、N=8 -> [40,60,71,77,80,82,83,84]
・・・・・・・・・・・・・・・・・・・・・・・・・

はただ一つの解なのか、はたまた他の解が存在できるのか?どうなんですかね?


 らすかるさんからのコメントです。(平成30年10月13日付け)

 N=3 のとき、[2,3,4] の他に [1,2,4] もあります。N=4、6、7、9 は唯一です。

 N=5 のときは確かに、[3,6,11,12,13] と [6,9,11,12,13] の2通りです。

 N=8 のときは、[40,60,71,77,80,82,83,84] の他に

 [20,40,71,77,80,82,83,84] と [39,59,70,77,78,79,81,84]

があり、計3通りです。この3通りは、「鳩ノ巣原理」にも書かれていました。

 N=9 までは全探索しましたが、N≧10 はちょっと厳しいですね。

 N=9 のときは、検索して見つけたページを見ると、1通りしかなさそうです。

 [2,3,4]→[1,2,4]
 [6,9,11,12,13]→[3,6,11,12,13]
 [40,60,71,77,80,82,83,84]→[20,40,71,77,80,82,83,84]

というパターンを見ると、先頭の2個が 2k、3k のとき、その2個を k、2k に置き換えても大丈
夫そうに見えますので、そうなっているN=12の場合の

 [570,855,1003,1080,1120,1140,1151,1157,1160,1162,1163,1164]

に対して、

 [285,570,1003,1080,1120,1140,1151,1157,1160,1162,1163,1164]

を確認したら、確かにこのパターンも条件を満たしていました。同様に、N=17の場合の先頭
2つ [16996,25494,…] を [8498,16996,…] に置き換えたものも条件を満たしていました。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月13日付け)

 N=9 では唯一ではないのではと思いました。

 [ 77, 117, 137, 148, 154, 157, 159, 160, 161 ] 、[77,116,136,147,154,155,156,158,161]

が考えられます。(わたし、手計算間違いましたかね……? 御検算を願いたく)


 らすかるさんからのコメントです。(平成30年10月13日付け)

 77+116+136+147+154=630 、155+156+158+161=630 ですね。プログラムで全探索してい
ますので、唯一であることはまず間違いないと思います。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月13日付け)

 お手を煩わせてしまい、申し訳ありませんでした。そして、ご指摘を有り難うございます。
やはり、山勘での手計算ではどうにもなりませんですね。



                         投稿一覧に戻る