题目

Problem 587. Concave triangle

A square is drawn around a circle as shown in the diagram below on the left.
We shall call the blue shaded region the L-section.
A line is drawn from the bottom left of the square to the top right as shown in the diagram on the right.
We shall call the orange shaded region a concave triangle.

It should be clear that the concave triangle occupies exactly half of the L-section.

Two circles are placed next to each other horizontally, a rectangle is drawn around both circles, and a line is drawn from the bottom left to the top right as shown in the diagram below.

This time the concave triangle occupies approximately 36.46% of the L-section.

If n circles are placed next to each other horizontally, a rectangle is drawn around the n circles, and a line is drawn from the bottom left to the top right, then it can be shown that the least value of n for which the concave triangle occupies less than 10% of the L-section is n = 15.

What is the least value of n for which the concave triangle occupies less than 0.1% of the L-section?

题解

第587题:凹三角形

一个圆外接一个正方形,如下图左边所示。
我们称图中的蓝色区域为 L 形区域。
从正方形的左下角到右上角画一条直线,如下图右边所示。
我们称橙色区域为凹三角形。

易知,凹三角形的面积正好是 L 形区域的一半。

水平放置两个圆,外接一个矩形。从矩形的左下角到右上角画一条直线。如下图所示。

此时,凹三角形的面积大约是 L 形区域的 36.46%。

如果水平放置 n 个圆,外接一个矩形,从矩形的左下角到右上角画一条直线。可以证明,当凹三角形的面积小于 L 形区域的 10% 时,n 的最小值是 15。

当凹三角形的面积小于 L 形区域的 0.1% 时,n 的最小值是多少?

分析

如上图所示,水平方向排列 n 个单位圆,我们有:

  • 第 1 个圆的方程:
  • 圆弧 DC 的方程:
  • 直线 AD 的方程:
  • 点 D 的坐标:
  • 令 x 为点 D 的横坐标,三角形 ABD 的面积:
  • 凹三角形 BCD 的面积:由与圆弧 DC 相关的定积分计算。
  • L 形区域的面积:(S正方形 - S) / 4 = (4-π)/4 = 1 - π/4

根据无理函数积分表,经过简单的计算,得到:

解答

根据以上分析,我们有以下 Haskell 程序:

main = print $ until (\n -> let x = n / (n + sqrt(2*n) + 1)
  in (f 1 - f x + x*x/n/2) / (1 - pi/4) < 0.001) succ 1
  where f x = x - ((x-1) * sqrt(x*(2-x)) + asin(x-1)) / 2

简要说明:

  • 第 1 行的x就是点 D 的横坐标。
  • 第 3 行的函数 f 就是圆弧 DC 的不定积分。
  • 第 2 行的f 1 - f x就是使用定积分计算凹三角形 BCD 的面积。
  • 第 2 行的x*x/n/2就是三角形 ABD 的面积。
  • 第 2 行的1 - pi/4就是 L 形区域的面积。
  • 第 1 行的until函数从 1 开始依次递增n值,直到计算出所求比例小于 0.1%。

这个程序的运行时间是 0.02 秒。

初等数学

不使用微积分,仅使用初等数学也可以解这道题。

如上图所示,凹三角形 ACD 面积等于三角形 ACD 面积减去弓形面积。我们有:

  • 点 D 的坐标:
  • 圆心角:
  • 弓形面积:
  • 三角形 ACD 面积:

我们有以下 Haskell 程序(程序中 h = |BD|):

main = print $ until (\n -> let
  h = 1 / (n + sqrt(2*n) + 1); θ = 2 * asin(sqrt(h/2))
  in (h - θ + sin θ) / 2 / (1 - pi/4) < 0.001) succ 1

这个程序的运行时间也是 0.002 秒。

数值积分

不计算不定积分,而是改用数值积分,也可以解答此题。PARI/GP 中计算数值积分的函数:

intnum(X=a,b,expr,{tab}): numerical integration of expr from a to b with respect to X. Plus/minus infinity is coded as +oo/-oo. Finally tab is either omitted (let the program choose the integration step), a non-negative integer m (divide integration step by 2^m), or data precomputed with intnuminit.

因此,我们有以下 PARI/GP 程序:

f(n)=b=n/(n+sqrt(2*n)+1);(intnum(x=b,1,1-sqrt(2*x-x*x))+b*b/n/2)/(1-Pi/4)
n=1;while(f(n)>=0.001,n++);print(n);quit()

这个程序的运行时间是 2.7 秒。虽然运行时间是三个程序中最长的,但是最省事,既不用计算不定积分,也不用计算弓形面积。

参考资料

  1. Wikipedia: List of integrals of irrational functions
  2. Wikipedia: Circular segment