2010/11/30

5つのビリヤード玉の問題(4)

(これまでの記事のリンク)

5つのビリヤード玉の問題
5つのビリヤード玉の問題(2)
5つのビリヤード玉の問題(3)

 

さて、以下の問題について、n 個の場合についてそろそろ考えてみましょう。

「…五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。たまには、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな?」


笑わない数学者 MATHEMATICAL GOODBYE (講談社文庫)
笑わない数学者 MATHEMATICAL GOODBYE (講談社文庫)

 

n 個の場合の問題とするには「1 から 21 までのすべての数ができるようにしたい」という部分も変えなければなりません。

「1 から 21 までまで」としたのは、玉の取り方が 21 通りあるからです。

では、n 個のビリヤード玉での玉の取り方は何通りあるかというと、n(n-1)+1 通りとなります。

で、問題を n 個のビリヤードの玉として置き換えると、以下のようになります。

「n 個のビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。たまには、それぞれナンバ(自然数)が書かれている。さて、この n 個の玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、n個全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1 から n(n-1)+1 までのすべての自然数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな?」

 

このままでは、わからないため、まずは n=1 から順に確認してみたいと思います。

 

n=1 の場合

これは答えは①のみです。

以下、「①」は「1と書かれたビリヤードの玉」とします。

(左端の数字は足し合わせた合計の数で、右側にビリヤードの玉の取り出し方)

 

n=2 の場合

2 個のビリヤード玉を使って、1 から 3 をつくることになります。

これも答えは①②となります。

  1. ①②

 

n=3 の場合

3 個のビリヤード玉を使って、1 から 7 をつくることになります。

これはちょっと考えればわかります。

①②④ですね。

  1. ①②
  2. ④①
  3. ②④
  4. ①②④

 

n=4 の場合

4 個のビリヤード玉を使って、1 から 13 をつくることになります。

自分で解いてはいないのですが、どうやらこの場合は答えが 2 通りあるようです。

[答1]①③②⑦

  1. ①③
  2. ③②
  3. ①③②
  4. ⑦①
  5. ②⑦
  6. ②⑦①
  7. ⑦①③
  8. ③②⑦
  9. ①③②⑦

[答2]①②⑥④

  1. ①②
  2. ④①
  3. ④①②
  4. ②⑥
  5. ①②⑥
  6. ⑥④
  7. ⑥④①
  8. ②⑥④
  9. ①②⑥④

 

n=5 の場合

もともとの問題で、5個の玉を使って、1から21までをつくることになります。

答えは①③⑩②⑤

  1. ①③
  2. ⑤①
  3. ②⑤
  4. ②⑤①
  5. ⑤①③
  6. ②⑤①③
  7. ⑩②
  8. ③⑩
  9. ①③⑩
  10. ③⑩②
  11. ①③⑩②
  12. ⑩②⑤
  13. ⑩②⑤①
  14. ⑤①③⑩
  15. ③⑩②⑤
  16. ①③⑩②⑤

 

n=6 の場合

6 個のビリヤード玉を使って、1 から 31 までをつくることになります。

どうやらこの解も複数の解があるようです。

(確認作業割愛・・・)

[答1]①⑦③②④⑭

[答2]①③⑥②⑤⑭

[答3]①③②⑦⑧⑩

[答4]①②⑤④⑥⑬

[答5]①②⑦④⑫⑤

 

n=7 の場合

7 個のビリヤード玉を使って、1 から 43 の数字をつくることになります。

驚くべきことに(!?)、この場合は解なしのようです。

余談ですが、森博嗣さんの『すべてがFになる』で「7は孤独な数字」と言われていたことを思い出します。

笑わない数学者 MATHEMATICAL GOODBYE (講談社文庫)
笑わない数学者 MATHEMATICAL GOODBYE (講談社文庫)

 

ちなみに、n=4、6、7 の場合の解答については、こちらのサイトを参照しました。

ありがとうございます。

Blog 2pi「『笑わない数学者』のビリヤード問題」

 

5つのビリヤード玉の問題(3)

さらに続きです。

一応、前回までのリンクを貼っておきます。

5つのビリヤード玉の問題
5つのビリヤード玉の問題(2)

 

さて、今回は(b)「1」と「2」が隣り合っていない場合を考えていきます。

 

(b)「1」と「2」が隣り合っていない場合(すなわち、C=2 or D=2 の場合)

「1」と「2」が隣り合っていないことより、「3」が必要となります。

従って、5個の自然数の組み合わせは、

{1、2、3、4、11}{1、2、3、5、10}{1、2、3、6、9}{1、2、3、7、8}

の4通りです。

ここでの並べ方ですが、「1」と「2」が隣り合っていないことから、とりあえず A=1、C=2 と置きます。

そして、「3」の位置で場合分けして考えます。

つまり、

(b1)B=3 の場合

(b2)D=3 の場合

(b3)E=3 の場合

です。

(b1) B=3 の場合

この場合、A=1、B=3、C=2 と並ぶため、「1」と「3」を足し合わせた「4」、「3」と「2」を足し合わせた「5」は不要となります。

また、「1」「3」「2」を足し合わせた「6」も不要です。

従って、残る組み合わせ{1、2、3、7、8}について考えます。

この組み合わせの並べ方は、

1・3・2・7・8

1・3・2・8・7

の2通りです。

足し合わせて9となる組み合わせが存在するのは、

1・3・2・7・8

の方だけですが、ここには 2+7=9、8+1=9 とダブってしまいます。

従って、ボツ。

(b2)D=3 の場合

この場合、1・B・2・3・E と並ぶため、「5」は不要となります。

また、「4」を入れると「1」と隣り合ってしまうため、「4」が入るとボツ。

(2+3=5 の組み合わせがあるのに、1+4(あるいは4+1)=5 を作るとダブってしまう。)

しかし、「4」が入れられないとすると、「1」と「3」が隣り合っていないため、足し合わせて4を作ることができなくなります。

従って、D=3 もボツ。

(b3)E=3 の場合

この場合、1・B・2・D・3 と並ぶため、「4」は不要となります。

従って、残る組み合わせは

{1、2、3、5、10}{1、2、3、6、9}{1、2、3、7、8}

の3つです。

しかし、「1・B・2・D・3」の並び方で、複数個を取り出して足し合わせると5になる組み合わせは存在しません。

足し合わせて5となるためには、1+4 か 2+3 (あるいは逆の 4+1 か 3+2)です。

「4」は不要ですし、「2」と「3」は隣り合っていないため、複数個で足し合わせるのではなく、1個を取り出して5とするために「5」が必要となります。

従って、5個の自然数の組み合わせは{1、2、3、5、10}が残ります。

このときの並べ方ですが、

1・5・2・10・3

1・10・2・5・3

の2通りとなります。

そして、足し合わせて6となるような並びが存在するのは、

1・5・2・10・3

の1つです。

あとは7以降の検証で、これは最初の記事でやりましたので、ここでは割愛します。

 

一番最初の記事では、「①③⑩②⑤」と解答していますが、これは単に時計回りに並べたか、反時計回りに並べたかの違いです。

 

さて、この考え方で n 個のときの一般解が出せるのか・・・。

やはり、不安です・・・。

5つのビリヤード玉の問題(2)

前回の続きです。

気が向いたら…、と締めくくっていたのですが、小説内ではさらに以下のようなやり取りがあります。
…天王寺博士の宿題について少し議論した。問題は玉の数が五個だったが、四個の場合も問題が成立する。では、六個はどうか、n個ではどうか、という話だった。
こちらについても、解答や解説はありません。

この問題について、n個の一般解を求めることができるのか?

難題です。

少しずつ考えてみましょう。

(以下、この記事内で解けるかどうかはわかりません。書きながら考えています。)


まずは、五つのビリヤード玉の問題を自分の考えを整理しながら解いていきたいと思います。

(以下、問題の再掲)
「…五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな?」
とりあえず分けて、数学的な表現にしてみます。

(横書きなので漢数字を数字に置き換えしています。)

  • 5個の異なる自然数を、真珠のネックレスのように、リングでつなげる。
  • この5個の自然数のうち、隣どうし連続したものしか取れない(=離れているものは取れない)。
  • この条件で取った自然数を足し合わせて、1から21のすべての自然数ができるようにしたい。
  • 5個の自然数は何か、そしてどのように並べるか?
となると思います。


まず考えることは、5個の異なる自然数を環状に並べ、隣どおし連続したものしか取れないという条件で、取り方は何通りあるか?です。

とりあえず、環状に並べた5つの自然数をそれぞれA・B・C・D・Eと置きます。

  • 1個ずつ取る取り方は、「Aを取る」「Bを取る」…「Eを取る」の5通り。
  • 2個ずつ取る取り方は、「ABを取る」「BCを取る」…「EAを取る」の5通り。
  • 3個ずつ取る取り方は、「ABCを取る」「BCDを取る」…「EABを取る」とこれも5通り。
  • 4個ずつ取る取り方は、「ABCDを取る」「BCDEを取る」…「EABCを取る」とこれも5通り。
  • 最後5個すべてを取る取り方は1通り。
となり、全部で 5+5+5+5+1=21(通り) となります。

この21通りが、1から21のすべての自然数となるようにしたい、ということになるため、

A+B+C+D+E=21

が成り立つことになります。

また、「1」は必ず必要であるため、とりあえず

A=1

と置きます。

環状につながっているので、どこに「1」を置いてもいいのですが、まあ考えやすいところで。

 

また、「2」も必ず必要になります。

なぜなら、「2」を2つ(以上)の自然数を足し合わせて作るためには、「1+1」しかないためです。

「1」を2つ使ってしまうと、21通りの中で、足し合わせて1から21を作ることができなくなってしまいます。

ただし「2」は、B・C・D・Eのどれにあたるかは、まだわかりません。

 

しかし、5個の自然数の合計は21で、5個の自然数のうち2個は「1」と「2」です。

まずは、残り3個の自然数にはどのような組み合わせがあるか考えてみましょう。

残り3個の自然数の合計は 21-(1+2)=18 となるため、3以上の異なる3個の自然数の組み合わせは、

{3、4、11}{3、5、10}{3、6、9}{3、7、8}

{4、5、9}{4、6、8}

{5、6、7}

の7通りです。

 

ここまでで、ひとまずもとに戻ります。

今、「2」の場所は決めずに考えていましたが、「2」の場所を場合分けして考えてみます。

場合分けは、

(a)「1」と「2」が隣り合っている場合(すなわち、B=2 or E=2 の場合)

(b)「1」と「2」が隣り合っていない場合(すなわち、C=2 or D=2 の場合)

です。

 

(a)「1」と「2」が隣り合っている場合(すなわち、B=2 or E=2 の場合)

「1」と「2」が隣り合っていることより、「3」は不要となります。

従って、残り3個の自然数の組み合わせは、

{4、5、9}{4、6、8}{5、6、7}

の3通りになります。

さらに、「1」と「2」が隣り合っていて、「3」が不要となれば、足し合わせて4となる組み合わせを作る組み合わせができないので、「4」が必要になります。

従って、残る組み合わせは、

{4、5、9}{4、6、8}

の2通りです。

さらに足し合わせて5を作るには、「1」「2」が隣り合っていて「4」がどこかに存在することになるため、ここでも場合分けをしてみます。

(a1)「5」が存在する場合

(a2)「5」が存在しない場合

(a1)「1」と「2」が隣り合っていて、「4」と「5」が存在する場合

ここでは、5個の自然数は{1、2、4、5、9}になります。

これの並べ方ですが、A=1、B=2 と置くと、Eが「4」となることはありません。

EとAを取った時に足し合わせると5になるからです。

従って、並べ方は、

1・2・4・5・9

1・2・4・9・5

1・2・5・4・9

1・2・9・4・5

の4通り。

では次に足し合わせて6となる組み合わせが存在するのはどれになるかというと、

1・2・4・5・9

1・2・4・9・5

1・2・9・4・5

の3通りに減ります。

さらに足し合わせて7となる取り方が存在するのはどれかとなると、

1・2・4・5・9

1・2・4・9・5

の2通り。

さらに足し合わせて8となる取り方があるものは

1・2・4・9・5

の1通りとなります。

しかしこの並べ方では、足し合わせて10とする取り出し方が存在しません。

したがって、ボツ。

(a1)「1」と「2」が隣り合っていて、「4」は存在し、「5」は存在しない場合

ここでは、5個の自然数は{1、2、4、6、8}になります。

これの並べ方ですが、A=1、B=2 と置くと、E=4となります。

なぜなら、足し合って5を作るためには、「3」がないため、1+4 の組み合わせしかないからです。

従って並べ方は、

1・2・6・8・4

1・2・8・6・4

の2通り。

足し合って7となる取り方はどちらもあり。

では、足し合って9となる取り方は…となると、

1・2・6・8・4

の1通り。

ですが、10が作れないためボツ。

つまりは、「1」と「2」は隣合うことはない、ということになります。

 

こうやって、今度は場合分け(b)に入るわけですが、疲れたので今度にします(^-^;)

果たしてこのような考え方で、一般解が導けるのでしょうか?

不安が残ります…

 

【追記】

続きを書きました。

5つのビリヤード玉の問題(3)

2010/11/28

5つのビリヤード玉の問題

森博嗣さんの『笑わない数学者』の中で、数学者天王寺博士が出す問題の一つに、以下の問題があります。
「…五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな?」
この小説内では、解答も解法も載っておらず、読んだ当時に力づくで解いた記憶があります。

最近『笑わない数学者』を再読し、この問題を発見(+自分の出した答えを本に書き込みしていた)ので、答え合わせをしてみたいと思います。


※小説のストーリーには関係ありませんが、未読の方ご注意ください。


自分の出した解答は、①③⑩②⑤を順に並べてネックレスを作る、というものです。

以下、本当に1から21まで取り出せるのか、の確認。

  1. ①を取り出す
  2. ②を取り出す
  3. ③を取り出す
  4. ①③の2個を取り出す
  5. ⑤を取り出す
  6. ⑤①の2個を取り出す
  7. ②⑤の2個を取り出す
  8. ②⑤①の3個を取り出す
  9. ⑤①③の3個を取り出す
  10. ⑩を取り出す
  11. ②⑤①③の4個を取り出す
  12. ⑩②の2個を取り出す
  13. ③⑩の2個を取り出す
  14. ①③⑩の3個を取り出す
  15. ③⑩②の3個を取り出す
  16. ①③⑩②の4個を取り出す
  17. ⑩②⑤の3個を取り出す
  18. ⑩②⑤①の4個を取り出す
  19. ⑤①③⑩の4個を取り出す
  20. ③⑩②⑤の4個を取り出す
  21. ①③⑩②⑤の5個すべてを取り出す


とりあえず、答えとしては合っていました(^-^)v


さて、この解き方の方が気になるのですが、私は当時力ずくで、場合分けしつつ考えました。

かなりの時間がかかりました。。。


まず、考えたことは、
  • 絶対に①と②の玉は必要であること
  • 玉の取り出し方は21通りになるため、五つの玉の合計は21になること
  • 足して10になるところまで考えられれば、後はその反対になること
  • ということは①②は決定しているから、残り三つの玉の合計は18になること
  • ・・・など

と、問題文から思いつく限りの条件を列挙してから、

(1)①と②が隣り合っている場合

(2)①と②が隣り合ってない場合

と場合分けして考えていきました。


もっと、スマートな解法があるかと思いますので、考えてみたいと思います。

気が向いたら・・・(^-^;)

笑わない数学者 MATHEMATICAL GOODBYE (講談社文庫)
笑わない数学者 MATHEMATICAL GOODBYE (講談社文庫)

【追記】

続きを書きました。
5つのビリヤード玉の問題(2)

2010/11/21

るみてえ変を点視

 

。んせまれしもかるあが見発るな異か何、とる見てえ変を点視

。すまいでん読を字文に右らか左、に下らか上はちた私、通普

。すまいてい書に左らか右、に上らか下は事記のこ