Euler : Problem 68

Posted by TAKAIY On 2011年11月30日水曜日 0 コメント

魔方陣系の問題です。

条件を見つけるためにちょっと試していたら、その場で答が出ちゃったという初めての経験をしました。
ですけど、勉強のために、コードは書いてみました。





魔方陣のセオリー通り、穴は図のA(外周)とB(内周)の様に2種類に分けられます。

一列に並んだ数の合計を同じにするということは、
 A1 + B1 + B2
 A2 + B2 + B3
 A3 + B3 + B4
 A4 + B4 + B5
 A5 + B5 + B1
この5つが同じになるということです。これをXとすると全部の合計は、5X ということになります。
次に、上の式から全部の合計は、
  (A1 + B1 + B2) +  (A2 + B2 + B3) + (A3 + B3 + B4) + (A4 + B4 + B5) + (A5 + B5 + B1)
= (Aの合計) + (Bの合計)×2
ということが分ります。
ということで、
 5X = (Aの合計) + (Bの合計)×2
 X = ((Aの合計) + (Bの合計)×2) ÷ 5

ということになり、Aの組に入れる数を決めれば、1列の合計を求めることができます。

たとえば、Aに 1,2,3,4,5 を入れたとします。Bには、残りの6,7,8,9,10が入ることになります。
(Aの合計) + (Bの合計)×2 = 95
5X= 95
X= 19
1列の合計はすべて19になるということです。

さて、この問題は、Aのグループのなかで一番小さい数から時計回りに数字を並べたときに、最も大きくなるものを求めるのですから、外周に最も大きな数字を並べればよさそうです。
ということで、上の例とは逆に、Aに6,7,8,9,10、Bに1,2,3,4,5を入れます。
 5X = 40 + 15 × 2 = 70
 X = 14
1列が14になります。

ここからごにょごにょやって、手で答えを出しちゃったわけですが、それは最後の方で


さて、答えがでちゃったわけですがやっぱりプログラムで解きたいのでちょっと考えました。
- A1が6で、A2~A5 が 7 8 9 10 のどれか
- 1列の合計を求めて、全ての列がそれになっているかどうか
という計算をしました。
もうちょっと頭のいいやりかたがありそうですけどね。





- check-pe68
  各列の合計が14であるかどうか確認して、そうであれば、
  順番に並べたものを返し、そうでなければFalseを返す。
  a1は6で固定。

- pe68
  外周用に7-10の全順列(6の位置は決っているから)、内周用に1-5の全順列を作って、
  それぞれの全ての組み合わせをcheckに喰わせてfalse以外の
  ものを取得


-----------------------------------------------------
この先は答え入りの手計算解説。 注意
-----------------------------------------------------



1から10の数字を組みあわせて合計が14になるものはそれほど多くありません。
10 3 1
 9 4 1
 9 3 2
 8 5 1
 8 4 2
 7 6 1
 7 5 2
 7 4 3
 6 5 3
たとえば、10を採とるとすると、のこりは4。1から9で足して4になるのは1と3だけ、という具合です。また、5以降はすでに表われているはずなので考える必要はありません。

さて、結果をみると、10と6は1通りしかありませんので、列の作りはそれぞれ2通りしかありません。
 10 3 1、 10 1 3
  6 5 3、  6 3 5

ここで、問題に立ち帰ると、Aで最も小さい6が先頭にきて、数字を大きくしなければならないわけですから、6の列は 6 5 3 に決ります。
もう一方の10の列は、10 3 1 に決ります。これは、3が6の列の最後に来ているため、10 1 3の並びが作れないためです。
また、このことから、他の列では3が使えないことがわかります。すると、9は 9 4 1 の組であり、1の場所から、 9 1 4 であることがわかります。
1が使えなくなってしまったので、8が決り、4の場所から、8 4 2 になり、最後の7は、同様に、7 2 5 となります。
結果
 6 5 3
10 3 1
 9 1 4
 8 4 2
 7 2 5
また、偶然ですが、並びもこのままになっています。
並べかたとしては、内周の並びが2つめと3つめであることから、最後の数が次の数の2番目にくるように並べることになります。

0 コメント:

コメントを投稿