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.

1 \leq \sum_{cyc} \cos A \leq \frac{3}{2}

by Kouichi Nakagawa, Jan 4, 2008, 11:19 AM

三角形の $3$ 辺を $a, b, c$ とすると, 面積 $S$ は,
\begin{align*} S^2 &= \left(\frac{a + b + c}{2} \right) \left(\frac{a + b + c}{2} - a \right) \left(\frac{a + b + c}{2} - b \right) \left(\frac{a + b + c}{2} - c \right) \\ &= \frac{1}{16} (a + b + c)( - a + b + c)(a - b + c)(a + b - c) \end{align*}また, 外接円の半径 $R$ を用いると,
\[ S = \frac{abc}{4R} \ \ i.e. \ \ R = \frac{abc}{4S} \]と表すことができる。
さらに, 内接円の半径 $r$ を用いると,
\[ S = \frac{1}{2}r(a + b + c) \ \ i.e. \ \ r = \frac{2S}{a + b + c} \]とも表すことができるので,
\begin{align*} \frac{R}{r} &= \frac{abc(a + b + c)}{8S^2} \\ &= \frac{2abc}{( - a + b + c)(a - b + c)(a + b - c)} \end{align*}ここで,
$abc \geq ( - a + b + c)(a - b + c)(a + b - c) \iff \ \frac{1}{2} \left( \sum_{cyc} (a - b)^2(a + b - c) \right) \geq 0$
よって,
$\frac{abc}{( - a + b + c)(a - b + c)(a + b - c)} \geq 1$
故に,
$\frac{R}{r} = \frac{2abc}{( - a + b + c)(a - b + c)(a + b - c)} \geq 2$

また, 余弦定理より,
\begin{align*} \left( \sum_{cyc} \cos A \right) - 1 &= \left( \sum_{cyc} \frac{b^2 + c^2 - a^2}{2bc} \right) - 1 \\ &= \frac{( - a + b + c)(a - b + c)(a + b - c)}{2abc} \\ &= \frac{4}{8abc} \cdot \frac{16(a + b + c)( - a + b + c)(a - b + c)(a + b - c)}{16(a + b + c)} \\ &= \frac{1}{8SR} \cdot \frac{16S^2}{a + b + c} \\ &= \frac{2S}{R(a + b + c)} \\ &= \frac{r}{R} \end{align*}ここで, $\frac{R}{r} \geq 2 \iff 0 \leq \frac{r}{R} \leq \frac{1}{2}$ より,
\[ 1 \leq \sum_{cyc} \cos A \leq \frac{3}{2} \]
This post has been edited 1 time. Last edited by Kouichi Nakagawa, Dec 6, 2018, 1:45 PM
Reason: I revised a LaTeX error.

Trisection of the angle with Origami (折り紙での角の三等分)

by Kouichi Nakagawa, May 28, 2007, 6:15 AM

ABCD is a origami (square paper).
Point E, F is arbitrary point.
Point G is middle point of AF.
GH is parallel to AB.
We turn down the origami to Point F on AE, and Point A on GH.
We assume the point where point F appeared in F' and point A appeared in A'.
We get $\angle EAB = 3 \angle A'AB$

image will not appear why...
This image is following URL
Trisection of the angle with Origami.png
Attachments:

多項式の値の和が等しい集合についての一考察

by Kouichi Nakagawa, May 22, 2007, 3:17 AM

問題
$f(x) \in R[x], \deg(f(x))=n$とするとき,$\sum_{i=1}^{2^{n}}f(a_{i})=\sum_{i=1}^{2^{n}}f(b_{i})$ を満たす$a_{1}, a_{2}, \cdots a_{2^{n}}, b_{1}, b_{2}, \cdots b_{2^{n}}$を$1\sim2^{n+1}$の数字を用いて作ることが出来ることを証明せよ。



解答
$\deg(f(x))=n$に対して, $\sum_{i=1}^{m}f(a_{i})=\sum_{i=1}^{m}f(b_{i})$ を満たすということは, 以下の関係式を満たすのと同値
$\sum_{i=1}^{m}a_{i}{}^{j}=\sum_{i=1}^{m}b_{i}{}^{j}$ただし, $j=1, 2, \cdots, n$
この解を
$[a_{1}, a_{2}, \cdots a_{m}] = [b_{1}, b_{2}, \cdots b_{m}]$
と書くことにする。
このとき, 以下の 2 つの補題が成立する。


補題 1
$j=1, 2, \cdots, n$ に対して, $[a_{1}, a_{2}, \cdots a_{m}] = [b_{1}, b_{2}, \cdots b_{m}]$が成立するならば, 任意の$s, t \in R$に対して,
$[sa_{1}+t, sa_{2}+t, \cdots sa_{m}+t] = [sb_{1}+t, sb_{2}+t, \cdots sb_{m}+t]$
も成り立つ。

補題 1 の証明
$[sa_{1}+t, sa_{2}+t, \cdots sa_{m}+t] = [sb_{1}+t, sb_{2}+t, \cdots sb_{m}+t]$
$\iff \sum_{i=1}^{m}(sa_{i}+t){}^{j}=\sum_{i=1}^{m}(sb_{i}+t){}^{j}$
$\iff \sum_{i=1}^{m}f(sa_{i}+t)=\sum_{i=1}^{m}f(sb_{i}+t)$
ここで, $f(sx+t)=g(x)$とおくと,
$\sum_{i=1}^{m}g(a_{i})=\sum_{i=1}^{m}g(b_{i})$
と書き直すことが出来る。
$g(x) \in R[x], \deg(g(x))=n$を満たしているので, $\sum_{i=1}^{m}g(a_{i})=\sum_{i=1}^{m}g(b_{i})$ の解も $[a_{1}, a_{2}, \cdots a_{m}] = [b_{1}, b_{2}, \cdots b_{m}]$ と書くことができ, 条件を満たす。
よって補題 1 は成立する。


補題 2
$j=1, 2, \cdots, n$ に対して, $[a_{1}, a_{2}, \cdots a_{m}] = [b_{1}, b_{2}, \cdots b_{m}]$が成立するならば,
任意の$t \in R$に対して,
$j=1, 2, \cdots, n, n+1$ に対して, $[a_{1}, a_{2}, \cdots a_{m}, b_{1}+t, b_{2}+t, \cdots b_{m}+t] = [b_{1}, b_{2}, \cdots b_{m}, a_{1}+t, a_{2}+t, \cdots a_{m}+t]$が成立する。

補題 2 の証明
$j=1, 2, \cdots, n$のとき,
$[a_{1}, a_{2}, \cdots a_{m}, b_{1}+t, b_{2}+t, \cdots b_{m}+t] = [b_{1}, b_{2}, \cdots b_{m}, a_{1}+t, a_{2}+t, \cdots a_{m}+t]$
$\iff \sum_{i=1}^{m}a_{i}{}^{j}+\sum_{i=1}^{m}(b_{i}+t){}^{j}= \sum_{i=1}^{m}b_{i}{}^{j}+\sum_{i=1}^{m}(a_{i}+t){}^{j}$
$\iff \sum_{i=1}^{m}(b_{i}+t){}^{j}= \sum_{i=1}^{m}(a_{i}+t){}^{j}$
補題 1 より両辺は等しい。
よって$j=1, 2, \cdots n$ のときは成立する。
$j=n+1$のとき,
$[a_{1}, a_{2}, \cdots a_{m}, b_{1}+t, b_{2}+t, \cdots b_{m}+t] = [b_{1}, b_{2}, \cdots b_{m}, a_{1}+t, a_{2}+t, \cdots a_{m}+t]$
$\iff \sum_{i=1}^{m}a_{i}{}^{n+1}+\sum_{i=1}^{m}(b_{i}+t){}^{n+1}= \sum_{i=1}^{m}b_{i}{}^{n+1}+\sum_{i=1}^{m}(a_{i}+t){}^{n+1}$
$\iff \sum_{i=1}^{m}a_{i}{}^{n+1}+\sum_{i=1}^{m}\sum_{k=0}^{n+1}\binom{n+1}{k}b_{i}{}^{n+1-k}t^{k}= \sum_{i=1}^{m}b_{i}{}^{n+1}+\sum_{i=1}^{m}\sum_{k=0}^{n+1}\binom{n+1}{k}a_{i}{}^{n+1-k}t^{k}$
$\iff \sum_{i=1}^{m}a_{i}{}^{n+1}+\sum_{i=1}^{m}b_{i}{}^{n+1}+\sum_{i=1}^{m}\sum_{k=1}^{n+1}\binom{n+1}{k}b_{i}{}^{n+1-k}t^{k}= \sum_{i=1}^{m}b_{i}{}^{n+1}+\sum_{i=1}^{m}a_{i}{}^{n+1}+\sum_{i=1}^{m}\sum_{k=1}^{n+1}\binom{n+1}{k}a_{i}{}^{n+1-k}t^{k}$
$\iff \sum_{i=1}^{m}\sum_{k=1}^{n+1}\binom{n+1}{k}b_{i}{}^{n+1-k}t^{k}= \sum_{i=1}^{m}\sum_{k=1}^{n+1}\binom{n+1}{k}a_{i}{}^{n+1-k}t^{k}$
ここで, 両辺は$n$次式の和であり, 補題 1 より両辺は等しい。
よって$j=n+1$のときも成立する。
よって補題 2 は成立する。

本題
$n=1$ のとき, $[1, 4]=[2, 3]$ は条件を満たすのは明らか。
また, この解は $1\sim2^{1+1}$を用いて作られている。
$k=n$ のとき, 解$[a_{1}, a_{2}, \cdots a_{2^{n}}] = [b_{1}, b_{2}, \cdots b_{2^{n}}]$は$1\sim2^{n+1}$を用いて作られていると仮定すると,
$k=n+1$ のとき, 補題 2 を用いて,
$[a_{1}, a_{2}, \cdots a_{2^{n}}, b_{1}+t, b_{2}+t, \cdots b_{2^{n}}+t] = [b_{1}, b_{2}, \cdots b_{2^{n}}, a_{1}+t, a_{2}+t, \cdots a_{2^{n}}+t]$
と書ける。ここで$t=2^{n+1}$ とおけば, これらの解は$1\sim2^{n+2}$を用いて作られていることが分かる。
よって, PMI より題意は成立する。
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: 5329
  • Total comments: 3
Search Blog
a