９の倍数　　　　 　　　 　 　　　　　　　　　 　　　　　　　　　　　　　　　

　１〜９の数字をいくつか足して、和が９の倍数となるような場合の数を求めたい。ただし、
足す順番は無視するものとする。

　（１）　１〜９の数字を最大１回だけ使えるときは何通りあるか。

　（２）　１〜９の数字を最大２回だけ使えるときは何通りあるか。

（参考文献：筑波大学付属駒場高校　数学科学研究会　編　「Ｃａｆｅ　Ｂｏｌｌ　Ｗｅｃｋ　Ｎｏ．７」）


































（答）　（２）を先に考える。

　　１、１＋１（＝２）、３、３＋１（＝４）、３＋１＋１（＝５）、３＋３（＝６）、３＋３＋１（＝７）、
　　３＋３＋１＋１（＝８）

　　と、１〜８までの数字が、１と３のみで表される。

　　そこで、問題の条件を満たす場合は、２、４、５、６、７、８、９ をそれぞれ０個〜２個足し
　た式に、上の８つの式の何れかを加えて（加えられる式がもともと９の倍数の場合は加え
　ないものとする）、９の倍数にしたものと考えられる。

　　したがって、求める場合の数は、　３⁷−１＝２１８７−１＝２１８６（通り）　となる。


（コメント）　０〜８のパターンを予め作っておき、それを用いて９の倍数になるように調整す
　　　　　　るという発想に脱帽しました。素晴らしいアイデアに感動！


　（１）も（２）と同様に出来ると思ったが、使える数字は１回までという制約が厳しくて意外に
難しい。


　（１）について、攻略法さんが（２）のアイデアを応用された。（平成２５年１２月１２日付け）

　上記の解では３進法の考え方が用いられている。それなら２進法でも・・・と。

類題　１〜８の数字をいくつか足して、和が８の倍数となるような場合の数を求めたい。ただ
　　　　し、足す順番は無視するものとする。

　(１)　１〜８の数字を最大１回だけ使えるときは何通りあるか。

類題　１〜１６の数字をいくつか足して、和が１６の倍数となるような場合の数を求めたい。た
　　　だし、足す順番は無視するものとする。

　(１)　１〜１６の数字を最大１回だけ使えるときは何通りあるか。

元の問題(１)に戻って、Bさんの解答（２進法に着目して数え上げる）

　１から８までの数字で考える。２進法に着目して、

　1　、2　、2+1（=3）　、4　、4+1（=5）　、4+2（=6）　、4+2+1（=7）

と、１〜７までの数字が、１と２と４のみで表される。

　８は、上記の式の組合せではできないので、直接８を足すことになる。

　問題の条件を満たす場合は、３、５、６、７、８をそれぞれ０個〜１個足した式に、上の７つの
式の何れかを加えて（加えられる式がもともと９の倍数の場合は加えないものとする）、９の
倍数にしたものと考えられる。

　これは、２⁵＝３２通りとなる。列挙すると、
　何れも未使用 = 0  ≡ 0　ｍｏｄ ９
　        8 = 8  ≡ 8
　      7   = 7  ≡ 7
　      7+8 = 15 ≡ 6
　    6     = 6  ≡ 6
　    6  +8 = 14 ≡ 5
　    6+7   = 13 ≡ 4
　    6+7+8 = 21 ≡ 3
　  5       = 5  ≡ 5
　  5    +8 = 13 ≡ 4
　  5  +7   = 12 ≡ 3
　  5  +7+8 = 20 ≡ 2
　  5+6     = 11 ≡ 2
　  5+6  +8 = 19 ≡ 1　←←← 8を足すことができない
　  5+6+7   = 18 ≡ 0
　  5+6+7+8 = 26 ≡ 8
　3         = 3  ≡ 3
　3      +8 = 11 ≡ 2
　3    +7   = 10 ≡ 1　←←← 3+7+8と重複する
　3    +7+8 = 18 ≡ 0
　3  +6     = 9  ≡ 0
　3  +6  +8 = 17 ≡ 8
　3  +6+7   = 16 ≡ 7
　3  +6+7+8 = 24 ≡ 6
　3+5       = 8  ≡ 8
　3+5    +8 = 16 ≡ 7
　3+5  +7   = 15 ≡ 6
　3+5  +7+8 = 23 ≡ 5
　3+5+6     = 14 ≡ 5
　3+5+6  +8 = 22 ≡ 4
　3+5+6+7   = 21 ≡ 3
　3+5+6+7+8 = 29 ≡ 2

　この中で、剰余１の２通りが除かれるので、　２⁵−２＝３０通り。

　これらの場合に、９を付け加えた場合も、９の倍数である。

　したがって、９を含む、含まないの両方を考えて、求める場合の数は、

　　２*３０−１＝５９（通り）となる。（終り）


（コメント）　攻略法さん、解答ありがとうございます。２進法を考えれば、（１）も（２）と同様に
　　　　　　エレガントに求まるんですね。まさしく私が欲していた解答です！


　当ＨＰ読者のＨＮ「とんくま」さんが、プログラムにより解を探究されました。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２５年１２月１０日付け）

　パズルをプログラムで解いては面白みが無いかもしれませんが、SQL(on DB2)でやってみ
ました。十分な検証はしていませんが、とりあえず、

　（１）　１〜９の数字を最大１回だけ使えるときは何通りあるか。
　（２）　１〜９の数字を最大２回だけ使えるときは何通りあるか。

に対して、　（１）　59通り　（２）　2186通り　の結果を得ました。

（（１）の出力結果）

（コメント）　とんくまさん、解答をお寄せいただき、ありがとうございます。

　（１）については、（２）のようなエレガントな解答が期待できそうになかったので、次のように地
道に数え上げようと思っていました。

　（１）　９の倍数になるのは、各位の数の和が９の倍数になるとき。

　一個の和（Ａ）のとき、　Ａ＝９　のみで、１通り。

　二個の和（Ａ＋Ｂ）のとき、　Ａ＋Ｂ＝９　の場合について、

　　　　Ａ＋Ｂ＝９　となるのは、　１＋８、２＋７、３＋６、４＋５　の４通り

　三個の和（Ａ＋Ｂ＋Ｃ）のとき、　Ａ＋Ｂ＋Ｃ＝９、１８　の場合について、

　　　　Ａ＋Ｂ＋Ｃ＝９　となるのは、　１＋２＋６、１＋３＋５、２＋３＋４　の３通り

　　　　Ａ＋Ｂ＋Ｃ＝１８　となるのは、　１＋８＋９、２＋７＋９、３＋６＋９、３＋７＋８、
　　　　　　　　　　　　　　　　　　　　　　　４＋５＋９、４＋６＋８、５＋６＋７　の７通り

　四個の和（Ａ＋Ｂ＋Ｃ＋Ｄ）のとき、　Ａ＋Ｂ＋Ｃ＋Ｄ＝１８、２７　の場合について、

　　　　Ａ＋Ｂ＋Ｃ＋Ｄ＝１８　となるのは、　１＋２＋６＋９、１＋２＋７＋８、１＋３＋５＋９、
　　　　　　　　　　　　　　　　　　　　　　　　　１＋３＋６＋８、１＋４＋５＋８、１＋４＋６＋７、
　　　　　　　　　　　　　　　　　　　　　　　　　２＋３＋４＋９、２＋３＋５＋８、２＋３＋６＋７、
　　　　　　　　　　　　　　　　　　　　　　　　　２＋４＋５＋７、３＋４＋５＋６　の１１通り

　　　　Ａ＋Ｂ＋Ｃ＋Ｄ＝２７　となるのは、　３＋７＋８＋９、４＋６＋８＋９
　　　　　　　　　　　　　　　　　　　　　　　　　５＋６＋７＋９　の３通り

　五個の和（Ａ＋Ｂ＋Ｃ＋Ｄ＋Ｅ）のとき、　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・。


　当ＨＰがいつもお世話になっているＨＮ「数々の和」さんが、（１）について考察されました。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２５年１２月１１日付け）

　法９で考え、A={1，2，3，4，−4，−3，−2，−1}　とする。Ａの部分集合で、要素の和が９
の倍数になる組の数を考えればよい。

　要素がｋ個の場合の数と８−ｋ個の場合の数は同じである（補集合を考えればよい）ので、

ｋ＝0、1、2、3、4 の場合を考えればよい。

　ｋ＝0　のとき　｛｝の1組

　ｋ＝1　のときはない。

　ｋ＝2　のとき、絶対値が同じ２数を加える場合しか９の倍数は得られないので、4組。

　ｋ＝3　のとき、絶対値が同じ２数を含まない。1組できると符号が反対のものも条件を満た
　　す。正のものが２個以上の場合を考えればよい。

　すべてが正の数の場合は、{2，3，4}　、２個が正の数の場合は、{1，2，−3}　、{1，3，−4}

　したがって、(１＋２)×２＝６組

　ｋ＝4　のとき、１組できると補集合もｋ個の同じ条件を満たす。したがって、１を含むすべて
　　の場合を考えればよい。また、同符号のものを３個以上含むことはない。このとき、
　　　{1，2，−1，−2}、{1，3，−1，−3}、{1，4，−1，−4}、{1，4，−2，−3}

　したがって、４×２＝８組

　ｋ＝5　のとき、６組

　ｋ＝6　のとき、４組

　ｋ＝8　のとき、１組

　これらに９を付け加えても９の倍数である。ただし、空集合には９を付け加えたときだけが
有効である。

　以上から、　(１＋４＋６＋８＋６＋４＋１）×２−１＝５９（通り）


（コメント）　法９で考えることにより数え上げがスッキリですね！数々の和さんに感謝します。


　当ＨＰがいつもお世話になっているＨＮ「ａｔ」さんが、問題の一般化に挑戦されました。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２５年１２月１０日付け）

　気が向いたら、上記の問題を少し一般化した次の問題を考えてみてください。

【問題】　ｎを任意の正整数とします。１〜９の数字を１つ以上足し合わせて、和が９の
　　　　　倍数となるような場合の数を考えます。ただし、足す順番は無視するものとし
　　　　　ます。また、１〜９のどの数字についても、最大 ｎ 回だけ使えるものとします。

　　　　　　このとき、和が９の倍数となるような場合の数がF(ｎ)通りあるものとします。
　　　　　F(ｎ)をｎの式で表してください。

　参考までに、ｎ=1、2、3、4、5、6、7、8、9、10 に対するF(ｎ)の値を、Maxima を使って計算
した結果を書いておきます。

　F(1)=59　、F(2)=2186　、F(3)=29143　、F(4)=217044　、F(5)=1119743　、F(6)=4483814
　F(7)=14913199　、F(8)=43046720　、F(9)=111111339　、F(10)=261994490

＜計算に使用したMaximaのプログラム＞
　　F(n):=sum(coeff(expand(prod(sum((x^k)^j,j,0,n),k,1,9)),x,9*p),p,1,5*n)$


　らすかるさんからのコメントです。（平成２５年１２月１０日付け）

　プログラムを作って求めてみました。

　F(1)=59　、F(2)=2186　、F(3)=29143　、F(4)=217044　、F(5)=1119743　、F(6)=4483814
　F(7)=14913199　、F(8)=43046720　、F(9)=111111339　、F(10)=261994490
　F(11)=573308927　、F(12)=1178278204　、F(13)=2295672483　、F(14)=4271484374
　F(15)=7635498335　、F(16)=13176431824　、F(17)=22039921151
　F(18)=35854190178　、F(19)=56888890679　、F(20)=88253338508
　F(21)=134141026579　、F(22)=200128076214　、F(23)=293534171135
　F(24)=423855255224　、F(25)=603278190475　、F(26)=847288609442
　F(27)=1175383999719　、F(28)=1611905113868　、F(29)=2186999999999
　F(30)=2937735802270　、F(31)=3909374683839　、F(32)=5156831600216
　F(33)=6746332538363　、F(34)=8757293195314　、F(35)=11284439629823
　F(36)=14440193321844　、F(37)=18357344596979　、F(38)=23192040128750
　F(39)=29127111125359　、F(40)=36375770503560　、F(41)=45185709316607
　F(42)=55843623566234　、F(43)=68680204408903　、F(44)=84075626953124
　F(45)=102465573651555　、F(46)=124347830367854　、F(47)=150289495621631
　F(48)=180934844238448　、F(49)=217013888916699　、F(50)=259351685898938
　　(以降10飛び)
　F(60)=1299349565920940　、F(70)=5094277857685030　、F(80)=16677181699666568
　F(90)=47547755570144010　、F(100)=121520585854046900
　F(110)=284226324931833398　、F(120)=617768590388419480
　F(130)=1262406294938257170　、F(140)=2447538344675751428
　F(150)=4534715195244855350　、F(160)=8075889627521143840
　F(170)=13890647296424932658　、F(180)=23166726118451719620
　F(190)=37588742395509694910　、F(200)=59500690724697049088
　F(210)=92108474215593440290　、F(220)=139729451328651058380
　F(230)=208096755760337932718　、F(240)=304726956232590605360
　F(250)=439360473796156542250　、F(260)=624485065329505575548
　F(270)=875953613306843962830　、F(280)=1213708433620805614520
　F(290)=1662625325277534129578　、F(300)=2253491638133658420700

　　F(n)≒(n+1)⁹/9 にはなっていますね。


　ａｔ さんからのコメントです。（平成２５年１２月１０日付け）

　鋭いご指摘です。確かにそうなっています。特に、n≡2、5、8　(mod 9)のときには、
F(n)=(n+1)⁹/9 - 1 となります。



　　以下、工事中！