募集:いい考え方
小噺という建前で
アイデアがほしいという本音が丸見えなのは置いといて・・・
問題は
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008
のSum of 4 Integersという問題。
AOJの問題は簡単なのもあるのですが、結構骨のある問題がそろっています。
この問題は最初のほうなので、簡単な部類なりますかね。
ざっくり言うと・・・
0個以上36個以下の 「おまんじゅう」 と 3個の 「仕切り」 がある。
この**「おまんじゅう」と「おまんじゅう」の間に「仕切り」を入れる。
ただし、「仕切り」と「仕切り」の間には1個も「おまんじゅう」が無くても構わないが、
10個以上「おまんじゅう」**があってはならない。
わかりにくいので図で説明すると
仕切りの入れる場所をきめるので、
おまんじゅうの個数 と 36-おまんじゅうの個数 の小さいほうの数をAとすると、
_{A+3}C_{3}
で 仕切り方の通りの数が出る
と思うじゃん？
答えは 「出ないです」
なぜなら
4つ0-9の数字を選ぶ(同じ数を選んでもよい)通りは、
10＾4=10000通り
存在します。
しかし、
_{A+3}C_{3}
で答えを求めると、
2\sum_{A=0}^{17} (_{A+3}C_{3})=2(1+4+10+20+35+56+84+120+165+220+286+364+455+560+680+816+969+1140) ....①\\
_{18+3}C_{3}=1330....②\\
①+②＝13300
つまり 謎の組み合わせが 3300通り存在します。
この謎の組み合わせは
仕切りで区切った空間に10個以上**「おまんじゅう」**がある時。
これを数え内にはどうすればいいのだろう?
考え方をお待ちしております！
もちろん、執筆者本人も熱血考え中です。
アイデアが出次第、小噺2にでもそのアイデアを出したいと思います。
乞うご期待を！(誰得)
↓小噺2書きました！