黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【高校入試】整数問題をC言語で解いてみた:日本女子大学附属高校より

はじめに

本記事は高校2年生以上または数学に興味のある中学生を対象にした記事である。不定方程式や文字式に慣れている人向けの説明なため、読みにくい部分があったら許して欲しい。

問題


1から8までの8個の整数から4個を選び,それらの積をaとし,残り4個の積をbとする.このとき,a=bとなることがあるか.あればその値を求め,いつもa≠bであれば理由を述べよ.(【高校入試061】日本女子大学附属高校:10年ぶりの数学少年の部屋)より

人力による解答(背理法)

a≠bであると予想し、これを背理法*1により示す。a=bと仮定すると、問題文よりab=8!となり、a^2 = 8!<=>a^2 = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1となる。

この時3,5,7は素数よりaは無理数となる。ところがaは4つの自然数の積であり、aが自然数である事に矛盾する。以上よりa≠b q,e,d

C言語による解答(毎度おなじみ総当たり法)

aに選ばれる4つの自然数の候補を総当たりであたって、a=bになるかどうかを調べて行く。ここでaに選ばれる4つの自然数の候補は、8個の整数から4個を選ぶ組み合わせとなるので\binom {8}{4} = 70(通り)である。この全ての候補を総当たりで計算していく。

さてaに選ばれる4つの自然数x,y,z,wとしたとき、a=xyzw(x < y < z < w)が成立する。日本の受験でおなじみ、不定方程式a=xyzwの解の候補を不等式を使って絞っていく。

[i]まず(x,y,z,w) = (5,6,7,8)以上はなりえないので、 x \leq 5 y \leq 6 z \leq 7 w \leq 8が成立。

[ii]次に(x < y < z < w)を整理して、 y \geq (x+1) z \geq (y+1) w \geq (z+1)である事が分かる。

従ってC言語x,y,z,wの4つの自然数に値を代入し、総当たりでa=bかを計算していく。 1 \leq x,y,z,w \leq 8の範囲で全て調べると、(2^3)^4 = 2^{12} = 4096(回)計算することになり、実行時間が上がってしまう。

そこで[i][ii]を考慮した上でfor文を組むなど、できる限りプログラムに計算をやらせない工夫が必要な場合もある。実務の場でプログラムを組んでいると、完成させる事に目が行きどうしてもここまで目がいかない。

ソースコード

実行結果:プログラムに70通りの計算をさせてみた

上記のプログラムを実行した結果を以下に記す。a≠bである事を示すには、x,y,z,wの候補70通り全てを計算し、全てa≠bとなる個数を確かめればよい。その個数が70であるかをプログラムにやらせていったと言う訳だ。下記の実行結果よりcountが70のため、全ての場合においてa≠bとなる事が分かった。

最後に

今回は元ネタのサイトのヒントを読んでから解答し、ネタづくりの目的でC言語に依る解答を書いてみた。おなじみの構成だが、プログラムやコンピューターを使った計算手法に興味を持ってくれる人が居たなら嬉しい。

*1:背理法:命題「AならばB」を示す際、「AならばBでない」が成立すると仮定して話を進めていき、その矛盾を示すことにより「AならばB」を示す方法。