| NO.1454 | 2004.3.10. | teki | ８６．同心円の分割・その後(1) |
８６．同心円の分割にあるＡ君からの宿題に
ついてです。
答えは 二上（２乗）山 金剛（根号）山 でしょうか？
| NO.1455 | 2004.3.10. | 三角定規 | ８６．同心円の分割・その後(2) |
８６．同心円の分割にあるＡ君からの宿題の答です。
(1) 山2 … 二上山（にじょうさん）
(2) √山 … 金剛山（こんごうさん）
(2)はすぐにわかりましたが、(1)は地図を捜しました。
もっとも「奈良から見える」というヒントがあればこそですが…。
| NO.1456 | 2004.3.18. | 小学名探偵 | ランダムウォークに関する問題(2) |
（解）
ＸＹ平面の経路図において、２つの経路が分かれてから出会うまでの区間ごとに 45度線について対称な経路に変換することで両集合の１対１対応を示します：
準備：
ＸＹ平面の経路図における最短経路問題として捉える：
ＸＹ平面座標系における非負の整数座標（a, b)で与えられる格子点において、 aは一次元ランダムウォークの元の位置から「右にa歩」を表し、 bは「左にb歩」を表すとします。
これにより、 2N歩目に元の位置に戻る一次元ランダムウォークの 経路の個数を求める問題は、原点のノード（0，0）からノード（N, N）までの 最短経路の個数を求める問題に帰着されます。この最短経路の個数は 2N個からN個を選ぶ組み合わせの数2N!/N!N!になります。
原点のノード（0，0）からノード（N, N）までの最短経路を （2N歩の、または単に）帰巣型経路と名付けます。
また、2N歩目までに一度も元の位置を経ることがない一次元ランダムウォークの 経路の個数を求める問題は、原点のノード（0，0）から、 一度もｙ＝ｘで定められる45度線上の格子点（x, x）を訪れることなく、 L+M=２Ｎ（Ｌ、ＭはＮでない非負の整数）を満たす 各ノード（L, M）までの最短経路の個数を求める問題に帰着されます。 この最短経路を（２N歩の、または単に）不如帰経路と名付けます。
帰巣型経路と不如帰経路間の変換を行う際に、ランダムウォークの 最初の一歩が右ステップである（スタートノード（0，0）からノード（1，0）に進む） 経路同士間で変換し、 最初の一歩が左ステップである（スタートノード（0，0）からノード（0，1）に進む） 経路同士間で変換することにします。
（１）順変換：
最初の一歩が右ステップである帰巣型経路（R帰巣型経路）の任意の１つを 最初の一歩が右ステップである不如帰経路（R不如帰経路）に変換する方法：
この場合、R帰巣型経路のスタートノード（0, 0）から ゴールノード（N, N）に向かって辿りながら、順次、 R不如帰経路の各部分を決めていきます。
ルール@：＊＊スタートからR帰巣型経路の左折・分岐ノードまで追従＊＊
R帰巣型経路がスタートノード（0，0）から左折するノード、すなわち 左折・分岐ノード（ｘ，0）に達するまで、 変換後経路（Ｒ不如帰経路）はＲ帰巣型経路と同じ道を辿ります。
ルールA：＊＊左折・分岐ノードから出会いノードまで45度線対称変換＊＊
R帰巣型経路が左折・分岐ノードから次の出会いノード（無ければゴール）に進む まで、変換後経路（Ｒ不如帰経路）は左折・分岐ノードからの45度線について Ｒ帰巣型経路と線対称な道を通ります。 すなわち、左折・分岐ノードをＸ，Ｙ座標軸の平行移動により 改めて原点（0，0）に置き換えたＸＹ’座標系で見たとき、 左折・分岐ノードから次の出会いノード（Ｘ，Ｘ）までの間、 Ｒ帰巣型経路の各ノード（x, y）におけるｘとｙを交換した位置（y, x）が 変換後の経路（Ｒ不如帰経路）のノードになります。
ルール@’：＊＊出会いノードから左折・分岐ノードまで追従＊＊
出会いノードで同じ位置になったら、次にＲ帰巣型経路が左折するノード（出会い ノードで左折する可能性あり）に達するまで、 Ｒ不如帰経路はＲ帰巣型経路と同じ道を辿ります。 このルールは、スタートノード＝出会いノードと見て、ルール@と同じです。
（変換例）８歩のＲ帰巣型経路として次を与えます。
８歩のＲ帰巣型経路（スタート(0,0)、ゴール(4,4)）： (0,0) (1,0) (1,1) (2,1) (2,2) (3,2) (4,2) (4,3) (4,4) これを変換すると、 ８歩のＲ不如帰経路（スタート(0,0)、ゴール(6,2)）： (0,0) (1,0) (2,0) (2,1) (3,1) (3,2) (4,2) (5,2) (6,2) が出来ます。このＲ帰巣型経路について、 出会いノード：(0,0)、(2,1)、(3,2)、 左折・分岐ノード：（1,0)、(2,1)、(4,2) です。 最初の左折・分岐ノード(1,0)から次の出会いノード(2,1)まで、 Ｒ帰巣型経路は(1,0)、(1,1)、(2,1)を通るのに対して、 Ｒ不如帰経路は(1,0)、(2,0)、(2,1)を通り、両者は 左折・分岐ノード(1,0)と次の出会いノード(2,1)を結ぶ45度線について対称です。 同様に、 ２番目の左折・分岐ノード(2,1)から次の出会いノード(3,2)まで、 Ｒ帰巣型経路は(2,1)、(2,2)、(3,2)を通るのに対して、 Ｒ不如帰経路は(2,1)、(3,1)、(3,2)を通り、両者は 左折・分岐ノード(2,1)と次の出会いノード(3,2)を結ぶ45度線について対称です。 また、最後の左折・分岐ノード（4,2）から各ゴール（4,4）、（6,2）まで、 Ｒ帰巣型経路は(4,2)、(4,3)、(4,4)に進むのに対して、 Ｒ不如帰経路は(4,2)、(5,2)、(6,2)に進み、両者は 最後の分岐ノード（4,2）からの45度線（最後の分岐ノード(4,2)と実現されていない 仮想の出会いノード(6,4）を結ぶ45度線）について対称です。
（２）逆変換：
最初の一歩が右ステップである不如帰経路（R不如帰経路）の任意の１つを 最初の一歩が右ステップである帰巣型経路（R帰巣型経路）に変換する方法： この場合、R不如帰経路のゴールノード（Ｌ, Ｍ）から スタートノード（0, 0）にさかのぼる方向で辿りながら、順次、 R帰巣型経路の各部分を決めていきます。 これが都合良いのは、変換（１）と（２）を互いに逆オペレーションとして 構成できることです。たとえば、
(a)順変換（１）の出会いノードは逆変換（２）における 不如帰経路の右折・分岐ノードになります（出会い／分岐）。
(b)順変換（１）でいう帰巣型経路の左折・分岐ノードは、 逆変換（２）では出会いノードになります（分岐／出会い）。
(c)順変換（１）における「最後」の左折・分岐ノードは 逆変換（２）における「最初」の出会いノードになります。
(d)順変換（１）で述べた順方向で見たときの 「最初」の左折・分岐ノードは、さかのぼる方向で見ると 「最後」の出会いノードになります。
ルールT：＊＊ゴールから出会いノードまで45度線対称変換＊＊
さかのぼる方向において、R不如帰経路がゴールノード（Ｌ，Ｍ）から最初の 出会いノードに進むまで、 変換後経路（Ｒ帰巣型経路）は格子点（Ｌ，Ｎ）からの45度線について Ｒ不如帰経路と線対称な道を通ります。格子点（Ｌ，Ｎ）はR不如帰経路の ゴールノード（Ｌ，Ｍ）に関するｙ＝Ｌと変換後経路（Ｒ帰巣型経路）の ゴールノード（Ｎ，Ｎ）に関するｘ＝Ｎとの交点（仮想的な右折・分岐ノード） で定められます。この45度線＝最初の出会いノードからの45度線です。ルールU：＊＊出会いノードからＲ不如帰経路の右折・分岐ノードまで追従＊＊
出会いノードで同じ位置になったら、次に、Ｒ不如帰経路が 右折するノード（右折・分岐ノード）に達するまで（無ければスタートノードまで）、 変換後経路（Ｒ帰巣型経路）はＲ不如帰経路と同じ道を辿ります。ルールT’：＊＊右折・分岐ノードから出会いノードまで45度線対称変換＊＊
不如帰経路の右折・分岐ノードから次の出会いノードまでは、 右折・分岐ノードからの45度線について不如帰経路と対称に 帰巣型経路を作ります。 このルールはルールTと基本的に同じです。
（３）最初が左ステップ同士の順変換：
ルール@：＊＊スタートからＬ帰巣型経路の右折・分岐ノードまで追従＊＊
ルールA：＊＊右折・分岐ノードから出会いノードまで45度線対称変換＊＊
ルール@’：＊＊出会いノードから右折・分岐ノードまで追従＊＊
（４）最初が左ステップ同士の逆変換：
ルールT：＊＊ゴールから出会いノードまで45度線対称変換＊＊
ルールU：＊＊出会いノードからＬ不如帰経路の左折・分岐ノードまで追従＊＊
ルールT’：＊＊左折・分岐ノードから出会いノードまで45度線対称変換＊＊
（５）変換後経路の形式：
比較のために、Ｒ不如帰経路からＲ帰巣型経路に逆変換したとき、変換後の経路 （Ｒ帰巣型経路）をスタートからゴールに向けて形式的に示すとともに、直ぐ下に、 上の順変換後のＲ不如帰経路の形式を並べてみると、次のようになります。
＊＊比較＊＊：
[ ]は仮想、（ ）は0回を含む ［分岐］スタートノード, 追従,出会い, (45度線対称), (分岐), (追従), (出会い), ．．．，45度線対称, ゴールノード，［分岐］ ［出会い］スタートノード, 追従, 分岐, (45度線対称), (出会い), (追従), (分岐), ．．．，45度線対称, ゴールノード，［出会い］
（６）順変換後経路∈Ｒ不如帰経路セット、逆変換後経路∈Ｒ帰巣型経路：
ここでは、Ｒ帰巣型経路を順変換（１）の方法で変換したとき、変換後の経路が 必ずＲ不如帰経路になることと、 Ｒ不如帰経路を逆変換（２）の方法で変換したとき、変換後の経路が 必ずＲ帰巣型経路になることを明らかします。 「順変換後経路∈Ｒ不如帰経路セット」になる理由は以下の通りです。 Ｒ不如帰経路は、（0，0）の後、（1，0）から、ｙ＝ｘで定められる 45度線上の格子点を一度も訪れることがない、 Ｌ＋Ｍ＝2Ｎ、Ｌ＞Ｍを満たすゴールノード（Ｌ，Ｍ） までの最短経路として定義されます。
順変換後経路は、変換前の経路であるＲ帰巣型経路が初めて左折する（最初の 左折・分岐ノード（k, 0）に進む）まではＲ帰巣型経路と同じ位置であるＸ軸上に あります。
それ以降は、ｙ＝ｘより右側（ｙ＝ｘ上をプラスの方向に進んで見たときに右側） にある最初の左折・分岐ノードからの45度線ｙ＝ｘ−k（1≦ｋ≦Ｎ）の上かそれ より右側にあります。すなわち、順変換後経路は、後の出会いノードにおいて 45度線ｙ＝ｘ−kの上にくる可能性があるだけで、この45度線ｙ＝ｘ−kの 左側になることは決してありません。
順変換後経路は、ステップごとにｘ+1かｙ+1して、次の経路位置ノードに進みます。 したがって、順変換後経路は、（0，0）の後、（1，0）から、 ｙ＝ｘ上の格子点を訪れることなしに、Ｌ＋Ｍ＝2Ｎ、Ｌ＞Ｍを満たす ゴールノード（Ｌ，Ｍ）まで進む最短経路（＝Ｒ不如帰経路）になります。
「逆変換後経路∈Ｒ帰巣型経路セット」になる理由は次の通りです。 Ｒ帰巣型経路は、（0，0）の後、（1，0）から（Ｎ，Ｎ）までの最短経路として 定義されます。 逆変換（２）において、逆変換後経路は、最初（Ｎ，Ｎ）にあり、その後、 ステップのたびにｘ−1かｙ−1により次のノードが決められます。そして、 Ｒ不如帰経路との最後の出会いノードで、Ｘ軸に達し、その後 Ｘ軸に沿って原点(0, 0)に至ります。 最後の出会いノードはｋを1以上の正整数として（ｋ，0）で与えられるので （なぜなら、最後の出会いノードの位置は、最後の45度線変換に関する対称軸である 45度線ｙ＝ｘ−ｋと、Ｒ不如帰経路の最後の通り道であるＸ軸との交点であるので）、 逆変換後経路は（1，0）を通ります。したがって、逆変換後経路は必ず Ｒ帰巣型経路になります。
（７）帰巣型経路セットと不如帰経路セットの一対一対応：
Ｒ帰巣型経路セットの任意の１要素Ai（任意の１つのＲ帰巣型経路Ai）について、 順変換（１）の方法で変換したＲ不如帰経路F(Ai)を、 逆変換（２）の方法で変換(invF)すると元のＲ不如帰経路Aiが復元されます。 すなわち、invF(F(Ai))=Aiが成り立ちます（前提）。
同様に、 Ｒ不如帰経路セットの任意の１要素Bi（任意の１つのＲ帰巣型経路Bi）について、 逆変換（２）の方法で変換したＲ帰巣型経路invF(Bi)を、 順変換（１）の方法で変換(F)すると元のＲ不如帰経路Biが復元されます。 すなわち、F(invF(Bi))=Biが成り立ちます（前提）。
したがって、 Ｒ帰巣型経路セットに含まれる任意の異なる２要素Ai, Ajは順変換（１）により、 Ｒ不如帰経路セットの異なる２要素に変換されます。同様に、 Ｒ不如帰経路セットに含まれる任意の異なる２要素Bi, Bjは逆変換（２）により、 Ｒ帰巣型経路セットの異なる２要素に変換されます。したがって、 Ｒ帰巣型経路セットとＲ不如帰経路セットは一対一で対応し、 Ｒ帰巣型経路の個数とＲ不如帰経路の個数は等しくなります。
同様の議論で、最初に、左ステップするランダムウォーク （ノード（0，0）から（0，1）に進む経路）について Ｌ帰巣型経路セットとＬ不如帰経路セットは一対一で対応し、 Ｌ帰巣型経路の個数とＬ不如帰経路の個数は等しくなります。
よって、２Ｎ歩の帰巣型経路のセットと２Ｎ歩の不如帰経路のセットは 1対1で対応します。
（８）一対一対応の前提の証明：
互いに逆のオペレーションであることから自明ですが いま、ノード列P0，P1, ．．．, P2nで 表現されるＲ／Ｌ帰巣型経路Ｋを順変換（１）で変換して、 Ｒ／Ｌ不如帰経路Ｈが出来たとします。 このノード列をP*0, P*1, ．．．, P*2n で表記します。Ｐに付けた「*」印は、そのノードが「追従」区間にあるノード、 すなわち変換（１）または（２）に関わらず、位置が変換前と変わらない ノードであるか（例えば、スタートノードP*0=P0, やP*1=P1）、あるいは 「45度線対称」区間内において、Ｒ／Ｌ帰巣型経路Ｋの分岐ノード からの45度線について変換前のノードPkと対称な位置にある ノードP*kであることを表しています。 このＲ／Ｌ不如帰経路Ｈを逆変換（２）で変換すると元のＲ／Ｌ帰巣型経路Ｋが 復元されます。理由は次の通りです。 分岐ノードからの45度線（「45度線対称変換」の対称軸）は変換（１）、（２）に 対して不変です。 したがって、変換（１）で用いた「45度線対称変換」の対称軸である45度線が 変換（２）で再度、元のノードPkと対称な位置にあるノードP*kに対して 適用されます。 同じ45度線を対称軸として、順変換（１）と逆変換（２）により２回の45度 対称変換が行われる結果、45度対称変換区間内のノードの位置は元に戻ります。 逆変換（２）の後で順変換（１）を行うと元の不如帰経路が再生されることも 同様にして示されます。
（９）ランダムウォークダンスペア：
変換（１）、（２）によって対応づけたＲ帰巣型経路とＲ不如帰経路を、一次元上で 踊るダンサーのペアに見立て、二人のダンスを想像してみてください。 たとえば、最初、男性と女性は原点でお互いに向かい合っています。右方向を向いた 男性が左足を踏み出すと、左方向を向いた女性はそれに合わせて右足を引きます。 そして二人とも足を揃えて一つのステップが完了します。 これが、ペアの最初の右ステップになります。 続けて、男性が右足を踏み出すとしたら、女性はそれに合わせて左足を引きます。 そして足を揃えます。これは２番目の右ステップです。 そのうち、男性は原点に戻る方向に右足か左足を引きます（男性の最初の 左ステップ）。このとき、二人は離れ、 女性は左足か右足を引きます（女性は右ステップ）。そして二人とも足を揃えます。 その後、二人は別れた位置（点）について対称に踊ります。 つまり、男性の右ステップと左ステップに合わせて女性は左ステップと右ステップを します。そのうち、 ペアは再び、接触する（出会う）かも知れません。出会いの位置はペアが別れた位置です。 出会った後、ペアは背中あわせの位置関係になること（すれ違うこと）はありません。 つまり、出会った後、男性が右ステップを続ければ、女性もそれに合わせて右ステップを 行います。その後、男性が原点に近づく方へ左ステップを行うと女性は原点から 遠ざかる方へ右ステップを行って、ペアは離れ、点対称のダンスが再開されます。 ２Ｎステップ目に男性が原点に戻ったところでダンスは終了です。 一人の動きはランダムですが、ペアにすると、対称的な動きが生まれるので、 ステップ数２Ｎ次第ですがペアのダンスといえないこともないようです。 巻き戻して再生すると、ペアが原点に揃ったところでダンスが終わります。
（１０）別解：
ランダムウォークダンスペア（９）の説明から次のような解法を思い付くことが出来ます。
L2n＝ΣRi
＝R1＋R2＋．．．＋R2n
と定義します。ここに、Riは互いに独立した乱数で、 右ステップならばRi＝1 左ステップならばRi＝−1 になります。 これにより、L2nは2ｎ歩目の一次元ランダムウォークの位置を表します。そして、 ＸＹ平面の格子点、すなわち整数座標（x, y）によりx歩目のランダムウォークの 位置yをLの値で表現します。つまり、歩数対位置の関係をＸＹ平面上に示すことに なります。
反射則：格子点P1＝（x1, y1）、 格子点P2＝（x2, 0）、格子点P3＝（x3, y3）について、 x3＞x2＞x1≧0とすると、 P1からP2を経てP3までの経路の個数は、P1’＝（x1, −y1）として、 P1’からP2を経てP3までの経路の個数に等しく、 また、P3’＝（x3, −y3）として、 P1からP2を経てP3’までの経路の個数に等しくなります。 なぜなら、前者の場合、x1からx2までの区間でＸ軸について対称な経路を 考えれば良く、後者の場合、x2からx3までの区間でＸ軸について対称な経路を 考えれば１対１対応は明らかです。 また、P2＝（x2, y2）、P3＝（x3, y2＋ｄ)とおくと、 P3’＝（x3, y2−ｄ）になるので、 P1からP2を経てP3までの経路のセットは P1からP2を経てP3’までの経路のセットと１対１で対応します。
歩数対位置の関係をＸＹ平面上に表現するバージョンにおいて、 Ｒ帰巣型経路を次のようにしてＲ不如帰経路に変換します。 最初を右ステップとするＲ経路の定義からスタートを（0, 0）、次を（1, 1）とし、 Ｒ帰巣型経路が初めて左ステップをする格子点（x2, y2）まで、 変換後経路にＲ帰巣型経路と同じ道を辿らせます。 その後、ｙ＝y2についてＲ帰巣型経路と対称な経路を作り、この対称経路変換を、 再度、格子点（x3, y2）で出会うことがあれば、それまでの間、続け、 再会がなければゴール（2n, 0）まで続けます。 再会したときは、その後、Ｒ帰巣型経路が左ステップをする格子点（x4, y4）まで （ここに、y4≧y2）、 変換後経路にＲ帰巣型経路と同じ道を辿らせます。 Ｒ帰巣型経路が左ステップをした後は、再び、対称経路変換を行って ｙ＝y4についてＲ帰巣型経路と対称な経路を作っていきます。 このようにして変換される経路は変換前のＲ帰巣型経路と１対１で対応する Ｒ不如帰経路になります。 Ｒ不如帰経路をゴールからスタートにさかのぼる方向でＲ帰巣型経路に変換する方法の 詳細はこれまでの説明から明らかと思われますので省略します。 なお、Ｒ帰巣型経路のセットをＬ不如帰経路のセットに１対１対応で変換する 方法や、Ｌ帰巣型経路のセットをＲ不如帰経路のセットに１対１対応で変換する 方法も反射則を区間別に利用して簡単に行えます。具体的には、Ｌ帰巣型経路の 全区間に反射則を適用すれば、Ｘ軸について対称なＲ帰巣型経路が出来ますから、 このＲ帰巣型経路に上の変換を施してＲ不如帰経路を作るようにすれば、 変換の合成でＬ帰巣型経路がＲ不如帰経路に１対１対応で変換されます。
（１１）一対一対応は一次元ランダムウォークでのみ成立：
次元が２以上では、原点の戻る経路の数に比べ、原点に戻ることのない経路が増え、 帰巣型経路の個数＜不如帰経路の個数になります。ペアのダンスはもう無理です。
以下は受け売りです。 Ｄ次元格子における対称（隣りの格子点へ移る確率が方向によらず同じである） ランダムウォークがいつかは元の位置に戻る確率は再帰確率Ｐ_Dと呼ばれます。 この再帰確率に関して、1921年にポリア（Goerge Polya）が定理を発表しています。 それによると、３次元以上の格子空間では、再帰確率は１未満になります。つまり、 無限にステップを踏んでも原点に戻れない正の確率が存在します。たとえば、３次元の 単純立方格子空間では、再帰確率Ｐ３はおよそ0.34に、100次元では約0.005に なるそうです。Ｄが大きいとき、素朴には、ＰDは１／（2Ｄ−１）で近似されます。
２Ｎ歩目に初めて原点に戻る確率をM(2N)と書くと、 Ｎ→∞に対して、 ＰD＝ΣM(2N)で定義されます。 そして、途中で何度原点に戻ってもよいが２Ｎ歩目に原点にいる確率をR(2N)と書くと、 Ｎ→∞に対して、 ΣM(2N)＝１−１／ΣR(2N) になるそうです。
ΣR(2N)は特性関数（母関数）を利用して計算されるそうです。
| NO.1457 | 2004.3.18. | 水の流れ | ３次関数 |
太郎さんは大学入試問題集をみていて、以下の問題を見つけました。
３次関数ｆ(ｘ)＝ａｘ３＋ｂｘ２＋ｃｘ＋ｄ は次の２つの条件を満たしているとき、 この関数ｆ(ｘ)を求めよ。
（１） ｆ(１)＝１，ｆ(−１)＝−１
（２） 区間−１＜ｘ＜１で極大値１、極小値−１をとる
E-mail
戻る