数の配列 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　下図のような格子状の表の枠内に次の条件を満たすように、０以上の整数を書き込む。

（条件）　１．左上隅は、「０」と書き込む。

２．どの枠においても、

「その枠と同じ行で、枠の左側にある数」　および　「その枠と同じ列で、枠の上側にある数」

とは異なる数のうち、最小の数を書き込む。


　この条件で、幾つか数を書き込むと

となる。そこで、問題です。

　４０行２０列目の枠内には、どんな数が書き込まれているでしょうか？

もっと一般に、ｍ行ｎ列目の枠内には、どんな数が書き込まれているでしょうか？
































（答え）　まずは条件に従って地道に表を埋めてみよう。

　上表から、４０行２０列目の枠内には、数「５２」が書き込まれている。

（コメント）　表を手計算で埋めていくと、２つ毎、４つ毎、８つ毎という規則性が垣間見える。
　　　　　　何となく、２進法が関係していそうな．．．雰囲気！

　下表で各数を２進数に展開してみると、

となる。

　このとき、ｍ−１、ｎ−１の数を２進数にすると、ｍ行ｎ列目の数は、各桁を比較して

　共通の数（０　または　１）ならば、　０　、異なっていれば　１

とおくことにより生成されていることが分かる。

　この性質に注目して当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんが、ｍ行ｎ列目の数
の求め方を示された。（平成２２年７月１７日付け）

（１）　ｍ行１列目の数 Ａ＝ｍ−１ を２進数に展開する。

　Ａ＝ａ_p・２^p＋ａ_p-1・２^p-1＋・・・＋ａ₁・２＋ａ₀　　（　ａ_ｋ＝０　または　１　）

（２）　１行ｎ列目の数 Ｂ＝ｎ−１ を２進数に展開する。

　Ｂ＝ｂ_p・２^p＋ｂ_p-1・２^p-1＋・・・＋ｂ₁・２＋ｂ₀　　（　ｂ_ｋ＝０　または　１　）

（３）　このとき、ｍ行ｎ列目の数 Ｃ は、次のように２進数に展開される。

　Ｃ＝ｃ_p・２^p＋ｃ_p-1・２^p-1＋・・・＋ｃ₁・２＋ｃ₀　　（　ｃ_ｋ＝０　または　１　）

　ただし、　ｋ＝０、１、２、・・・、ｐ　で、

　ａ_ｋ＋ｂ_ｋ＝０　または　２　　ならば、　ｃ_ｋ＝０

　ａ_ｋ＋ｂ_ｋ＝１　ならば、　ｃ_ｋ＝１

（例）　４０行２０列目の数を求めよ。

　Ａ＝３９＝１００１１１₂　、Ｂ＝１９＝０１００１１₂

より、各桁を高い方から計算して、Ｃ＝１１０１００₂

よって、　Ｃ＝１・２⁵＋１・２⁴＋０・２³＋１・２²＋０・２＋０＝３２＋１６＋４＝５２


（コメント）　一見ランダムに入りそうな数ですが、きちんとした法則の下にあるのですね！
　　　　とても不思議な感覚です。ＧＡＩ さんに感謝します。

　さて、問題は上記のような操作をして所要のものが何故得られるかという点である。　

　上表で、４行１列目の数 Ａ＝３ と １行３列目の数 Ｂ＝２ から、４行３列目の数 Ｃ＝１ が
できたわけであるが、Ｃ＝１ は２行１列目の数であり、１行４列目の数 Ａ＝３ とからできる
数は、何故か、Ｂ＝２　である．．．面白い性質ですね！

　いま、２つの数 Ａ　、Ｂ が、２進数に展開されて、

　Ａ＝ａ_p・２^p＋ａ_p-1・２^p-1＋・・・＋ａ₁・２＋ａ₀　　（　ａ_ｋ＝０　または　１　）

　Ｂ＝ｂ_p・２^p＋ｂ_p-1・２^p-1＋・・・＋ｂ₁・２＋ｂ₀　　（　ｂ_ｋ＝０　または　１　）

であるとき、

　ａ_ｋ＋ｂ_ｋ＝０　または　２　　ならば、　ｃ_ｋ＝０

　ａ_ｋ＋ｂ_ｋ＝１　ならば、　ｃ_ｋ＝１

で定められる２進数 Ｃ＝ｃ_p・２^p＋ｃ_p-1・２^p-1＋・・・＋ｃ₁・２＋ｃ₀　　（　ｃ_ｋ＝０　または　１　）

のことを、　Ｃ＝Ｆ（Ａ ，Ｂ）　と表すことにする。

例　　Ｆ（０ ，０）＝０　、Ｆ（ｍ ，０）＝ｍ　、Ｆ（０ ，ｎ）＝ｎ　、Ｆ（３ ，２）＝１

　Ｆ（Ｆ（３ ，２） ，３）＝２　、・・・

　果たして、　Ｆ（Ｆ（Ａ ，Ｂ） ，Ａ）＝Ｂ　という性質は、一般的に成り立つのだろうか？

　実際に、計算して確認してみよう。

　いま、２つの数 Ａ　、Ｂ

　Ａ＝ａ_p・２^p＋ａ_p-1・２^p-1＋・・・＋ａ₁・２＋ａ₀　　（　ａ_ｋ＝０　または　１　）

　Ｂ＝ｂ_p・２^p＋ｂ_p-1・２^p-1＋・・・＋ｂ₁・２＋ｂ₀　　（　ｂ_ｋ＝０　または　１　）

に対して、　Ｆ（Ａ ，Ｂ）＝ｃ_p・２^p＋ｃ_p-1・２^p-1＋・・・＋ｃ₁・２＋ｃ₀　　（　ｃ_ｋ＝０　または　１　）

である。ただし、

　ａ_ｋ＋ｂ_ｋ＝０　または　２　　ならば、　ｃ_ｋ＝０

　ａ_ｋ＋ｂ_ｋ＝１　ならば、　ｃ_ｋ＝１

このとき、

　Ｆ（Ｆ（Ａ ，Ｂ） ，Ａ）＝ｄ_p・２^p＋ｄ_p-1・２^p-1＋・・・＋ｄ₁・２＋ｃ₀　　（　ｄ_ｋ＝０　または　１　）

において、ｄ_ｋ　は、

　ｃ_ｋ＋ａ_ｋ＝０　または　２　　ならば、　ｄ_ｋ＝０

　ｃ_ｋ＋ａ_ｋ＝１　ならば、　ｄ_ｋ＝１

により定められる。ここで、

なので、　ｄ_ｋ＝ｂ_ｋ　すなわち、　Ｆ（Ｆ（Ａ ，Ｂ） ，Ａ）＝Ｂ　が成り立つ。

　よって、ｍ行１列目の数 Ａ と １行ｎ列目の数 Ｂ から作られる数 Ｃについて、

　Ｆ（Ｆ（Ａ ，Ｂ） ，Ａ）＝Ｂ

の成り立つことが示された。

　同様にして、　Ｆ（Ｆ（Ａ ，Ｂ） ，Ｂ）＝Ａ　が成り立つ。

実際に、

　Ｆ（Ａ ，Ｂ）＝ｃ_p・２^p＋ｃ_p-1・２^p-1＋・・・＋ｃ₁・２＋ｃ₀　　（　ｃ_ｋ＝０　または　１　）

　Ｂ＝ｂ_p・２^p＋ｂ_p-1・２^p-1＋・・・＋ｂ₁・２＋ｂ₀　　（　ｂ_ｋ＝０　または　１　）

に対して、

　Ｆ（Ｆ（Ａ ，Ｂ） ，Ｂ）＝ｅ_p・２^p＋ｅ_p-1・２^p-1＋・・・＋ｅ₁・２＋ｅ₀　　（　ｅ_ｋ＝０　または　１　）

の ｅ_ｋ は、

　ｃ_ｋ＋ｂ_ｋ＝０　または　２　　ならば、　ｅ_ｋ＝０

　ｃ_ｋ＋ｂ_ｋ＝１　ならば、　ｅ_ｋ＝１

により定められる。ここで、

なので、　ｅ_ｋ＝ａ_ｋ　すなわち、　Ｆ（Ｆ（Ａ ，Ｂ） ，Ｂ）＝Ａ　が成り立つ。

　この性質を用いると、ｍ行１列目の数 Ａ と １行ｎ列目の数 Ｂ から作られるｍ行ｎ列目の
数 Ｃについて、

　どの枠においても、

「その枠と同じ行で、枠の左側にある数」および「その枠と同じ列で、枠の上側にある数」

とは異なる数

であることが容易に示される。

　実際に、　Ｆ（Ａ ，Ｂ）＝Ｆ（Ａ ，Ｂ’）　 （ただし、Ｂ’＜Ｂ）　であるとすると、

　Ｆ（Ｆ（Ａ ，Ｂ） ，Ａ）＝Ｂ　、　Ｆ（Ｆ（Ａ ，Ｂ’） ，Ａ）＝Ｂ’

において、　Ｆ（Ａ ，Ｂ）＝Ｆ（Ａ ，Ｂ’）　から、　Ｂ＝Ｂ’　となり矛盾である。

　さらに、　Ｆ（Ａ ，Ｂ）＝Ｆ（Ａ’ ，Ｂ）　 （ただし、Ａ’＜Ａ）　であるとすると、

　Ｆ（Ｆ（Ａ ，Ｂ） ，Ｂ）＝Ａ　、　Ｆ（Ｆ（Ａ’ ，Ｂ） ，Ｂ）＝Ａ’

において、　Ｆ（Ａ ，Ｂ）＝Ｆ（Ａ’ ，Ｂ）　から、　Ａ＝Ａ’　となり矛盾である。


　あと残された問題は、数Ｃの最小性の証明である。すなわち、

　数Ｃより小さい０以上の整数は、

Ｃを含む行のＣの左側にある数またはＣを含む列のＣの上側にある数の何れかに等しい

ことを示せば十分である。

（最小性の証明）　２つの数 Ａ　、Ｂ

　Ａ＝ａ_p’・２^p’＋ａ_p’-1・２^p’-1＋・・・＋ａ₁・２＋ａ₀　　（　ａ_ｋ＝０　または　１　）

　Ｂ＝ｂ_p’・２^p’＋ｂ_p’-1・２^p’-1＋・・・＋ｂ₁・２＋ｂ₀　　（　ｂ_ｋ＝０　または　１　）

に対して、　Ｆ（Ａ ，Ｂ）＝ｃ_p・２^p＋ｃ_p-1・２^p-1＋・・・＋ｃ₁・２＋ｃ₀　　（　ｃ_ｋ＝０　または　１　）

である。ただし、

　ａ_ｋ＋ｂ_ｋ＝０　または　２　　ならば、　ｃ_ｋ＝０

　ａ_ｋ＋ｂ_ｋ＝１　ならば、　ｃ_ｋ＝１

　この　Ｃ＝Ｆ（Ａ ，Ｂ）　の最小性は次のようにして示される。

　いま、　Ｘ＝ｘ_ｑ・２^ｑ＋ｘ_ｑ-1・２^ｑ-1＋・・・＋ｘ₁・２＋ｘ₀　　（　ｘ_ｋ＝０　または　１　）　を、Ｃより

小さい０以上の整数とする。このとき、明らかに、　ｑ≦ｐ　である。

　特に、ｑ＝ｐ　の場合は、ある自然数 ｒ に対して、

　ｘ_ｐ＝ｃ_p　、ｘ_ｐ-1＝ｃ_p-1　、・・・ 、ｘ_ｒ+1＝ｃ_ｒ+1　、ｘ_ｒ＝０　、ｃ_ｒ＝１　、・・・

が成り立つ。

　ここで、　一般性を失うことなく、

　ｃ_p＝１　で、　ａ_p＝１　、ｂ_p＝０　としてよい。

このとき、Ａ　、Ｂの ｐ より高次の係数は全て等しい。

また、　ｑ＝ｐ　の場合に、ｃ_ｒ＝１　であるが、以下では、ａ_ｒ＝１　、ｂ_ｒ＝０　として考える。

ａ_ｒ＝０　、ｂ_ｒ＝１　の場合も同様である。

　さて、　Ｘ＝ｘ_ｑ・２^ｑ＋ｘ_ｑ-1・２^ｑ-1＋・・・＋ｘ₁・２＋ｘ₀　　（　ｘ_ｋ＝０　または　１　）

　Ｂ＝ｂ_p’・２^p’＋ｂ_p’-1・２^p’-1＋・・・＋ｂ₁・２＋ｂ₀　　（　ｂ_ｋ＝０　または　１　）

に対して、

　Ｆ（Ｘ ，Ｂ）＝ｙ_p’・２^p’＋ｙ_p’-1・２^p’-1＋・・・＋ｙ_ｑ+1・２^ｑ+1＋ｙ_ｑ・２^ｑ＋・・・＋ｙ₁・２＋ｙ₀

（ただし、　ｙ_ｋ＝０　または　１　）

の ｙ_ｋ は、

　ｘ_ｋ＋ｂ_ｋ＝０　または　２　　ならば、　ｙ_ｋ＝０

　ｘ_ｋ＋ｂ_ｋ＝１　ならば、　ｙ_ｋ＝１

により定められる。このとき、　Ｆ（Ｘ ，Ｂ）＝Ａ’　とおき、　Ａ’＜Ａ　であることを示したい。

　明らかに、Ａ’　、Ｂの ｑ より高次の係数は全て等しく、ｑ≦ｐ　なので、

　Ａ’　、Ａ の ｐ より高次の係数は全て等しい。

次に、ｑ＜ｐ　のときを考える。このときは、Ａ’、Ｂの ｐ 次の係数は一致するので、

　ｙ_ｐ＝ｂ_p＝０

となる。これに対して、ａ_p＝１　なので、　Ａ’＜Ａ　となることが分かる。

　次に、ｑ＝ｐ　のときを考える。このときは、ある自然数 ｒ に対して、

　ｘ_ｐ＝ｃ_p　、ｘ_ｐ-1＝ｃ_p-1　、・・・ 、ｘ_ｒ+1＝ｃ_ｒ+1

が成り立つ。すなわち、Ｘ　、Ｆ（Ａ ，Ｂ） の ｒ より高次の係数は一致する。

このとき、

　Ｘ＝ｘ_ｐ・２^ｐ＋ｘ_ｐ-1・２^ｐ-1＋・・・＋ｘ₁・２＋ｘ₀　　（　ｘ_ｋ＝０　または　１　）

　＝ｃ_ｐ・２^ｐ＋ｃ_ｐ-1・２^ｐ-1＋・・・＋ｃ_ｒ+1・２^ｒ+1＋０・２^ｒ＋・・・＋ｘ₁・２＋ｘ₀

　Ｂ＝ｂ_p’・２^p’＋ｂ_p’-1・２^p’-1＋・・・＋ｂ₁・２＋ｂ₀　　（　ｂ_ｋ＝０　または　１　）

より、Ｆ（Ｘ ，Ｂ）＝Ａ’　は、

　Ａ’＝ｂ_ｐ’・２^ｐ’＋・・・＋ａ_ｐ・２^ｐ＋・・・＋ａ_ｒ+1・２^ｒ+1＋０・２^ｒ＋・・・＋ｙ₁・２＋ｙ₀

と書ける。したがって、このことから、

　Ａ’　、Ａ の ｐ より高次の係数は全て等しく、

かつ、

　Ａ’　、Ａ の ｒ より高次の係数も全て等しい

ことが分かる。さらに、　ａ_ｒ＝１　、ｙ_ｒ＝０　であることから、　Ａ’＜Ａ　となることが分かる。

　以上から、何れにしても、Ａ’＜Ａ　となるので、

　Ｘ＝Ｆ（Ｆ（Ｘ ，Ｂ） ，Ｂ）＝Ｆ（Ａ’ ，Ｂ）

となり、Ｘは、Ｆ（０ ，Ｂ）、Ｆ（１ ，Ｂ）、・・・、Ｆ（Ａ−１ ，Ｂ）の何れかと一致する。

　他の場合も同様である。

よって、Ｆ（Ａ ，Ｂ）　の最小性が確かめられた。　（証終）


　平成２２年７月２０日付けで、当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんより、この
「数の配列」の問題が「三山崩し」の必勝法に関連する旨ご教示いただいた。

　当ＨＰの「パズル＆クイズ」に「三山崩しゲーム」がある。平成１４年９月２日アップなので、
かれこれ８年前のものになる。再度そのページを読んでみると今回の「数の配列」の問題
に通じる同じ匂いを感じることができる。

　このような機会を与えていただいたＦＮさんに感謝します。


　一番上の行を「0行目」、一番左の列を「0列目」とする。

　非負整数 ｍ、ｎ に対して、非負整数 Ｆ（ｍ，ｎ）を帰納的に次のように定める。

（０）　Ｆ（０，０）＝０

（１）　Ｆ（ｍ，ｎ）は、

　Ｆ（ｍ，０）、Ｆ（ｍ，１）、・・・、Ｆ（ｍ，ｎ−１）、Ｆ（０，ｎ）、Ｆ（１，ｎ）、・・・、Ｆ（ｍ−１，ｎ）

　以外の最小の非負整数

このとき、「数の問題」における ｍ＋１行 ｎ＋１列の数は、Ｆ（ｍ，ｎ）そのものになる。

　いま、三山崩しゲームを考える。

　３つの山 Ａ 、Ｂ 、Ｃ に、それぞれ ａ 、ｂ 、ｃ 個の石がある。２人のＰｌａｙｅｒが交互にどれか
１つの山から１個以上任意の個数の石を取る。最後に石を取った者を勝ちとする。

　自分が石を取り終わった後、相手がどのように石を取ろうと自分が正しく応接すれば勝ちに
なる形を必勝形と呼ぶ。

　非負整数 ｍ、ｎ が与えられたとき、 ｋ 、ｍ 、ｎ が必勝形になる ｋ は１通りに定まる。

これを、ｋ＝Ｇ（ｍ，ｎ）とおく。

非負整数 ｍ 、ｎ に対して、その２進和 Ｈ（ｍ，ｎ）を次のように定義する。

　ｍ 、ｎ を２進法で表示して、各桁ごとに足し算をする。ただし、２は０とする。

こうしてえられた数を、Ｈ（ｍ，ｎ）とする。

　一松　信　著：「石取りゲームの数理」（森北出版）によると、

　Ｆ（ｍ，ｎ）＝Ｇ（ｍ，ｎ）＝Ｈ（ｍ，ｎ）

であることが示されているとのことである。


（コメント）　このページでは上記の証明により、　Ｈ（ｍ，ｎ）＝Ｆ（ｍ，ｎ）　であることが示され
　　　　　たことになるわけですね！



　　　以下、工事中！