マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第６章 ６次魔方陣・８次魔方陣の作成

第14話 第13話の説が正しいことの証明


第１命題　黄色は対角線合計に影響を与えない。

第２命題　白は横合計と縦合計に影響を与えない

第３命題　明るい紫は横合計に影響を与えない

第４命題　緑は縦合計に影響を与えない

これを証明するために記号を導入します。一見難しそうですが、難しいことではありません。

a11　   a 12　   a 13　・・・・　   a1(n-2)　    a1(n-1)　    a1n

a21　   a 22　   a 23　・・・・　   a2(n-2)　    a2(n-1)　    a2n

a31　   a 32　   a 33　・・・・　   a3(n-2)　    a3(n-1)　    a3n

                     .

                     . 

                     .

a(n-2)1　a (n-2)2　a (n-2)3　・・・・　a(n-2)(n-2)　 a(n-2)(n-1)　  a(n-1)n

a(n-1)1　a (n-1)2　a (n-1)3　・・・・　a (n-1)(n-2)　 a (n-1)(n-1)　 a (n-1)2n

an1　　 a n2　　 a n3　・・・・　　an(n-2)　     an(n-1)　  　  ann

第１命題の証明
　　
　点対称移動前は
　　a11+a 22+a 33+・・・+a(n-2)(n-2)+a(n-1)(n-1)+ann
　　点対称移動後は
　　　ann+a (n-1)(n-1)+a (n-2)(n-2)+・・・+a33+a22+a11
　つまり順番が逆になっただけで両者は等しい。


第２命題の証明
　　
　白は何もしないので自明

第３命題の証明
　　
　明るい紫の交換は
　　a pqとa (n-p+1)qの交換であり
　両者の合計は当然同じである。
　ですから横合計に影響を与えません。

第４命題の証明　　
　緑の交換は
　　a pqとa (n-p+1)qの交換であり
　両者の合計は当然同じである。
　ですから縦合計には影響を与えません。

解説　
a (n-p+1)qとa (n-p+1)qがわかりにくいと思いますので解説しておきます。

ｐと左右対称の位置に来るのｎ - ｐではありません。
a 13とa1(n-2)とを考えればわかります。
a1(n-2)はa1(n-3+1）なのです。
ｐと左右対称の位置に来るのはｎ - ｐ + 1というわけです。
a (n-p+1)qの場合も同じです。

ｐと上下対称の位置に来るのはｎ - ｐ + 1というわけです。

プログラミングの世界や数学の世界ではこの現象を防ぐために

a00　   a 01　   a 02　・・・・　   a0(n-3)　    a0(n-2)　    a1(n-1)

a10　   a 11　   a 12　・・・・　   a1(n-3)　    a2(n-2)　    a2(n-1)

と表記します。ですが、熟れないとわかりにくいですね。

純粋に熟れの問題です。

for(int i=0;i<n;i++)がわかりにくいと感じた人は、

沢山いると思います。これは

0，1，2，・・・，n - 1

でn個の処理です。

0のカウントを忘れ皆さんn - 1個の処理と誤解しますが、

0をカウントすればn個なのです。

基本プログラミングの世界では0から始めた方がよいのです。

理由は配列にあります。

a[0]から始めますね。

字の大きさが勝手に変わってしまいますので、

ホームページビルダーはとてもできの悪いソフトです。

現在のバージョンは23ですが、改善されていません。

文字の大きさをそろえようとすると軽く２時間がつぶれてしまいますので、

お許しください。

さて、まだ証明は終わっていません。

横合計に影響を与える緑の個数が、

１行あたり左上1/4に注目すると

(n / 2 - 2) / 2 であることを証明していないからです。

上下対称移動によって横合計はどれだけ影響を受けるかを考えれば、

これは証明できます。

交換されるのはa pqとa (n-p+1)qです。

第４命題のように縦合計には影響を与えませんが、

当然横合計には影響を与えます。

最初は具体例で考えましょう。

（同じもの図にしました）

3と59の交換では差し引き56増となります。

緑は１行あたり２個ですから56×2で112増です。

そして対角線の点対称移動で（64-1）+（57-8）=112増です。

白と明るい紫は横合計に影響を与えませんから

横合計は

1 + 2 + 3 + 4 5 + 6 + 7 + 8 + 112 + 112 = 260

ドンピシャリです。

証明は結構複雑な構造になりますので、

特別話を設けてそこで証明したいと思います。

とりあえず第15話ではすべての行・すべての列・２本の対角線の合計を計算して、

一般的な証明の考え方のみを説明して、

証明は特別編で行います。

特別編は数学に自信を持っている方のみが挑戦してください。

人間は１つわからない項目があると全部わからなかったという印象を持つ傾向がありますので、

特別編は数学に自信ある方のみが読んでください。



第６章第13話へ　第６章第15話へ

本講義トップへ