PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 587 / 凹三角形

左下図のように円に外接する正方形に対し,青い部分を「Lセクション」と呼ぶことにする。
また,右下図のように対角線を引いて,オレンジの部分を凹三角形と呼ぶことにする。この図では凹三角形の面積はLセクションの面積の半分である。

f:id:variee:20170419165012p:plain


同じ大きさの円2つを横にならべ,それらに外接する長方形を描く。このとき,凹三角形の面積はLセクションの面積の約36.46%である。

f:id:variee:20170419165027p:plain


n 個の円をならべたとき,凹三角形の面積がLセクションの面積の10%未満になる n の最小値は15である。この比が0.1%未満になる n の最小値を求めよ。*1

Problem 587 - Project Euler


数値積分で解きました。

長方形の左下の頂点を原点として座標系をとり,円の半径を1とします。直線の方程式は y=x/nで,円の方程式は (x-1)^2+(y-1)^2=1。凹三角形は次の不等式であらわされます。

 0 \leqq y \leqq \min\left\{\dfrac{x}{n},\, 1-\sqrt{1-(x-1)^2}\right\}\quad (0\leqq x\leqq 1)

これの積分がLセクションの面積 1-Pi/4 の0.1%未満になる n を求めます。n=1 から調べても1分以内に答えが出ますが,何度も何度も数値積分するのは無駄なので,適当に大きな n から調べはじめるといいと思います。


また,受験数学っぽい話ですが,円と直線の交点の座標を求められることを利用して,Lセクションから凹三角形を除いた部分を考える方が早いです。

*1:私が適当に意訳しました。