完全差集合のつくり方

Cyclic Difference Sets - by Kris Coolsaetを眺めていると、「How to make perfect CDSs（完全差集合のつくり方）」と題されたところがあったので、気になって読んでみた。それまでのページをしっかりと読んでいないので、理屈がわからないところもあるが、おおよそ以下の内容である。

まず、ひとつの数列をつくる。初項 \( 0 \) からはじまり、第2項も \( 0 \) 、第3項は \( 1 \) 、第4項以降は前の3項を足した数でつくる数列である。具体的に書くと、次の数列である。
$$
0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 4 \quad 7 \quad 13 \quad 24 \quad 44 \quad 81 \quad 149 \quad 274 \quad 504 \quad 927 \quad \cdots
$$
そして、この数列を \( mod \ p \) で書く。\( p \) は素数である。たとえば \( mod \ 3 \) で、上の数列は次のようになる（ \( mod \ 3 \) は、\( 3 \) で割った余りのこと）。この数列で、\( 0 \) が2連続で続いているところの間に注目する。以下の数列では、初項と第2項で \( 0 \) が2連続し、次は14項目と15項目で \( 0 \) が2連続している。なので、この数列の初項から13項目までに注目する。
$$
0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 1 \quad 1 \quad 1 \quad 0 \quad 2 \quad 0 \quad 2 \quad 1 \quad 0 \quad 0 \quad \cdots
$$
この数列の \( 0 \) の部分に印（下図では \( \sharp \) ）をつけて、印のついたナンバを見る。下図では、印のついたナンバは \( 0, 1, 8, 10 \) である。
$$
\begin{array}{lcrrrrrrrrrrrrrl}
sequence &:& 0 & 0 & 1 & 1 & 2 & 1 & 1 & 1 & 0 & 2 & 0 & 2 & 1 & ( 0 \quad 0 \ \cdots ) \\
marks &:& \sharp & \sharp & & & & & & & \sharp & & \sharp & & & \\
numbering &:& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & (13)
\end{array}
$$
この集合 \( \{ 0, 1, 8, 10 \} \) が、\( mod \ 13 \) での完全差集合となるということだ。理屈はあるようだが、僕はまだ理解していない。

最初につくった数列については、「linear recurrences of degree three」（3次の線形再帰？）と呼ばれている。フィボナッチ数列というものがあるが、フィボナッチ数列は、最初の2項が \( 0, 1 \) で、第3項以降の項はその直前の2つの項の和となっている数列である。最初につくった数列は、このフィボナッチ数列と似ており、最初の3項が \( 0, 0, 1 \) で、以降はその直前の3つの項の和となっている数列である。Wikipedia「フィボナッチ数」の項を見ていると、「トリボナッチ数（数列）」という名称があった。この数列の一般項を \( T_n \) とすると、
$$
T_0 = T_1 = 0, \qquad T_2 = 1 \\
T_{n+3} = T_n + T_{n + 1} + T_{n + 2} \qquad ( n \geqq 0)
$$
と表わされる。

最初の例では、素数 \( 3 \) を法としたトリボナッチ数列から、\( 13 \) を法としたサイズ \( 4 \) の完全差集合をつくった。一般的には、素数 \( p \) を法としたトリボナッチ数列から、\( p^2 + p + 1 \) を法としたサイズ \( p+1 \) の完全差集合がつくれるということだ。

これまで、5つのビリヤード玉の問題を考えるにあたり、完全差集合に行き当たった。5つのビリヤード玉の問題に関係する完全差集合としては、\( 21 \) を法とする、サイズ \( 5 \) の完全差集合である。単純に考えると、サイズ \( 5 \) の完全差集合をつくるなら \( p \) を \( 4 \) とすることになるが、\( 4 \) は素数ではない。しかし、以前に確認したTweetの中に、「\( n-1 \) が素数か素数の冪ならば、\( mod \ n(n-1)+1 \) で完全差集合になる \( \{ a_1, a_2, …, a_n \} \) が存在することを、Singer が証明している」というものがあった。\( 4 \) は素数ではないが、素数の冪である（ \( 4 = 2^2 \) ）。また、\( p = 4 \) とすると、\( p^2 + p + 1 = 21 \) となる。同様の方法で、\( 21 \) を法とする、サイズ \( 5 \) の完全差集合はつくれるだろうか。

トリボナッチ数列を \( mod \ 4 \) で表すと以下のようになる。
$$
0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 0 \quad 3 \quad 1 \quad 0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 0 \quad 3 \quad \cdots
$$
第9、10項で0が連続する。やはりこの方法は \( p \) が素数であることが必要みたいだ。 そしてサイズ \( 5 \) の完全差集合をつくる方法は、また違うということだろう。

ビリヤードの問題再考（10）巡回差集合、完全差集合

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えているなかで、「完全差集合」「巡回差集合」という言葉に出会いました。今回は、完全差集合、巡回差集合とはどのようなものなのかを確認したいと思います。

今回確認するのは、前回に紹介したtweet中にあった英語のサイトです。

Cyclic Difference Sets - by Kris Coolsaet

この中の Cyclic difference sets の内容を確認します。基本的には英文を引用し、意訳するところもあるかと思いますが、日本語に訳していきながら進めていきます。

では、早速。

A cyclic difference set (CDS) modulo n is a set of s positive numbers {a1=0,a2,a3,...,as} less than n, with the property that all differences ai-aj modulo n for i not equal to j, are different. The number n is called the modulus of the CDS and s is the size of the CDS. The set itself is usually written as

0 a1 a2 ... as (n)

where 0 < a1 < a2 < ... < as.

（意訳）
法 \( n \) の巡回差集合（CDS: cyclic difference set）とは、\( n \) より少ない正の整数の集合 \( \{ a_1 = 0, a_2, a_3, \cdots, a_s \} \) で、すべての差 \( a_i - a_j ( \bmod n, \ i \neq j ) \) が異なるという特性をもっています。\( n \) をCDSの法、\( s \) をCDSのサイズといいます。この集合は通常次のように書きます。
$$
0 \ a_1 \ a_2 \ \cdots \ a_s \ (n)
$$
ここで、\( 0 \lt a_1 \lt a_2 \lt \cdots \lt a_s \) です。

英文内での集合の要素である a1 などについて、意訳では添字として表現しました。数学用語の訳語はそれっぽいものを採用。意訳での \( a_i - a_j ( \bmod n, \ i \neq j ) \) という表記は \( a_i - a_j ( \bmod n ) \ ( i \neq j ) \) と書いたほうがいいのかもしれません。意味としては、\( \bmod n \) での引き算で、\( a_i \neq a_j \) ということです（よね？）。size を単にサイズと訳しましたが、専門用語があるかもしれません。

OK, apart from some terminology, we have not really encountered anything new. Consider the 21-bead necklace from the previous page, written as a numerical sequence:

0 5 6 9 19 (21)

Here, the cyclic difference set is {0,5,6,9,19} ({a1,...,a5} in the definition), the modulus is 21 (n in the definition) and the size is 5 (s). By the difference of two numbers a and b 'modulo 21' we mean a-b if a is not less than b, or else a-b+21. Hence, the requirement that no two differences `modulo 21' are the same, means that all non-diagonal elements in the difference table must be different.
Therefore, mathematically speaking, cyclic difference sets are the same as weird necklaces, whichever terminology you prefer.

（意訳）
用語は別として、何も新しいことに出会ったわけではありません。前のページの21個の玉のネックレスを思い出してみましょう。前ページのネックレスは数列として次のように書けます。

0 5 6 9 19 (21)

ここで、巡回差集合は \( \{ 0,5,6,9,19 \} \) （定義では \( \{ a_1, \cdots, a_5 \} \) ）で、法は \( 21 \) （定義での \( n \) ）、サイズは \( 5 \) （定義での \( s \) ）です。\( \bmod 21 \) での2つの数 \( a \) と \( b \) の差というのは、\( a \geqq b \) ならば \( a - b \) を、\( a \lt b \) ならば \( a - b + 21 \) を計算することを意味します。よって、\( \bmod 21 \) での差が同じものはないということは、差の演算表のなかで対角線上にない要素がすべて異なっていなければなりません。したがって、数学的にいえば、巡回差集合は奇妙なネックレスと同じであるともいえます。

ちょっとこなれた日本語にはなっておらず、何となく意味がつかめるかなという意訳です。difference table を差の演算表としていますが、引用元のサイトではリンクが張られており、前ページに飛ぶようになっています。そこに（まだ読んでいませんが）演算表らしきものがあったので、差の演算表としました。\( \bmod 21 \) での演算表だと思われます。

ビリヤードの問題では、ネックレスのようにリング状につながったビリヤード玉として問題が提示されていました。いま参照している引用元のサイトではネックレスで例を挙げながら巡回差集合を説明しているのだと思われます。diagonalの意味は辞書をひいて「対角線」とあったので、演算表の対角線上にない（non-diagonal）としています。

引用元の前ページも確認したほうがよさそうですね。しかし、いまは後回しとして先に進みます。

As you may have noticed while trying to string your own weird necklaces, it is fairly easy to construct cyclic difference sets with large modulus and small size. For example:

0 1 10 100 1000 10000 ... 100000000000 (1000000000000)

The trick lies in constructing large sets with small modulus. We may ask the question again: is there a weird necklace with 5 yellow beads and less than 16 black beads? Or in other words, is there a cyclic difference sets of size 5 with modulus less than 21?

（意訳）
ネックレスをつける間に気づいたかもしれませんが、法が大きくサイズが小さい巡回差集合をつくることはとても簡単です。たとえば、（略）
法が小さい、大きな集合をつくるときにはトリックがあります。もう一度質問しましょう：5個の黄色い玉と16個より少ない黒い玉で作られたネックレスはありますか？　別の言葉でいえば、法が21よりも少ない、サイズが5の巡回差集合はありますか？

trick の訳がすぐに思いつかず、そのままトリックとしています。前ページでは、黄色い玉と黒い玉を使った例を挙げているようですね。ビリヤード玉の問題を考えているので、何となくの意味はわかります。

次に進みます。

To answer this question, we must have a closer look at the difference table. For size 5, this table has the following form:

0 * * * * (n)
* 0 * * *
* * 0 * *
* * * 0 *
* * * * 0

where the various stars correspond to different positive numbers. Now, the picture above contains 20 stars (count them!) and each star must hold a number greater than 0 and less than the modulus. In other words the modulus must be at least one more than the number of stars, in this case 20+1=21. The total number of beads in a necklace with 5 yellow beads must therefore be at least 21.

（意訳）
この質問に答えるために、差の演算表をもう少し詳しくみてみましょう。サイズ5の演算表は以下になります。
$$
\begin{array}{cccccc}
0 & * & * & * & * & (n) \\
* & 0 & * & * & * & \\
* & * & 0 & * & * & \\
* & * & * & 0 & * & \\
* & * & * & * & 0 &
\end{array}
$$
ここで \( * \) は異なる正の整数に対応します。いま、上の図には20個の \( * \) があり（数えたらわかる！）、そしてそれぞれの \( * \) は、0より大きく法より小さい数でなければなりません。別の言葉でいうと、法は \( * \) の数よりも少なくとも1は大きくなければなりません。このケースでは、\( 20+1 = 21 \) です。したがって、5個の黄色い玉のネックレスでの玉の総数は少なくとも21でなければなりません。

表をきれいにしてみました（笑）

This reasoning can be repeated for any size s. Indeed, the number of stars is s times s-1 (there are s rows of s-1 stars) and hence the modulus n is at least s^2-s+1. (We write s^2 to denote s squared.) The following table lists the various values of this number for given sizes s:

s | 4 5 6 7 8 9 10 11 12 13
-------------------------------------------------
s^2-s+1 | 13 21 31 43 57 73 91 111 133 157

So you see that our 13-bead necklace is the shortest possible for size 4 as well.
A CDS of size s for which the modulus is exactly s^2-s+1 (and hence the smallest possible) is called a perfect difference set. It has the added property that every number between 0 and the modulus can be found in the corresponding difference table.

（意訳）
この理屈は \( s \) がどんなサイズでもいえます。実際、\( * \) の数は、\( s ( s-1) \)個（ \( s-1 \) 個の \( * \) が \( s \) 列 ある）で、よって法 \( n \) は少なくとも \( s^2 - s + 1 \) です。次の表は、サイズ \( s \) が与えられたときの \( s^2 - s + 1 \) の値です。
$$
\begin{array}{c|rrrrrrrrrr}
s & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
s^2-s+1 & 13 & 21 & 31 & 43 & 57 & 73 & 91 & 111 & 133 & 157
\end{array}
$$
13玉のネックレスはサイズ4で最短であることがわかります。
法がちょうど \( s^2-s+1 \) であるサイズ \( s \) の巡回差集合（つまり、サイズ \( s \) で最小の法 \( s^2-s+1 \) である巡回差集合）を完全差集合と呼びます。完全差集合は、対応する差の演算表に、0と法の間のすべての数が現れるという特性があります。

完全差集合（perfect difference set）がでてきました。巡回差集合はすべての差が異なる数の集合、完全差集合はすべての差が異なり、かつ差が \( 0 \) より大きく法 \( n \) より小さいすべての数となる集合ということです。

たしかに、ビリヤードの問題と完全差集合は関係しそうです。では、どのように関係しているか。

引用文中に、サイズ5の巡回差集合の例として、\( \{ 0,5,6,9,19 \} \) が挙げられていました。この集合は、サイズ \( 5 \) で、法 \( 21 \) ですので、完全差集合となります。数列としては以下です。

\( 0 \quad 5 \quad 6 \quad 9 \quad 19 \quad (21) \)

一方、5個のビリヤード玉での問題での解答は以下でした。

\( 1 \quad 3 \quad 10 \quad 2 \quad 5 \)

注意深く眺めると、完全差集合の数列では、初項に5を足すと第2項に、第2項に1を足すと第3項に、第3項に3を足すと第4項に、第4項に10を足すと第5項に、第5項に2を足すと法である21になります。\( \bmod 21 \) では \( 21 \equiv 0 \) ですので、第5項に2を足すと初項になるともいえます。足していった数に、ビリヤード玉での問題の解答の数が並んでいます。

次回は、完全差集合の特性とビリヤード玉の問題について確認することにしましょう。

ビリヤードの問題再考（９）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えていて、少し煮詰まってきたので Web 上で \( n \) が大きいときの解の一覧がないかとか、解を見出すためのアルゴリズムにはどのようなものがあるのかを確認していたら、興味深いtweetのまとめを見つけました。

Togetter：『笑わない数学者』のパズルと目盛の節約，ゴロム分度器と完全差集合予想について

tweet内のリンク先で非公開となってしまっているところがあるのが少し残念ですが、話題として盛りだくさんな内容です。

簡単に興味あるところをピックアップして書くと、まずは考えているビリヤード玉の問題について、次のことが書かれていました。解もいくつか書かれていましたが、解の個数については明記されてはいませんでした。検証はまだしていません。

• \( n = 8 \) のときの解（解の個数についての明記なし）
  $$
  ( 1, 3, 8, 2, 16, 7, 15, 5 ）
  $$
• \( n = 10 \) のときの解（解の個数についての明記なし）
  $$
  ( 1, 2, 9, 8, 14, 4, 43, 7, 6, 10, 5, 24 )
  $$
• \( n = 14 \) までのうち，解が存在しないのは \( n = 7, 11, 13 \) 。この先の素数でも解は存在しない様子。
• \( n = 15, 16, 21, 22 \) でも解なしの模様。
• \( n = 30 \) のときの解（解の個数についての明記なし）
  $$
  ( 1, 35, 17, 21, 20, 56, 7, 19, 98, 5, 29, 3, 11, 2, 62, \\ 6, 60, 25, 15, 9, 18, 4, 8, 47, 10, 23, 28, 44, 99, 89 )
  $$

「隣接ではなく、球のすべての組み合わせの合計でやるなら、番号 \( 1, 2, 4, …, 2^{n-1} \) の \( n \) 個の球で \( 1 \) から \( 2^{n-1} \) までの全部の整数が作ることができる。2進法。」「輪にする（＝ \( mod \) で考える）だけで大きな \( n \) でも完全性が成り立つようになる」というのもおもしろいです。

また、目盛節約定規、ゴロム定規について。ゴロム定規というのを初めて知りましたが、Wikipediaにも載っていて、いま考えているビリヤード玉の問題ではリング状に並んだ状態で考えていますが、ゴロム定規はリング状ではなく直線上として並んでいるようなものですね。まだ詳しくは読んでいません。そして、モジュラーゴロム定規（ゴロム分度器）。詳しく書かれているわけではありませんが、ビリヤード玉の問題と同じような気がします。すでに定理となっているのか予想のままなのかはわかりませんが、「\( n-1 \) が素数か素数の羃のとき、かつそのときに限って、目盛数 \( n \) の完全ゴロム分度器が存在するであろう」という有名な予想があるようです。おそらくはこの予想のことを指していると思いますが、\( n \lt 1600 \) ではこの予想が成り立っていることが Evans & Mann によって確かめられているみたいです。

興味をひいたのは、完全差集合という言葉です。\( n-1 \) が素数か素数の羃ならば、\( mod \ n(n-1)+1 \) で完全差集合になる \( \{ a_1, a_2, …, a_n \} \) が存在することを、Singer が証明しているらしく、tweet主がビリヤードの問題と「完全差集合」と本質的に同じであることをつぶやいています。\( n(n-1)+1 \) はビリヤードの問題にも出てきました。

Wikipediaには「完全差集合」の項はありませんでした。「差集合」の項がありましたが、完全差集合での差集合とは違うものかと思われます。

tweetのリンク先には英語で書かれているサイトも含まれているので、ななめ読みしかしていませんが、完全差集合は英語で perfect different sets でしょう。もうひとつ、cyclic difference sets というのもリンク先にありました。日本語ではどうやら「巡回差集合」と訳されているようです。

完全差集合、巡回差集合について確認してみます。

ビリヤードの問題再考（８）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

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

5つのビリヤード玉 \( a_1, a_2, a_3, a_4, a_5 \) が、右回りでこの順につながっているとして、\( a_1 = 1 \) としたとき、21通りの取り出し方にどこまで大小関係がつけられるのかを考えています。前回は以下まで確認しました。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 & \lt & D_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] & \lt & D_5 \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] & \lt & D_4 \\
[ A_5 B_5 ] & \lt & C_5 & \lt & D_4
\end{eqnarray}
$$
上の不等式について、一応きれいにそろえるように書きましたが、もう少しわかりやすくならないでしょうか。

\( A_1 \) とか \( A_2 \) というような記号は、表記を短くするだけのために使っているのですが、もともとは、\( a_1, a_2, a_3, a_4, a_5 \) の組み合わせでつくったものです。いま \( a_1 = 1 \) として考えているので、\( a_1 = 1 \) を代入したそれぞれの記号は以下です。
$$
\begin{eqnarray}
A_1 &=& 1 \\
A_2 &=& a_2 \\
A_3 &=& a_3 \\
A_4 &=& a_4 \\
A_5 &=& a_5 \\\\

B_1 &=& 1 + a_2 \\
B_2 &=& a_2 + a_3 \\
B_3 &=& a_3 + a_4 \\
B_4 &=& a_4 + a_5 \\
B_5 &=& a_5 + 1 \\\\

C_1 &=& 1 + a_2 + a_3 \\
C_2 &=& a_2 + a_3 + a_4 \\
C_3 &=& a_3 + a_4 + a_5 \\
C_4 &=& a_4 + a_5 + 1 \\
C_5 &=& a_5 + 1 + a_2 \\\\

D_1 &=& 1 + a_2 + a_3 + a_4\\
D_2 &=& 20 \\
D_3 &=& a_3 + a_4 + a_5 + 1 \\
D_4 &=& a_4 + a_5 + 1 + a_2 \\
D_5 &=& a_5 + 1 + a_2 + a_3 \\\\

E &=& 21
\end{eqnarray}
$$
今度は、\( a_1, a_2, a_3, a_4, a_5 \) の大小関係が、どのように各要素に影響しているのかを見てみます。たとえば、\( a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5 \) だったならば、\( B_1 , B_2 , B_3 , B_4 , B_5 \) の大小関係はどうなるのか、ということです。

\( a_1 = 1 \) としているので、残りの \( a_2, a_3, a_4, a_5 \) の大小関係を仮定してすすめていこうと思いますが、4個の順列すべてを確認するのはさすがに骨が折れます（ \( 4! = 24 \) 通りあります）。なのでここでは、\( a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5 \) のときと、5つのビリヤード玉での解（ \( 1, 5, 2, 10, 3 \) ）のとき、つまり \( a_1 \lt a_3 \lt a_5 \lt a_2 \lt a_4 \) のときにとどめたいと思います。

まずは、\( a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5 \) のとき。

\( B_1 \) と \( B_2 \) では、\( a_2 \) が共通しているので、\( 1 \) と \( a_3 \) の大小関係が \( B_1 \) と \( B_2 \) の大小関係となり、\( B_1 \lt B_2 \) です。このように続けると、\( B_2 \lt B_3 \)、\( B_3 \lt B_4 \)、\( B_5 \lt B_4 \) がわかります。ひとまずまとめた不等式を書くと、\( B_1 \lt B_2 \lt B_3 \lt B_4, \ B_5 \lt B_4 \) です。さて、\( B_5 \) がどこに入るかですが、\( B_1 \lt B_5 \) はわかりますがパッと見ではわかりません。ひとまず現在の状況でまとめておきます。
$$
\begin{array}{ccccc}
B_1 & \lt & B_2 \lt B_3 & \lt & B_4 \\
B_1 & \lt & B_5 & \lt & B_4
\end{array}
$$
同様に \( C_1 \) から \( C_5 \) を見ると、
$$
\begin{array}{ccccc}
C_1 & \lt & C_2 & \lt & C_3 \\
C_1 & \lt & C_5 \lt C_4 & \lt & C_3
\end{array}
$$
\( D_1 \) から \( D_5 \) では、
$$
\begin{eqnarray}
D_1 \lt D_5 \lt D_4 \lt D_3 \lt D_2
\end{eqnarray}
$$
です。

\( D \) 系列（と勝手に呼びますが）は、\( A \) 系列のいわば逆の関係です。\( a_1, a_2, a_3, a_4, a_5 \) で\( A \) 系列、つまり1個の要素を取るということは、4個の要素を残すことになります。逆も然りです。いま\( A \) 系列の大小関係を決定させているので、\( D \) 系列の大小関係も決定しています。一方、\( B \) 系列と\( C \) 系列は（これも逆の関係です）、大小関係が決定しておりません（決定できるのに、僕が決定させられていないだけかもしれませんが……）。

では、\( a_1 \lt a_3 \lt a_5 \lt a_2 \lt a_4 \) のときはどうでしょうか。

まずは \( B \) 系列をみてみます。
$$
\begin{eqnarray}
B_5 \lt B_1 \lt B_2 \lt B_3 \lt B_4
\end{eqnarray}
$$
続いて \( C \) 系列。
$$
\begin{eqnarray}
C_1 \lt C_5 \lt C_4 \lt C_3 \lt C_2
\end{eqnarray}
$$
\( D \) 系列。
$$
\begin{eqnarray}
D_5 \lt D_3 \lt D_1 \lt D_4 \lt D_2
\end{eqnarray}
$$
となりました。

\( a_1 \lt a_3 \lt a_5 \lt a_2 \lt a_4 \) のときというのは解答のときなので、決定しても不思議ではないのですが、このメカニズムというか、本質というか、それが僕にはまだわかっていないようです。

ビリヤードの問題再考（７）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

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

5つのビリヤード玉 \( a_1, a_2, a_3, a_4, a_5 \) が、右回りでこの順につながっているとして、\( a_1 = 1 \) としたとき、21通りの取り出し方にどこまで大小関係がつけられるのかを考えています。

使っている記号の意味については前回を確認してください。

\( B_1 \) を見ると、\( B_1 = 1 + A2 \) ですので、\( A_2 \lt B_1 \) となり、さらに \( A_2 \) と \( B_1 \) の差が1ですので、間に何も入らないという意味で \( [ A_2 B_1 ] \) と書こうというのが前回までのところです。ひとつひとつ確認しながら順に大小関係を確認していこうと思います。\( B_1 \) について、当然 \( 1 \lt B_1 \) がいえますが、\( 1 \lt B_1 \) や \( B_1 \lt 13 \) などはここでは省いていきます。

さて、\( B_2 \) を見ると、\( B_2 = A2 + A3 \) ですので、明らかに \( A_2 \lt B_2 \) 、\( A_3 \lt B_2 \) です。ところで \( [ A_2 B_1 ] \) ですので、 \( A_2 \lt B_2 \) から、\( [ A_2 B_1 ] \lt B_2 \) がいえます。

\( B_3 \) を見ると \( A_3 \lt B_3 \) 、\( A_4 \lt B_3 \) です。

また \( B_4 \) からは \( A_4 \lt B_4 \) 、\( A_5 \lt B_4 \) がいえます。\( B_5 \) を見ると、\( B_1 \) のときと同様に、\( [ A_5 B_5 ] \) がいえます。
\( A_5 \lt B_4 \) と \( [A_5 B_5] \) より、\( [A_5 B_5] \lt B_4 \) です。これまでをまとめると以下です。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & B_2 \\
A_3 & \lt & B_2 \\
A_3 & \lt & B_3 \\
A_4 & \lt & B_3 \\
A_4 & \lt & B_4 \\
[A_5 B_5] & \lt & B_4
\end{eqnarray}
$$
続いて \( C_1 \) から \( C_5 \) を見ます。

\( C_1 \) より、\( B_1 \lt C_1 \) と \( [ B_2 C_1 ] \) がいえます。つまり、\( B_1 \lt [ B_2 C_1 ] \) です。上のまとめた不等式に追加していきます。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] \\
A_3 & \lt & B_3 \\
A_4 & \lt & B_3 \\
A_4 & \lt & B_4 \\
[ A_5 B_5 ] & \lt & B_4
\end{eqnarray}
$$
\( C_2 \) は、\( B_2 \lt C_2 \) と \( B_3 \lt C_2 \) です。同様にまとめた不等式をまとめていきます。見やすくなるように表示を工夫してはいきたいですが、ごちゃごちゃするかもしれません。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 \\
A_4 & \lt & B_4 \\
[ A_5 B_5 ] & \lt & B_4
\end{eqnarray}
$$
このようにして、ひとつずつ確認をしていきます。以下、読むには退屈になりますので飛ばしていただいても大丈夫です。

\( C_3 \) は、\( B_3 \lt C_3 \) と \( B_4 \lt C_3 \) です。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & B_4 & \lt & C_3 \\
[ A_5 B_5 ] & \lt & B_4
\end{eqnarray}
$$
\( C_4 \) は、\( [ B_4 C_4 ] \) と \( B_5 \lt C_4 \) です。\( B_5 \lt [ B_4 C_4 ] \) がいえ、\( [A_5 B_5] \lt B_4 \) と合わせることができます。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & [ B_4 C_4 ] & \lt & C_3 \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ]
\end{eqnarray}
$$
\( C_5 \) は、\( B_5 \lt C_5 \) と \( B_1 \lt C_5 \) です。だんだん書きづらくなってきました。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & [ B_4 C_4 ] & \lt & C_3 \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] \\
[ A_5 B_5 ] & \lt & C_5
\end{eqnarray}
$$

\( D_1 \) から \( D_5 \) をみます。

\( D_1 \) は、\( C_1 \lt D_1 \) と \( [ C_2 D_1 ] \) 。つまり \( C_1 \lt [ C_2 D_1 ] \) 。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & [ B_4 C_4 ] & \lt & C_3 \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] \\
[ A_5 B_5 ] & \lt & C_5
\end{eqnarray}
$$
\( D_2 \) は、\( D_2 = 20 \) ですので飛ばします。

\( D_3 \) は、\( [ C_3 D_3 ] \) と \( C_4 \lt D_3 \) 。つまり \( C_4 \lt [ C_3 D_3 ] \)
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] \\
[ A_5 B_5 ] & \lt & C_5
\end{eqnarray}
$$
\( D_4 \) は、\( C_4 \lt D_4 \) と \( C_5 \lt D_4 \) 。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] & \lt & D_4 \\
[ A_5 B_5 ] & \lt & C_5 & \lt & D_4
\end{eqnarray}
$$
\( D_5 \) は、\( C_5 \lt D_5 \) と \( C_1 \lt D_5 \) 。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 & \lt & D_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] & \lt & D_5 \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] & \lt & D_4 \\
[ A_5 B_5 ] & \lt & C_5 & \lt & D_4
\end{eqnarray}
$$
\( E \) は \( E = 21 \) なので省略。

ひと通りみましたが、どっか抜けてそうな気がします……。

また、チェックもしたいし、他にも考慮したいところがありますし、こんなことをやって意味があるのかも見直したいので、また次回……。

ビリヤードの問題再考（６）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

原点に戻って、5つのビリヤード玉で問題をあらためて考えます。

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

問題文の条件でビリヤード玉を取り出す方法が何通りあるかと数えると、21通りあります。5つのビリヤード玉を \( a_1, a_2, a_3, a_4, a_5 \) として、この順につながっているとすると、取り出し方は次の21通りです。

1個だけ取り出す　5通り
$$
a_1, \quad a_2, \quad a_3, \quad a_4, \quad a_5
$$
2個取り出す　5通り
$$
a_1 + a_2 , \quad a_2 + a_3 , \quad a_3 + a_4 , \\
a_4 + a_5 , \quad a_5 + a_1
$$
3個取り出す　5通り
$$
a_1 + a_2 + a_3 , \quad a_2 + a_3 + a_4 , \quad a_3 + a_4 + a_5 , \\
a_4 + a_5 + a_1 , \quad a_5 + a_1 + a_2
$$
4個取り出す　5通り
$$
a_1 + a_2 + a_3 + a_4 , \quad a_2 + a_3 + a_4 + a_5 , \\
a_3 + a_4 + a_5 + a_1 , \quad a_4 + a_5 + a_1 + a_2 , \\
a_5 + a_1 + a_2 + a_3
$$
5個全部取り出す　1通り
$$
a_1 + a_2 + a_3 + a_4 + a_5
$$

この21通りが、1から21までのすべての数（自然数）に対応することになります。この21通りのそれぞれの計算結果はすべて異なる数で、1から21のどれかということになります。そこから、1（と2）が \( a_1, a_2, a_3, a_4, a_5 \) のうちのどこかに入ること、そして5個すべてを取り出した \( a_1 + a_2 + a_3 + a_4 + a_5 \) が21となることが容易にわかります。

そこで、\( a_1 = 1 \) としたとき、この21通りにどこまで大小関係がつけられるのかを考えてみたいと思います。

見やすさのため次のように記号をおきます。
$$
\begin{eqnarray}
A_1 &=& a_1 = 1 \\
A_2 &=& a_2 \\
A_3 &=& a_3 \\
A_4 &=& a_4 \\
A_5 &=& a_5 \\\\

B_1 &=& a_1 + a_2 = 1 + a_2 \\
B_2 &=& a_2 + a_3 \\
B_3 &=& a_3 + a_4 \\
B_4 &=& a_4 + a_5 \\
B_5 &=& a_5 + a_1 = a_5 + 1 \\\\

C_1 &=& a_1 + a_2 + a_3 = 1 + a_2 + a_3 \\
C_2 &=& a_2 + a_3 + a_4 \\
C_3 &=& a_3 + a_4 + a_5 \\
C_4 &=& a_4 + a_5 + a_1 = a_4 + a_5 + 1 \\
C_5 &=& a_5 + a_1 + a_2 = a_5 + 1 + a_2 \\\\

D_1 &=& a_1 + a_2 + a_3 + a_4 = 1 + a_2 + a_3 + a_4\\
D_2 &=& a_2 + a_3 + a_4 + a_5 = 20 \\
D_3 &=& a_3 + a_4 + a_5 + a_1 = a_3 + a_4 + a_5 + 1 \\
D_4 &=& a_4 + a_5 + a_1 + a_2 = a_4 + a_5 + 1 + a_2 \\
D_5 &=& a_5 + a_1 + a_2 + a_3 = a_5 + 1 + a_2 + a_3 \\\\

E &=& a_1 + a_2 + a_3 + a_4 + a_5 = 21
\end{eqnarray}
$$
\( A_1 \) など、記号をおく必要がないところもありますが、一貫性のために一応記号をおいています。また、\( A_1 = 1 \) のようにすでにわかっている数字を書き込んでいます。この21個を小さいものから順に並べると1から21の数字となります。現在は \( a_1 = 1 \) とおいているだけですので一列に並べることはできませんが、この状態でどこまで大小関係をつけられるか、どこまで並べられるのかを考えてみます。\( A_1 ( = 1) \lt \cdots \lt D_2 ( = 20 ) \lt E ( = 21 ) \) ですので、2から20の間を考えましょう。

まずは、\( A_2 \) から \( A_5 \) について。この4つは \( A_1 \) よりも大きいことはわかりますが、現状、\( A_2 \) から \( A_5 \) のあいだで大小関係をつけることはできません。ただし、すべて異なる自然数であるということと、\( E = 21 \) より、\( A_2 \) から \( A_5 \) のなかの自然数は最大でも11であることはわかります。4つの異なる自然数の組で最小の組み合わせは \( { 1, 2, 3, 4 } \) で、この合計は10です。合計が21である5つの自然数のうちの4つを一番小さくしたとすると、残る1つは11となり、11より大きくなると他の4つの組み合わせは存在しなくなるためです。ここで使うかどうかはわかりませんが、一応書いておきます。
$$
2 \leqq A_2 \leqq 11 \quad
2 \leqq A_3 \leqq 11 \\
2 \leqq A_4 \leqq 11 \quad
2 \leqq A_5 \leqq 11
$$
続いて \( B_1 \) をみてみましょう。\( B_1 = 1 + a_2 \) ですので、\( A_2 \lt B_1 \) が成り立ちます。ここで \( A_2 \) と \( B_1 \) の差は1ですので、 \( A_2 \) と \( B_1 \) の間には他の要素は入りません。そこで、このように間に何も入らないときは、\( [ A_2 B_1 ] \) と書いていきます。右側のほうが左側よりも1だけ大きいという意味です。3つ以上の要素を並べるときもあるかもしれませんが、その際も同様に考えます。

\( B_5 \) についても、\( [ A_2 B_1 ] \) と同様に、\( [ A_5 B_5 ] \) といえます。すぐにわかる差が1の組み合わせを挙げておきましょう。
$$
[ A_2 B_1 ] , \quad
[ A_5 B_5 ] , \\
[ B_2 C_1 ] , \quad
[ B_4 C_4 ] , \\
[ C_2 D_1 ] , \quad
[ C_3 D_3 ]
$$
と、このように大小関係を少しずつ確認してみることにします。

ビリヤードの問題再考（５）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

現時点では次のようなことを考えています。

\( n \) 個の自然数が、真珠のネックレスのように、リングでつながっている。この \( n \) 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、\( n \) 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から \( n(n-1)+1 \) までのすべての自然数ができるようにしたい。\( n \) がどのようなときに成り立つだろうか。あるいはどのようなときに成り立たないだろうか。

具体例があったほうが考えやすいので、\( n \) が少ないときの状況についてまとめておきます。

\( n \) が少ないときの状況（ \( n = 7 \) まで）は以下です。成り立つときを解あり、成り立たないときを解なしと表現しています。解ありの場合は解の数と実際の解も明記しております。ただし、自分自身で実際に確認したのは \( n = 5 \) までで、 \( n = 6, 7 \) のときは以前にネットで確認したものを載せています（解ありの \( n = 6 \) の解が条件を満たすことは確認済み）。

\( n=1 \) のとき、\( n(n-1)+1 = 1 \)。解は1つ
$$
( 1 )
$$
\( n=2 \) のとき、\( n(n-1)+1 = 3 \)。解は1つ
$$
( 1, 2 )
$$
\( n=3 \) のとき、\( n(n-1)+1 = 7 \)。解は1つ
$$
( 1, 2, 4 )
$$
\( n=4 \) のとき、\( n(n-1)+1 = 13 \)。解は2つ
$$
( 1, 2, 6, 4 ), \ ( 1, 3, 2, 7 )
$$
\( n=5 \) のとき、\( n(n-1)+1 = 21 \)。解は1つ
$$
( 1, 3, 10, 2, 5 )
$$
\( n=6 \) のとき、\( n(n-1)+1 = 31 \)。解は5つ（以下の解が条件を満たしていることは確認済み。他に解があるかどうかは未確認）
$$
( 1, 2, 5, 4, 6, 13 ), \ ( 1, 2, 7, 4, 12, 5 ), \ ( 1, 3, 2, 7, 8, 10 ), \\
( 1, 3, 6, 2, 5, 14 ), \ ( 1, 7, 3, 2, 4, 14 )
$$
\( n=7 \) のとき、\( n(n-1)+1 = 43 \)。解なし（未確認）

解があったりなかったり、またあったとしても1つだけではなく複数あったりするので、解の公式のようなものは存在しないと思われます。解き方としてはアルゴリズム的な解き方となると思います。以前にネットで見たものも、アルゴリズムをつくって、その結果を載せていたものだったと思います。

ビリヤードの問題再考（４）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

前回、このビリヤードの問題を一般化して考えるとどのような問題になるのかについて考えてみました。現時点では次のようなことを考えています。

\( n \) 個の自然数が、真珠のネックレスのように、リングでつながっている。この \( n \) 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、\( n \) 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から \( n(n-1)+1 \) までのすべての自然数ができるようにしたい。\( n \) がどのようなときに成り立つだろうか。あるいはどのようなときに成り立たないだろうか。

考え方も一般化していきたいので、さらに記号を導入していきます。ひょっとすると使わないような記号や定義があるかもしれませんが、考えられるだけ考えておきます。

まずは、\( n \) 個の自然数がリングでつながっている状態を図ではなく、数式のように表していくことを考えました。5個のビリヤード玉の問題を解いたときにはＡ－Ｂ－Ｃ－Ｄ－Ｅというような表記の仕方をしましたが、今後は一般化をみこして、ここでは \( \langle a_5 \rangle \) と表記していきます。\( \langle a_5 \rangle \) は、5個の自然数 \( a_1, a_2, a_3, a_4, a_5 \) がこの順序でリング状につながっていることを表します。\( \langle a_n \rangle \) ならば、\( n \) 個の自然数が、右回りで \( a_1, a_2, \cdots, a_n \) とつながっていて、最後の \( a_n \) が \( a_1 \) につながっています。 当然のこと（？）ながら、\( a_1, a_2, \cdots, a_n \) は自然数です。

なので、\( \langle a_n \rangle \) を循環する数列とみることもできます。\( \langle a_5 \rangle \) ならば、 \( a_1, a_2, a_3, a_4, a_5, a_1, a_2, \cdots \) と続いていく数列です。ここでは循環数列と呼んでいきます。循環数列という言葉はあるようですが、一般の循環数列の定義をしっかりとは知らないので、一般的な循環数列の定義とは異なるかもしれません。

循環小数で循環する間隔（？）のことを長さと表現します。\( 0.121212\cdots \) ならば \( 12 \) が循環しているので循環の長さは \( 2 \) となります。\( 0.333333\cdots \) ならば長さは \( 1 \) 、\( 0.456745674567\cdots \) ならば、長さは \( 4 \) です。

ここでの循環数列 \( \langle a_n \rangle \) も、循環小数での言葉にならい、長さ \( n \) の循環数列と呼びます。\( \langle a_5 \rangle \) は、長さ \( 5 \) の循環数列です。また、数列にならい、 \( a_1, a_2, \cdots, a_n \) を初項（第1項）、第2項、…、第 \( n \) 項と呼びます（「第」をつけず単に \( n \) と呼ぶ場合もあり）。第 \( n+1 \) 項ということも言いますが、（長さ \( n \) の場合、）値としては第1項と同じ値です。

また、ここで考えていく循環数列の特徴として、「この \( n \) 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、\( n \) 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から \( n(n-1)+1 \) までのすべての自然数ができるようにしたい」ということがあります。そこで、この特徴を表せるような表記も考えておきます。簡略化となるかどうかはわかりませんが、一応簡略化のための表記です。（逆にわかりにくくなってしまいこの表記ボツにするかもしれません。）

この条件での取り出し方のひとつに、\( a_1, a_2, \cdots, a_n \) の初項 \( a_1 \) と第2項 \( a_2 \) を取り出すということがあります。そして、\( a_1 + a_2 \) を計算することになります。この \( a_1 + a_2 \) を、\( a(2) _1 \) と表したいと思います。\( a(2) _1 = a_1 + a_2 \) です。括弧()の中の2は2つの項を足したという意味で、添字は足し算の最初の項という意味です。\( a(3) _1 \) ならば、\( a(3) _1 = a_1 + a_2 + a_3 \)、\( a(4) _2 \) ならば \( a(4)_2 = a_2 + a_3 + a_4 + a_5 \) という意味です。循環の長さより大きな項が出てきたときは、同じ値の項に変換します（ここはうまく表現できていませんが、やっていくうちにわかるかと思います）。

もうひとつ、表記の仕方の（ここでの）ルールとして、次のようなことを挙げておきます。

以前、5個のビリヤード玉での解答として①－⑤－②－⑩－③（－①）を挙げましたが、これは①－③－⑩－②－⑤（－①）と同じものと見なします。この2つは、右回りか左回りの違い、別の表現では裏返したら同じです。また、⑤－②－⑩－③－①（－⑤）も同じものです。同じものを表すのに、いくつもの表記があるとわかりにくいので、①を初項として表記することを基本として、②がなるべく前にあるものを代表として表記とします。もしかすると計算過程などでこのルールとズレることがあるかもしれませんので、そこまで厳密ではありません。

まぁ、うだうだと書いておりますが、あまり考えが進んでいないことはわかったかと思います。

ビリヤード玉の問題再考（３）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

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

この問題を一般的な問題におきかえることができるとしたらどのようになるのかについて考えてみます。

問題では5個のビリヤード玉で、取った玉のナンバを足し合わせて1から21までのすべての数ができるようにしたいとしていますが、これは、玉のとり方が\( 21 \) 通りあるからであるとします。\( n \) 個の場合だと、玉の取り方は \( n(n-1)+1 \) 通りとなります。ここから確認していきましょう。

まずは5個の場合を考えます。リング状につながったビリヤード玉に記号をつけておきます。右回りに「Ａ－Ｂ－Ｃ－Ｄ－Ｅ」とつながっているとします。リング状ですので最後のＥはＡにつながっています。

まずは、1個を取る場合。これはＡを取るか、Ｂを取るか、Ｃを取るか、Ｄを取るか、Ｅを取るかの5通り。2個の場合は、Ａ－Ｂ、Ｂ－Ｃ、Ｃ－Ｄ、Ｄ－Ｅ、Ｅ－Ａの5通り。3個の場合は、Ａ－Ｂ－Ｃ、Ｂ－Ｃ－Ｄ、Ｃ－Ｄ－Ｅ、Ｄ－Ｅ－Ａ、Ｅ－Ａ－Ｂの5通り。4個の場合は、Ａ－Ｂ－Ｃ－Ｄ、Ｂ－Ｃ－Ｄ－Ｅ、Ｃ－Ｄ－Ｅ－Ａ、Ｄ－Ｅ－Ａ－Ｂ、Ｅ－Ａ－Ｂ－Ｃの5通り。5個の場合は、Ａ－Ｂ－Ｃ－Ｄ－Ｅの1通りとなります。\( 5+5+5+5+1 = 21 \) で、\( 21 \) 通りとなります。

\( n \) 個の場合だと、1個を取る取り方が \( n \) 通り、2個も \( n \) 通り、3個も \( n \) 通り、……、 \( n-1 \) 個も \( n \) 通り、 \( n \) 個すべてを取るのが1通りとなり、合計 \( n(n-1) + 1 \) 通りとなります。

なので問題を一般化するとすれば、\( n \) 個のビリヤード玉で、1から\( n(n-1) + 1 \) までのすべての数ができるように、ということになります。玉を取る条件は変わりません。

5個のビリヤード玉のときは、1から21までのすべての自然数をつくることができましたが、他の個数のときには解答があるかどうかわかりません。また、一意に定まるかどうかもわかりません。実際、確認したところでは、1個のときは解あり（1つ）、2個のときも解あり（1つ）、3個の場合も解あり（1つ）、4個の場合は解ありですが2つの解、5つのときは解あり（1つ）。また、詳細未確認ですが、6個のときは複数解あり、7個のときは解なしとなるようです。（以前に書いたブログより。以前のブログに参照したサイトのリンクをつけていましたが、リンク切れとなっていました。6個のときと7個のときは検証が必要です。）

そこでこれから考えていく問題文を以下のようにしたいと思います。厳密さを要求するならばもう少ししっかりと書いたほうがいいのかもしれませんが、いまはこのくらいで。

\( n \) 個の自然数が、真珠のネックレスのように、リングでつながっている。この \( n \) 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、\( n \) 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から \( n(n-1)+1 \) までのすべての自然数ができるようにしたい。\( n \) がどのようなときに成り立つだろうか。あるいはどのようなときに成り立たないだろうか。

ビリヤード玉の問題再考（２）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

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

最終的には \( n \) 個のビリヤード玉で解が存在するかどうか、存在するとすればその求め方、存在しないとすればその証明などを明らかにしたいと思いますが、そこまで行き着けない可能性もあります。

まずは、5個のビリヤード玉での解法を確認します。解法といっても、僕が以前に解いたやり方（場合分けによる総当り的なやり方）ですので、もう少しスマートな解法があるかもしれません。あらためて解くことで、そういった解法に出会えるかもしれませんし、当たり前と思ってさらっと流していた条件などに気づけるかもしれませんので、もう一度あらためて解いてみたいと思います。なので少し細かく書いているので冗長な部分があるかと思います。

条件とか、ここでの表記の仕方についての確認しながら解いていきます。

5個のビリヤード玉を、Ａ・Ｂ・Ｃ・Ｄ・Ｅとして、この順で右回りにリングでつながっているとします。Ａ－Ｂ－Ｃ－Ｄ－Ｅ（－Ａ）とつながっていて、最後のＥとＡがつながってリング状になっている状態です。書かれているナンバは自然数とします。5つの玉のうち、幾つ取っても良いが隣どうし連続したものしか取れません。この条件で取った玉のナンバを足し合わせて、1から21までのすべての自然数ができるようにします。

問題の条件での玉の取り方が何通りあるかを数えると、\( 21 \) 通りあります。まずは、1個を取る場合。これはＡを取るか、Ｂを取るか、Ｃを取るか、Ｄを取るか、Ｅを取るかの5通り。2個の場合は、Ａ－Ｂ、Ｂ－Ｃ、Ｃ－Ｄ、Ｄ－Ｅ、Ｅ－Ａの5通り。3個の場合は、Ａ－Ｂ－Ｃ、Ｂ－Ｃ－Ｄ、Ｃ－Ｄ－Ｅ、Ｄ－Ｅ－Ａ、Ｅ－Ａ－Ｂの5通り。4個の場合は、Ａ－Ｂ－Ｃ－Ｄ、Ｂ－Ｃ－Ｄ－Ｅ、Ｃ－Ｄ－Ｅ－Ａ、Ｄ－Ｅ－Ａ－Ｂ、Ｅ－Ａ－Ｂ－Ｃの5通り。5個の場合は、Ａ－Ｂ－Ｃ－Ｄ－Ｅの1通りとなります。\( 5+5+5+5+1 = 21 \) で、\( 21 \) 通りとなります。この \( 21 \) 通りで1から21までのすべての自然数をつくるので、Ａ・Ｂ・Ｃ・Ｄ・Ｅはすべて異なる自然数で、玉の取り方1つに対し、1から21までの自然数のどれかが対応することになります。

したがって、①は必ず入っていることになります。ここでは1と書かれているビリヤード玉を①と書きます。1をつくるのには①が必要です。①の場所をＡに固定して考えます。これをＡ=①と書きます。Ａ－Ｂ－Ｃ－Ｄ－Ｅ（－Ａ）とつながっているので、①－Ｂ－Ｃ－Ｄ－Ｅ（－①）となります。

そして②も必ず入っていることになります。2をつくるためには \( 1+1 \) でもつくれますが、ビリヤード玉に書かれている自然数はすべて異なる自然数となりますので、①+①という組み合わせはありません。②も必ず存在することになりますが、場所はわかりません。

また、\( Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 \) となります。Ａ・Ｂ・Ｃ・Ｄ・Ｅを場所と言ったり、文字式の中に使ったりしてしまいますが、ご容赦ください。このあたり、一般化して考えるときにはもう少し表記の仕方を考えなければならないかもです。

Ａ=①として、その隣に②があるかどうかで場合分けをして考えます。もし①の隣に②があれば、\( ①+②=3\) となり、③の玉は不要になります。逆に①の隣に②がなければ③の玉が必要になります。もし3を自然数の和で表すとすれば、\( 1+2 \) しか存在しないためです。（Mathjaxを使って書いており、フォントが異なってしまっているところがあります。フォントの違いは無視してください。区別しなければならないときはその旨記載します。）

Ａ=①の隣ということは、ＢかＥとなりますが、ＢでもＥでも裏返して考えると同じになるので、ここではＢ=②かどうかで考えます。


(i) ①の隣に②がある場合（Ｂ=②の場合）
つまり、①－②－Ｃ－Ｄ－Ｅ（－①）の場合です。

残りのＣ・Ｄ・Ｅについて考えると、①、②は使われていて、3は①+②で不要ですので、4以上の自然数となります。また、\( Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 \) ですので、\( Ｃ+Ｄ+Ｅ=18 \) です。このような相異なる自然数の組となるものは、{ ④, ⑤, ⑨ } { ④, ⑥, ⑧ } { ⑤, ⑥, ⑦ } の3組です。{}でくくった組み合わせは順番関係なしの組み合わせとします。このうち { ⑤, ⑥, ⑦ } では4をつくることができませんので、残るは { ④, ⑤, ⑨ } { ④, ⑥, ⑧ } です。

④が存在しなければならないことになるので、④が①－②－Ｃ－Ｄ－Ｅ（－①）のどこに入るかを場合分けして考えます。

(i-a) Ｃ=④の場合
つまり、①－②－④－Ｄ－Ｅ（－①）の場合です。

この状態では5をつくることができませんので⑤が必要となり、Ｃ・Ｄ・Ｅの組み合わせは、{ ④, ⑤, ⑨ } となります。しかし、①－②－④－⑤－⑨（－①）としても、①－②－④－⑨－⑤（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｃ=④ではありません。

(i-b) Ｄ=④の場合
つまり、①－②－Ｃ－④－Ｅ（－①）の場合です。

この場合も⑤が必要となり、Ｃ・Ｄ・Ｅの組み合わせは、{ ④, ⑤, ⑨ } となります。しかし、①－②－⑤－④－⑨（－①）としても、①－②－⑨－④－⑤（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｄ=④でもありません。

(i-c) Ｅ=④の場合
つまり、①－②－Ｃ－Ｄ－④（－①）の場合です。

この場合は、④+①で5をつくれます。したがって、Ｃ・Ｄ・Ｅの組み合わせは { ④, ⑥, ⑧ } となります。しかし、①－②－⑥－⑧－④（－①）としても、①－②－⑧－⑥－④（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｅ=④でもありません。

したがって、(i)①の隣に②がある場合は解なしです。

(ii) ①の隣に②がない場合
つまり、①－Ｂ－②－Ｄ－Ｅ（－①）か、①－Ｂ－Ｃ－②－Ｅ（－①）の場合ですが、この2つは裏返すと同じものですので、①－Ｂ－②－Ｄ－Ｅ（－①）として考えます。

①と②が離れているので、③が必要になります。そこで、③の場所で場合分けして考えます。

(ii-a) Ｂ=③の場合
つまり、①－③－②－Ｄ－Ｅ（－①）の場合です。

この場合は、①、②、③、①+③、③+②、①+③+②と、6までの自然数がつくれます。7をつくるには、Ｄ=⑤とするか、ＤかＥに⑦が存在するかのどちらかです。

(ii-a1) Ｄ=⑤の場合
この場合は、\( Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 \) から、①－③－②－⑤－⑩（－①）となります。しかし、8をつくることができません。

(ii-a2) ＤかＥに⑦が存在する場合
この場合、残るひとつは⑧になります。したがって、①－③－②－⑦－⑧（－①）か、①－③－②－⑧－⑦（－①）です。しかし、どちらも1から21までのすべての自然数をつくることができません（前者は10がつくれない。後者は⑧と⑦+①で8がダブる）。

したがって、(ii-a) Ｂ=③の場合、解なしです。

(ii-b) Ｄ=③の場合
つまり、①－Ｂ－②－③－Ｅ（－①）の場合です。

この場合、④が必要となります。したがって残る1つは⑪となり、①－④－②－③－⑪（－①）か、①－⑪－②－③－④（－①）となります。しかし、どちらも1から21までのすべての自然数をつくることができません（どちらも5がダブる）。

したがって、(ii-b) Ｄ=③の場合も、解なしです。

(ii-c) Ｅ=③の場合
つまり、①－Ｂ－②－Ｄ－③（－①）の場合です。

この場合、③+①で4がつくれます。このままでは5がつくれないので⑤が必要です。⑤が決まれば、残りは⑩となります。したがって、①－⑤－②－⑩－③（－①）か、①－⑩－②－⑤－③（－①）です。後者は6がつくれません。前者の場合は、1から21までのすべての自然数をつくることができます。

念のため、確認してみましょう。

1. ①
2. ②
3. ③
4. ③+①
5. ⑤
6. ①+⑤
7. ⑤+②
8. ①+⑤+②
9. ③+⑤+①
10. ⑩
11. ③+①+⑤+②
12. ②+⑩
13. ⑩+③
14. ⑩+③+①
15. ②+⑩+③
16. ②+⑩+③+①
17. ⑤+②+⑩
18. ①+⑤+②+⑩
19. ⑩+③+①+⑤
20. ⑤+②+⑩+③
21. ①+⑤+②+⑩+③

1から21までのすべての自然数をつくれることが確認できました。

したがって、5つのビリヤード玉の問題の答えは、①－⑤－②－⑩－③（－①）となります。

さて、これを一般化して考えるにはどうすればよいでしょうか。

ビリヤード玉の問題再考（１）

森博嗣さんの『笑わない数学者』の中で、数学者天王寺博士が出す問題の一つに、以下の問題があります。

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

小説内では解答も解法も載っておらず、読んだ当時に力づくで解きました。しかし、小説内ではさらに以下のようなやり取りがあります。

天王寺博士の宿題について少し議論した。問題は玉の数が五個だったが、四個の場合も問題が成立する。では、六個はどうか、\( n \) 個ではどうか、という話だった。

\( n \) 個の場合に問題が成立するかどうかについては、以前考えてみたものの煮詰まって途中で投げ出しておりました。

以前は力づくで解いたのですが、もう少しスマートな方法はないか、また、\( n \) 個の場合に問題が成立するかどうかについてなど、あらためて考えてみたいと思います。

（以前途中で投げ出した記事はこちら）

５つのビリヤード玉の問題(1)(2)(3)(4)(5)(6)、試行錯誤編(1)(2)

これから考えていくことの方向性としては、次のようなことを考えます。まずは5つのビリヤード玉での問題をどのように解いたのかの整理。次に5つではなく4つとか6つとか他の場合での解き方や解答の確認。そこから一般的な問いや条件、解き方などを見出していき、最終的には、\( n \) 個の場合に問題が成立するかどうか、言い換えると、\( n \) がどのようなときに解答が存在するのか、存在するならばその解き方を、存在しないならばなぜなのかを明らかにできればいいと考えています。

書きながら考えているので、まだ結論はでておりませんので、（以前のように）途中で放棄するかも。

まずは5つのビリヤード玉で、問題をどのように解いたのかの整理していきたいと思います。

５つのビリヤード玉の問題（試行錯誤編２）

（これまで）

５つのビリヤード玉の問題（１）（２）（３）（４）（５）（６）

５つのビリヤード玉の問題（試行錯誤編）

　

循環数列のことはさておき、数列的に考えてみることを試みてみます。

アプローチの方法として、答えから考えてみるのも有りだと思いますので、５つのビリヤード玉の問題の答えから解き方の方向性を考えてみます。

考えるだけで、答えは出ない可能性があります(^-^;)

　

５つのビリヤード玉の問題での答えは、①③⑩②⑤でした。

そこで、まずこの答を数列Aとして、第1項が1、第2項が3、というように数列として考えます。

つまり、ここでは、A1=1、A2=3、A3=10、A4=2、A5=5、です。

　

次に、隣り合う2個のビリヤード玉を取ってその数字を足し合わせたことを考えて、数列Bを作ります。

つまり、B1=A1+A2、B2=A2+A3、B3=A3+A4、…という数列です。

さらに、今度は隣り合う3個のビリヤード玉を取って足し合わせたことを考え、数列Cを作ります。

C1=A1+A2+A3、C2=A2+A3+A4、C3=A3+A4+A5、…という数列です。

同じように4個の玉のため、数列Dをつくります。

　

すると、今、以下のような数列を作りました。

数列A：　A1　A2　A3　A4　A5

数列B：　B1　B2　B3　B4　B5

数列C：　C1　C2　C3　C4　C5

数列D：　D1　D2　D3　D4　D5

　

問題内の条件から、このA１～D5は、1から20の自然数のどれかに1対1に対応していることになります。

　

ちなみに、５つのビリヤード玉の解答を当てはめると、以下のようになります。

数列A：　①　③　⑩　②　⑤

数列B：　④　⑬　⑫　⑦　⑥

数列C：　⑭　⑮　⑰　⑧　⑨

数列D：　⑯　⑳　⑱　⑪　⑲

（ブログ内での表作成の方法を知りませんので、そろえるために〇囲み数字で書いています。）

　

さて、問題の条件から、A1+A2+A3+A4+A5=21なので、当然といえば当然のことですが、A1+D2=21となります。

同様に、A2+D3=21、A3+D4=21…です。

　

今、A1=1とします。

すると、D2=20となります。

　

また、A1+A2+A3+A4+A5=21なので、D1+D2+D3+D4+D5=21×4=84です。

A1=1、D2=20から、

1+A2+A3+A4+A5=21　⇒　A2+A3+A4+A5=20

D1+20+D3+D4+D5=84　⇒　D1+D3+D4+D5=64

となります。

そして、数列Aには②がどこかに含まれるので、数列Dにはどこかに⑲が含まれることになります。

　

ここまでの条件を列挙すると、

• A2+A3+A4+A5=20
• D1+D3+D4+D5=64
• A2+D3=21
• A3+D4=21
• A4+D5=21
• A5+D1=21
• A2、A3、A4、A5のうち、どれかは2
• D1、D3、D4、D5のうち、どれかは19
• D1=A1+A2+A3+A4　=1+A2+A3+A4
• D3=A3+A4+A5+A1　=A3+A4+A5+1
• D4=A4+A5+A1+A2　=A4+A5+1+A2
• D5=A5+A1+A2+A3　=A5+1+A2+A3
• A2、A3、A4、A5、D1、D3、D4、D5は2～19までの自然数のどれか
• A2、A3、A4、A5、D1、D3、D4、D5は全て異なる自然数
• D1、D3、D4、D5は10～19までの自然数

　

う～ん、考えやすくなったような、なっていないような…。

やっぱり組み合わせになってきますね。

もともとの解き方と同じになりそうですが、とりあえず進めます。

　

まずは、単純なところから、2～19までの自然数で、足して21になるような2つの自然数の組み合わせを考えましょう。

｛2、19｝（この組み合わせは必ず入る）

｛3、18｝｛4、17｝｛5、16｝｛6、15｝

｛7、14｝｛8、13｝｛9、12｝｛10、11｝

　

今度は、A2+A3+A4+A5=20から、数列Aについて2を含めた4個の自然数の組み合わせを考えて、その場合の数列Dの組み合わせをあげてみると、

（左側の方が数列Aの集合、右側は数列Dの集合）

｛2、3、4、11｝　｛19、18、17、10｝

｛2、3、5、10｝　｛19、18、16、11｝

｛2、3、6、9｝　｛19、18、15、12｝

｛2、3、7、8｝　｛19、18、14、13｝

｛2、4、5、9｝　｛19、17、16、12｝

｛2、4、6、8｝　｛19、17、15、13｝

｛2、5、6、7｝　｛19、16、15、14｝

　

やはり、場合分けになってしまいますね(^-^;)

５つのビリヤード玉の問題（試行錯誤編）

５つのビリヤード玉の問題を考えるにあたり、ちょっと思いついたことを書いてみます。

それは、５つのビリヤード玉の数と並べ方を数列として扱えないか、というものです。

　

５つのビリヤード玉の答えは、①③⑩②⑤（あるいは逆に①⑤②⑩③）でした。

これを、数列として、

1, 3, 10, 2, 5, 1, 3, 10, 2, 5, …

というように、循環する数列として表せないか？ということです。

そして、これを満たすような式があるかどうか、というものです。

　

しかし「数列」といっても、高校生のときに習ったきり全く縁がありませんでしたので、「等差数列」と「等比数列」そして「フィボナチ数列」の名前しか出てきません(^-^;)

とりあえず、WEB上で

等差数列は、一般項：an=a1+(n-1)d、漸化式：an+1=an+d

等比数列は、一般項：an=r^(n-1)･a1、漸化式：an+1=r・an

と表せることまでは、何とか思い出しました。

PC上の表記の仕方をすぐに思いつきませんでしたので、数列aの第n項をanと、大きなフォントのaと小さなフォントのnで表しています。

（HTMLでの下付け文字や上付け文字の表記がわからず…）

ちなみに、フィボナチ数列はの漸化式（？）は、an+2=an+an+1です。

　

さて、５つのビリヤード玉の問題に話を戻すと、５つの数字が並ぶ循環数列（この名称が合っているのかどうかわかりませんが、とりあえずこう表現しています。ちなみに「循環数列」で検索すると、オイラー関数とかが出てきたので、今のところチンプンカンプンです。）とかんがえられます。

つまり、第1項は「1」、第2項は「3」、第3項は「10」、…、第6項はまた「1」、というような数列です。

この数列を数列aとすると、

a1=1, a2=3, a3=10, a4=2, a5=5, a6=1(=a1), a7=3(=a2), …

という感じです。

この数列を求めることができるかどうか、ということです。

　

５つのビリヤード玉の問題から考えると、条件として以下のようなものがあげられるかと思います。

• 数列aの各項は自然数である。
• 数列aは５つで一巡する循環数列である。
• その５つの項はそれぞれ異なる。
• ５つの項をビリヤード玉の問題のように取り出す方法は21通りある。
• その21通りの取り出し方は、1から21までの自然数と対応する。

など。

　

さて、解けるでしょうか？

今のところの自信は全く「なし」です(^-^;)

５つのビリヤード玉の問題（６）

続きを書くのを忘れていたのです。

（これまで）

５つのビリヤード玉の問題（１）（２）（３）（４）（５）

　

前回は、６つの場合の組み合わせを羅列したところで終わっていました。

今回は、そこからの続きです。

　

では、今までと同じように、

（a）①と②が隣り合う場合

（b）①と②が隣り合わない場合

で考えてみましょう。

　

（a）①と②が隣り合う場合

①と②が隣り合うということは、③の玉は不要となります。

で、③が不要ということは、④が必要ということになります。

従って、組み合わせとしては、以下の組み合わせが残ります。

｛①、②、④、⑤、⑥、⑬｝

｛①、②、④、⑤、⑦、⑫｝

｛①、②、④、⑤、⑧、⑪｝

｛①、②、④、⑤、⑨、⑩｝

｛①、②、④、⑥、⑦、⑪｝

｛①、②、④、⑥、⑧、⑩｝

｛①、②、④、⑦、⑧、⑨｝

ではここで、

（a1）②と④が隣り合う場合

（a2）②と④が隣り合わない場合

を考えましょう。

　

（a1）②と④が隣り合う場合

これはつまり、①②④が隣り合う場合となります。

従って、⑥と⑦は不要。

残る組み合わせは、

｛①、②、④、⑤、⑧、⑪｝

｛①、②、④、⑤、⑨、⑩｝

の２つです。

　

１～７の数字までは作ることができるので、８を作る方法を考えてみると、⑧を含むか、⑤①②④の並びにするか、どちらかとなります。

　

では、⑧を含む方の組み合わせから考えます。

｛①、②、④、⑤、⑧、⑪｝

9をつくるには、④と⑤を並べる方法か、⑧と①を並べる方法になります。

なので並べ方は、①②④⑤⑧⑪か、①②④⑪⑤⑧のどちらか。

ですが、どちらも１０を作ることができません。

従って、ボツ。

　

では今度は、｛①、②、④、⑤、⑨、⑩｝の組み合わせの方で、⑤①②④と並べた場合を考えると、

並べ方は、①②④⑨⑩⑤と①②④⑩⑨⑤の2通り。

ですが、どちらの並べ方でも１１が作れません。

従って、ボツ。

　

なので、（a1）②と④が隣り合う場合はボツ。

　

今日はここまで(^-^;)

５つのビリヤード玉の問題（５）

（これまでのリンク）

５つのビリヤード玉の問題
５つのビリヤード玉の問題（２）
５つのビリヤード玉の問題（３）
５つのビリヤード玉の問題（４）

とりあえず考えがまとまらないので、４個の場合と６個の場合を考えてみます。

　

まずは４個の場合。

　

①と②が使われることは決まっていて、４個の異なる自然数の和が13になればいいので、４個の自然数の組み合わせは、

｛①、②、③、⑦｝　｛①、②、④、⑥｝

の２通りしかありません。

５個の場合と同じように、①と②が隣り合っているかないか、で考えてみると、①と②が隣り合う場合は③が不要、①と②が隣り合わない場合は③が必要、となります。

ということは、①と②が隣り合う場合の組み合わせとして｛①、②、④、⑥｝の組み合わせ、隣合わない場合の組み合わせとして｛①、②、③、⑦｝を考えればいいことになります。

　

①と②が隣り合う場合

並べ方としては、「①②④⑥」と「①②⑥④」の２通りがあります。

このうち、５をつくることができるのは「①②⑥④」の並べ方です。

この並べ方が正解の一つ。

　

①と②が隣り合わない場合

並べ方としては、「①③②⑦」と「①⑦②③」の２通りがあります。

しかしこの並べ方は、時計回りか、反時計回りかの違いですので、どちらもかわりない並べ方と考えられます。

　

４個の場合は、５個の場合より簡単に解けました。

　

では、６個の場合はどうでしょうか？

　

６個の場合は、1から31までの数をつくることになります。

①と②を使用することは変わりませんので、組み合わせとしては、

｛①、②、③、④、⑤、⑯｝

｛①、②、③、④、⑥、⑮｝

｛①、②、③、④、⑦、⑭｝

｛①、②、③、④、⑧、⑬｝

｛①、②、③、④、⑨、⑫｝

｛①、②、③、④、⑩、⑪｝

｛①、②、③、⑤、⑥、⑭｝

｛①、②、③、⑤、⑦、⑬｝

｛①、②、③、⑤、⑧、⑫｝

｛①、②、③、⑤、⑨、⑪｝

｛①、②、③、⑥、⑦、⑫｝

｛①、②、③、⑥、⑧、⑪｝

｛①、②、③、⑥、⑨、⑩｝

｛①、②、③、⑦、⑧、⑩｝

｛①、②、④、⑤、⑥、⑬｝

｛①、②、④、⑤、⑦、⑫｝

｛①、②、④、⑤、⑧、⑪｝

｛①、②、④、⑤、⑨、⑩｝

｛①、②、④、⑥、⑦、⑪｝

｛①、②、④、⑥、⑧、⑩｝

｛①、②、④、⑦、⑧、⑨｝

｛①、②、⑤、⑥、⑦、⑩｝

｛①、②、⑤、⑥、⑧、⑨｝

　

これだけですかね。

数え落しがあるかもしれません。

疲れたので、休憩(^-^;)

５つのビリヤード玉の問題（４）

（これまでの記事のリンク）

５つのビリヤード玉の問題
５つのビリヤード玉の問題（２）
５つのビリヤード玉の問題（３）

　

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

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

　

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と書かれたビリヤードの玉」とします。

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

1. ①

　

n=2 の場合

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

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

1. ①
2. ②
3. ①②

　

n=3 の場合

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

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

①②④ですね。

1. ①
2. ②
3. ①②
4. ④
5. ④①
6. ②④
7. ①②④

　

n=4 の場合

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

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

［答1］①③②⑦

1. ①
2. ②
3. ③
4. ①③
5. ③②
6. ①③②
7. ⑦
8. ⑦①
9. ②⑦
10. ②⑦①
11. ⑦①③
12. ③②⑦
13. ①③②⑦

［答2］①②⑥④

1. ①
2. ②
3. ①②
4. ④
5. ④①
6. ⑥
7. ④①②
8. ②⑥
9. ①②⑥
10. ⑥④
11. ⑥④①
12. ②⑥④
13. ①②⑥④

　

n=5 の場合

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

答えは①③⑩②⑤

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

　

n=6 の場合

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

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

（確認作業割愛・・・）

［答1］①⑦③②④⑭

［答2］①③⑥②⑤⑭

［答3］①③②⑦⑧⑩

［答4］①②⑤④⑥⑬

［答5］①②⑦④⑫⑤

　

n=7 の場合

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

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

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

　

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

ありがとうございます。

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

【2019/12/13追記】上記サイト、リンク切れとなっていました。

　

５つのビリヤード玉の問題（３）

さらに続きです。

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

５つのビリヤード玉の問題
５つのビリヤード玉の問題（２）

　

さて、今回は（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｝

の３つです。

しかし、「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 個のときの一般解が出せるのか・・・。

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

５つのビリヤード玉の問題（２）

前回の続きです。

気が向いたら…、と締めくくっていたのですが、小説内ではさらに以下のようなやり取りがあります。

…天王寺博士の宿題について少し議論した。問題は玉の数が五個だったが、四個の場合も問題が成立する。では、六個はどうか、ｎ個ではどうか、という話だった。

こちらについても、解答や解説はありません。

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

難題です。

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

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


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

（以下、問題の再掲）

「…五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、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

の２通り。

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

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

1・2・6・8・4

の1通り。

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

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

　

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

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

不安が残ります…

　

【追記】

続きを書きました。

５つのビリヤード玉の問題（３）

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

森博嗣さんの『笑わない数学者』の中で、数学者天王寺博士が出す問題の一つに、以下の問題があります。

「…五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、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になること
• ・・・など

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

（１）①と②が隣り合っている場合

（２）①と②が隣り合ってない場合

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


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

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

【追記】

続きを書きました。

５つのビリヤード玉の問題（２）