Pool-Ball Triangles

by Kouichi Nakagawa, Dec 9, 2018, 8:39 PM

マーティン・ガードナー(Martin Gardner, 1914 - 2010) がScientific American の 236 巻 4 号 (1977 年 4 月) の「Mathematical Games」というコラムで以下のような問題を紹介しました.
Martin Gardner wrote:
Colonel George Sicherman of Buffalo tells me that about $10$ years ago, while he was watching a game of pool, the following problem occurred to him: Is it possible to form a "difference triangle" in arranging the $15$ balls in the usual triangular configuration before the start of a game? In a difference triangle the numbers $1$ through $15$ are arranged in such a way that each number below a pair of numbers is the positive difference between that pair.
例えば $1 \sim 3$ のボールを用いて $2$ 段の三角形を考えた場合は以下のような答えになります.
\[\begin{array}{cc} 3 \ 2 & 3 \ 1 \\ 1 & 2 \\ \end{array}\]では $1 \sim 6$ のボールを用いて $3$ 段の三角形を考えた場合はどのようになるでしょうか?
左右対称を同一視した場合以下の $4$ 通りの解があることが知られています.
\[\begin{array}{cccc} 6 \ 2 \ 5 & 2 \ 6 \ 5 & 6 \ 1 \ 4 & 1 \ 6 \ 4 \\ 4 \ 3 & 4 \ 1 & 5 \ 3 & 5 \ 2 \\ 1 & 3 & 2 & 3 \\ \end{array}\]これくらいの範囲ならば, 闇雲に勘で数字を当てはめても解けるかも知れません.
しかし $1 \sim 10$ のボールを用いて $4$ 段の三角形を考えた場合では大変になってしまいます.
因みにこの場合も $4$ 通りの解があることが知られているのですが, 全部探し出すのは勘では至難の業です.
そこで, もう少し数学的に候補を絞って考えてみましょう.
先ほど紹介した $1 \sim 6$ のボールを用いた $3$ 段の三角形の場合を例として考えてみます.
まずはじめに, 偶奇性に着目します. 便宜上偶数を $\textup{E}$, 奇数を $\textup{O}$ と置くことにすると
\[\begin{cases} \textup{E} \pm \textup{E} = \textup{O} \pm \textup{O} &= \textup{E} \\ \textup{E} \pm \textup{O} = \textup{O} \pm \textup{E} &= \textup{O} \\ \end{cases}\]となります.
よって最上段は以下の高々 $8$ 通りとなります.
\[\textup{E}\textup{E}\textup{E} \quad \textup{E}\textup{E}\textup{O} \quad \textup{E}\textup{O}\textup{E} \quad \textup{E}\textup{O}\textup{O} \quad \textup{O}\textup{E}\textup{E} \quad \textup{O}\textup{E}\textup{O} \quad \textup{O}\textup{O}\textup{E} \quad \textup{O}\textup{O}\textup{O}\]しかし, 使う数字は $1 \sim 6$ なので, $\textup{E}$ と $\textup{O}$ は各 $3$ つずつしか使えません.
これより条件を満たす偶奇の配置は以下の $3$ 通りしかないことが分かります.
\[\begin{array}{ccc} \textup{E} \ \textup{E} \ \textup{O} & \textup{E} \ \textup{O} \ \textup{E} & \textup{O} \ \textup{O} \ \textup{O} \\ \textup{E} \ \textup{O} & \textup{O} \ \textup{O} & \textup{E} \ \textup{E} \\ \textup{O} & \textup{E} & \textup{E} \\ \end{array}\]ここで, 一番大きい数字である $6$ は $5$ 以下の数字の差の絶対値では表すことが出来ないので, 最上段に来ることが分かります.
また, 二番目に大きい数字である $5$ は $6 - 1 = 5$ として作るしかないので,
$6$ と同じ最上段か, $6$ と $1$ を隣接させてその間の下(上から $2$ 段目) に置くことしか出来ません.
以上より $6$ と $5$ (と $1$) の位置の候補は以下のようになります.
\[\begin{array}{ccccc} 6 \ \textup{E} \ 5 & \textup{E} \ 6 \ 5 & \textup{E} \ 6 \ 1 & 6 \ 5 \ \textup{E} & 6 \ 1 \ \textup{E} \\ \textup{E} \ \textup{O} & \textup{E} \ \textup{O} & \textup{E} \ 5 & \textup{O} \ \textup{O} & 5 \ \textup{O} \\ \textup{O} & \textup{O} & \textup{O} & \textup{E} & \textup{E} \\ \textup{Pattern A} & \textup{Pattern B} & \textup{Pattern C} & \textup{Pattern D} & \textup{Pattern E} \\ \end{array}\]$\textup{Pattern C}$ と $\textup{Pattern E}$ は $\textup{O}$ が $1$ つしかないのでこの部分には $3$ が入ることが分かります.
残りもそこから自動的に分かり以下のようになります.
\[\begin{array}{cc} 4 \ 6 \ 1 & 6 \ 1 \ 4 \\ 2 \ 5 & 5 \ 3 \\ 3 & 2 \\ \end{array}\]残りのパターンは, 最上段の $\textup{E}$ は $2$ か $4$ なので, 具体的にいれて計算をして, 条件を満たすか確かめます.
すると
\[\begin{array}{cc} 6 \ 2 \ 5 & 2 \ 6 \ 5 \\ 4 \ 3 & 4 \ 1 \\ 1 & 3 \\ \end{array}\]と分かり, 以上 $4$ つが答えとなります.

これらの問題を単純に総当たりで解こうとすると
$1$ 段は $1$ なので $1$ 通り
$2$ 段は $1 \sim 3$ なので $3! = 6 < 10^{1}$ 通り
$3$ 段は $1 \sim 6$ なので $6! = 720 < 10^{3}$ 通り
$4$ 段は $1 \sim 10$ なので $10! = 3628800 < 10^{7}$ 通り
$5$ 段は $1 \sim 15$ なので $15! = 1307674368000 < 10^{13}$ 通り
$6$ 段は $1 \sim 21$ なので $21! = 51090942171709440000 < 10^{20}$ 通り
と増えていきます.
一方
$1$ kB = $1024$ byte > $10^{3}$ byte
$1$ MB = $1000$ kB > $10^{6}$ byte
$1$ GB = $1000$ MB > $10^{9}$ byte
$1$ TB = $1000$ GB > $10^{12}$ byte
ですので, $5$ 段以降の計算では総当たりで調べようにもメモリが足りないので工夫が必要になってきます.
また, CPU が $3$ GHz だとすると, これは $1$ 秒間に $3$ G 回 = $3 \times 10^9$ 回計算出来るということですが,
計算と行っても四則演算(除算に関しては加算・減算・乗算の倍かかる) に過ぎないので, 複雑な計算であればある程より時間がかかります.
ですので, 仮にメモリが沢山あり, $1$ 秒間に $3 \times 10^9$ パターンのチェックが出来たとしても $5$ 段では $4.3 \times 10^2$ 秒つまり約 $7$ 分かかります.
何とか待てる時間ですが, 瞬時ではないですね.
ましてや $6$ 段ですと $540$ 年ほどかかってしまいます.
やはりそのまま計算するのは現実的ではないですね.
(実際には $1$ 秒間に $3 \times 10^9$ パターンもチェックできないので, $5$ 段でさえ結構時間がかかります.)

しかし今回のように偶奇性に着目して問題にアプローチすれば, $3$ 段の場合は $10$ パターンも計算しないですみます.
規則や法則を見抜いて関係性などを見つけることが出来ればこんなにも計算量が減ることが分かります.
「プログラムを組んでパソコンに解かせばそんなことは関係ないではないか！」
という意見もあるかも知れませんが, 大きい数ではメモリが足りなくなったり, 余りにも時間がかかりすぎてしまうことがあります.
ですので, プログラムで問題を解くにしてもパソコンの気持ちになって工夫が必要になります.

問題を解くときは総当たりのように闇雲に問題に挑戦するのではなく, 何か計算をしたり試したりして少しでもできるだけ考えるようにしましょう.


因みに
$4$ 段の場合の偶奇の配置の候補は
\[\begin{array}{ccc} \textup{E} \ \textup{E} \ \textup{O} \ \textup{E} & \textup{E} \ \textup{E} \ \textup{O} \ \textup{O} \ & \textup{E} \ \textup{O} \ \textup{E} \ \textup{O} \\ \textup{E} \ \textup{O} \ \textup{O} & \textup{E} \ \textup{O} \ \textup{E} & \textup{O} \ \textup{O} \ \textup{O} \\ \textup{O} \ \textup{E} & \textup{O} \ \textup{O} & \textup{E} \ \textup{E} \\ \textup{O} & \textup{E} & \textup{E} \\ \end{array}\]となり, 解は
\[\begin{array}{cccc} 6 \ 10 \ 1 \ 8 & 8 \ 10 \ 1 \ 6 & 8 \ 3 \ 10 \ 9 & 8 \ 10 \ 3 \ 9 \\ 4 \ 9 \ 7 & 2 \ 9 \ 5 & 5 \ 7 \ 1 & 2 \ 7 \ 6 \\ 5 \ 2 & 7 \ 4 & 2 \ 6 & 5 \ 1 \\ 3 & 3 & 4 & 4 \\ \end{array}\]の $4$ つとなります.

また
$5$ 段の場合の偶奇の配置の候補は
\[\begin{array}{ccccc} \textup{E} \ \textup{E} \ \textup{O} \ \textup{E} \ \textup{O} & \textup{E} \ \textup{E} \ \textup{O} \ \textup{O} \ \textup{O} & \textup{E} \ \textup{O} \ \textup{O} \ \textup{O} \ \textup{O} & \textup{O} \ \textup{E} \ \textup{E} \ \textup{E} \ \textup{O} & \textup{O} \ \textup{E} \ \textup{E} \ \textup{O} \ \textup{O} \\ \textup{E} \ \textup{O} \ \textup{O} \ \textup{O} & \textup{E} \ \textup{O} \ \textup{E} \ \textup{E} & \textup{O} \ \textup{E} \ \textup{E} \ \textup{E} & \textup{O} \ \textup{E} \ \textup{E} \ \textup{O} & \textup{O} \ \textup{E} \ \textup{O} \ \textup{E} \\ \textup{O} \ \textup{E} \ \textup{E} & \textup{O} \ \textup{O} \ \textup{E} & \textup{O} \ \textup{E} \ \textup{E} & \textup{O} \ \textup{E} \ \textup{O} & \textup{O} \ \textup{O} \ \textup{O} \\ \textup{O} \ \textup{E} & \textup{E} \ \textup{O} & \textup{O} \ \textup{E} & \textup{O} \ \textup{O} & \textup{E} \ \textup{E} \\ \textup{O} & \textup{O} & \textup{O} & \textup{E} & \textup{E} \\ \end{array}\]となり, 解は
\[\begin{array}{c} 6 \ 14 \ 15 \ 3 \ 13 \\ 8 \ 1 \ 12 \ 10 \\ 7 \ 11 \ 2 \\ 4 \ 9 \\ 5 \\ \end{array}\]の $1$ つだけです.

更に, $6$ 段以上に関しては解が存在しないことが証明されています.
This post has been edited 2 times. Last edited by Kouichi Nakagawa, Dec 9, 2018, 9:10 PM
Reason: Revision by CPU part.

Comment

0 Comments

Shouts
Submit

  • whoa these css

    by rowern, Sep 29, 2020, 6:59 PM

  • Whoa! a post straight after 10 years (or maybe you just deleted some of them). Either way doesnt matter, how do you type latex though?

    by AnArtist, Jan 6, 2019, 7:49 PM

  • 面白いね!!!!

    by JunaBug13, Sep 9, 2016, 1:22 PM

  • im korean i don't understand english...

    i only understand pirate talk
    >.<

    by TrueshotBarrage, Jun 21, 2013, 1:07 AM

  • jesus christ are you serious

    by revelations, Mar 26, 2013, 10:40 PM

  • agreed :D $\filler$

    by tuanyuan2008, Jan 7, 2012, 1:32 AM

  • Smartest Guy Ever

    by ipwnuall, Dec 31, 2011, 5:09 AM

  • cool, and nice job on latex. please use english for us americans though, but nice job !!! :D

    by awesomeaopser257, Dec 29, 2010, 3:29 AM

  • this crazy skilled. Nice job on the latex. Could u use english instead though? :blush:

    by AlphaBetaTheta, Sep 13, 2010, 2:24 AM

  • I don't think he's having any contribs.

    by gauss1181, Aug 5, 2009, 7:54 PM

  • whoa
    nice blog
    its awesome
    can be a contrib? lol

    by SonyWii, Jul 1, 2009, 2:49 AM

  • hi

    by gauss1181, Jun 12, 2009, 11:22 PM

12 shouts
Tags
About Owner
  • Posts: 1719
  • Joined: Feb 16, 2007
Blog Stats
  • Blog created: May 21, 2007
  • Total entries: 4
  • Total visits: 5323
  • Total comments: 3
Search Blog
a