今回はなかなか厄介でしたよね!

今回の組み合わせの問題は、非常に厄介だと思います。
けれどもその答えは、想像つかないような綺麗な数になってくれるのです。
ということで、今回はいつもと少し違った流れで解答を書いていきます。

まず今回の問題の解答から。正解は512通りです。
あまり数字に馴染みが無い方には、これのどこが綺麗な数字なのかと思うでしょうが、
実はこれは2^9(2の9乗)の値なのです。

私がこの問題に挑戦したとき、まずは最初の数字を少ないもので実験しました。
「0、1、2」とすると、012・102・120・210の4通り。
「0、1、2、3」とすると、0123・1023・1203・1230・2103・2130・2310・3210の
全部で8通り。
「0、1、2、3、4」とすると、(具体例は省略します)全部で16通りが出てきたのです。
つまり、3つの数字ならば2^2通り、4つの数字ならば2^3通り、5つの数字ならば2^4通りとなったのです。
ということは、この問題の答えは2^9通りと予想ができますね。

そこで少し置き換えを考えました。
例えば、「0、1、2、3、4」の場合に考えられる、23104という数を考えます。
これは数直線

  0--1--2--3--4

を考えた時に、「2」をスタートとしてどういう数を並べたものなのか。
これは条件から、2と隣り合っている数の左右どちらかを選ぶことになります。
そうやって選んだ数字の塊を考え、次の桁も塊と隣り合っている数の左右どちらかを選ぶ、と考えるのです。
(以下混乱を防ぐために、数直線での左右を←→で表します)

こうなると、1つの数字を作る作業が、塊を少しずつ大きくしていくイメージができるのです。
ただし限りなく大きく広げていくわけにはいかない。最小は0、最大は4という条件が付いている。
そこで「塊が広がる向きとできる数とを関連付けた」のです。
つまり、2から→に進み3を選ぶ。次に←に進み1を選ぶ。次に←に進み0を選ぶ。最後に→に進み4を選ぶ。
こういう操作によって、23104という数ができる、と見てやったのです。

こうなるとだんだん、よく見る問題のレベルになってきます。
2を一番最初に選んだ場合、その後塊を広げる(数を選んでいく)向きは、←に2回、→に2回となります。
そこでこの場合の数は、4_C_2=6通りとなるのです。(n_C_rは二項係数)
この考えでいくと、0から始まる数は、0から→に4回進むことになるので、その場合は1通り。
1から始まるときは、←が1回、→が3回なので、4_C_1=4通り。
3から始まるときは、←が3回、→が1回なので、4_C_3=4通り。
4から始まるときは、→が4回なので1通り。
以上を合計すると、ちゃんと16通りと求められるのです。

この決め方から明らかに、これは次の計算をしていることになります。

 4_C_0+4_C_1+4_C_2+4_C_3+4_C_4=(1+1)^4

そう、これは二項定理を応用した、二項係数の和ですね!

この塊の作り方は幅の広さには影響せず、一般化が可能です。そこで10個の数字の場合、
←と→が合計9回存在することになり、それらを並べる総数を考えることで、

 9_C_0+9_C_1+・・・+9_C_9=(1+1)^9=512

と計算できるのです。

ふぅ・・・とっても大変な計算ですよね。でも何気ない数ならべが、二項定理まで関係することになり、
また結果が2のべきになっているというのは、非常に美しい関係と言えますよね!

ところが、この問題を見つけた本によると、より簡潔でとんでもない解法が紹介されていました。
まず少し考えると、数を作った時に一番右にある数字は0か9になることがわかります。
その一つ左の数は、それまでに使われていない数の中から、最も大きな数か最も小さい数が入ります。
これは数直線で考えた時、選ばれていない数の集合が小さいグループと大きいグループに分かれていることから
得られることなのです。つまりその2通りのどちらかになっているのです。
さらにその左にある数は、同様に使われていない数から最大か最小が入っている。
これを繰り返していくと、一番右が2通り、そして左になるたびに2通りずつが選ばれていきます。
そして一番左のみ、最後に残った1通りの数しか入りません。
このことから、2^(10-1)=512通りとなるのです。

問題の条件では左から数を作っていくのに、計算では右から考える・・・なんてすごい解法ですよね!
でもこれは、場合の数を考えるときには「条件が厳しいところから計算」という、非常にオーソドックスな
解法とも言えるのです。

ということで、非常に難しい問題なのですが、非常に楽しい問題なんですね。

今回も、jay gatsbyさんから解答をいただいています。
自信が無い・・・とのことでしたが、見事512通りという答えを出されています。
いやはや本当に素晴らしいことです!

ということで、またいろいろな問題を見つけていこうと思いますので、よろしくおねがいします。

当ブログは、 にほんブログ村受験塾・進学塾豊前情報のランキング、
BLOG RANKING高校受験大学受験塾教育のブログランキングに参加しています。
クリックして応援して頂けると励みになります。もしよろしかったらお願いします。

0 Comments

  1. jay gatsby

    塊で考える数の作り方とても面白いですね。
    一度読んだだけではピンと来ませんでしたが、なるほどです!

    簡潔でとんでもない解法の方はこれまたあざやかですね。
    「最も大きな数か最も小さい数が入ります」の根拠を理解する
    のにちょっと戸惑いましたが。

    毎度直感で考えているもので、今回の問題はたね明かしを見る
    ほうが楽しい問題でした。

    だんだん年とともに直感も鈍くなり、nabeさんの解説を見るのが楽しみです。

    Reply
    1. nabe (Post author)

      いつもコメントありがとうございます。また、ここのところお返事を返せずに申し訳ありませんでした。

      私もですね、たまたま大学数学の初歩の本を読んでいたので、
      「デデキントの切断」のイメージからこの解法に行き着いたのです。
      だからそれが無かったら・・・この問題もお蔵入りだったでしょうね!

      とは言え、お褒めの言葉を頂き、本当にありがとうございます。
      これからも楽しんでもらえるような、問題や解答を見つけていきたいと思います。

      ・・・というか、この過程を私も楽しんでいますからね!

      それでは今後とも、どうぞよろしくお願いいたします。

      Reply
  2. ラルゴ

    おもしろうそうな問題だったのですが、入試前日の12日の月曜日まで連日、
    受検生の相手をしていましたので、じっくりと取り組む時間がありませんでした。
    残念です。
    次の週末は、今度は新年度の準備で にゃんにゃこ舞い なので、また見送りかな…

    Reply
    1. nabe (Post author)

      コメント本当にありがとうございます。

      同業なんですから、今の時期の大変さはよく分かりますよ。
      ただうちはまだ、生徒の数が少ないからこういうブログを書く余裕があって。
      もしかしたら、生徒が激増して更新のペースが落ちるのかも・・・いや、意固地になって
      続けるだろうなぁ、私は。

      ということで、無理せずお互いがんばりましょう!

      Reply

Leave a Comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

Optionally add an image (JPEG only)