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

読者です 読者をやめる 読者になる 読者になる

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

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

【数論】【整数】【C言語】総当たり法で、英国数学オリンピックの整数問題を解いてみた

数学 整数 高校数学 C言語

外国の幾何学の問題を探す為に「geometry problem」「geometry question」と検索を入れていた。すると英国数学オリンピック一次予選のページに遭遇し、面白い問題があったので紹介したい。

問題(英語):bmo 2010 Round1より

One number is removed from the set of integers from 1 to n. The average of the remaining numbers is 40\frac{3}{4} . Which integer was removed?

問題(筆者の解釈)

1からnの自然数の集合がある。この集合から自然数を1つ取り除きその平均を取ると40\frac{3}{4}となる。このとき取り除いた自然数を答えよ。

分からなかったので、C言語で解いてみた

とりあえず整数問題を総当たりで解くためのプログラムを作成した。総当たりの組み合わせは、n+(n-1)+(n-2)+...+1 = n(n+1)/2通りとなる。従って計算量のオーダーがO(n^2)型のプログラムである事がわかり、nが大きい程、計算(処理)が終わらなくなる可能性も高くなるので注意。この為1 \leq n \leq 100というように少ないnからプログラムを走らせるようにすると良い。以下プログラムの説明を始める。

プログラムの説明

1.まず総和S(n)を計算する
2.S(n)から1からnの自然数rを引いて行き、(n-1)で除算して平均値avgを算出
3.avg=40.75となった自然数rを出力
4.1〜3の作業を1〜nまで繰り返す

プログラム(C言語)

オブジェクト指向と言うのもおおそれたものを使わず行けると思ったので、C言語を採用した。

プログラムを実行してみた


f:id:program_study:20141111223217j:plain

上記に依れば求める整数は61で、そのときのnの値はn=81の時である事が分かる。

プログラムを見て解答を作成

解答作成にあたり二次方程式の判別式までたどり着いたが、その先の手作業をどうするかで一旦中断。プログラムの検算の結果、そこまで計算回数が増えないだろうと思い再び解答作成。その結果論理に不備があるか不安であるが、以下の解答を得る。

問題を解く上でax^2+bxy+cy^2+dx+ey+f=0型(二次曲線型)の不定方程式を解く流れで、判別式が平方数となるかどうか?に注目していく。

尚後半の「m=...」の平方数を割り出す為の計算をするに当たり、ExcelのSQRT関数や電卓を多用して、自分の歳というものを感じさせた。

ここからが解答

自然数1からnまでの総和は、S(n) = \frac{n(n+1)}{2}であらわせる。ここで取り除かれる自然数r(但し1 \leq r \leq n)とおく。

このときS(n)-rは、(n-1)における合計\frac{163(n-1)}{4}と等しく、\frac{n(n+1)}{2}-r = \frac{163(n-1)}{4}

これを整理してnの二次方程式2n^2-161n+(163-4r) = 0を得る。ここでこの二次方程式が少なくとも一つ整数解をもつためには、この方程式が因数分解できることが必要。

このことから判別式をDとしてD=(161)^2 - 8(163-4r)より、m^2 = 32r+24617(但しm自然数]とおける。さて(156)^2 = 24336,(157)^2 = 24649より、mはm>156を満たすただ一つの自然数である。さらにrが整数であるためにはmは奇数である事が必要*1

m=157のとき、32r+24617=24649 ∴r=1。このときこのときn=\frac{161±157}{4}より、n=1,\frac{318}{4}。さてこの事からn=1となるが1を取り除いた平均値が0となるので不適。

m=159のとき、(159)^2=25281より、32r=632 r= 19.75よりrが自然数である事に反する。

m=161のとき、(161)^2=25921より、32r=1272 r= 39.75 よりrが自然数である事に反する。

m=163のとき、(163)^2=26569より、32r=1952∴ r= 61 このときmが1つに定まればrも1つに定まるのでr=61である。このときn=\frac{161±163}{4}より、n=\frac{-1}{2},\frac{324}{4}よりn = 81となる(答)

感想

人間とコンピューター両方で解くことができる辺り、Project Eulerにあるような問題に感じた。海外の数学の問題は設問にヒントが少なく、やり方の指針の立てにくい。途中からどの不等式を使って論理を組み立てて行くかが難しい問題も多く、なかなか上手く行かない。最後に英国数学オリンピックのサイトを紹介しよう。

British Mathematical Olympiad Subtrust

URL:http://www.bmoc.maths.org/home/bmo.shtml

f:id:program_study:20141111223126j:plain

*1:mが偶数だと式の右辺が奇数なり、rが自然数となりえない