책 이야기

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

변의 길이가 정수이고 정수 크기의 면적을 가지는 정삼각형이 없다는 것은 증명하기 쉽다. 그러나, 거의 정삼각형인 5-5-6의 면적은 12로 정수가 된다.

두 변이 같고 다른 변과 길이 차이가 1 이하인 삼각형을 "거의 정삼각형"으로 정의하고자 한다.

변의 길이와 면적이 정수이고 둘라가 10억을 이하인 모든 "거의 정삼각형"의 둘래의 합계를 구하시오.

--------------------------------------------------------------------------

"거의 정삼각형"을 다시 생각해보면 2개의 직각삼각형이 붙어 있는 구조이며, 직각삼각형의 빗변(가장 긴 변)이 "거의 정삼각형"에서 길이가 같은 변이 된다. 그리고 길이가 같은 변을 a, 나머지 변을 b라 하면, 문제에서 정의한 내용에 따라 b=a±1이 되고, "거의 정삼각형" 안에 있는 직각삼각형은 빗변이 a, 다른 변은 피타고라스 정리에 의해 각각 b/2=(a±1)/2, (a**2-(b/2)**2)**0.5가 된다.

문제에서 둘레와 면적이 모두 정수가 된다고 했으므로 b, b/2, (a**2-(b/2)**2)**0.5 모두 정수가 되어야 하며 a*2+b는 10억 이하가 되어야 한다. 그리고, b/2가 정수가 되기 위해서는 a는 홀수가 된다.

이런 전제조건에 따라 a가 커지면서 b, b/2, (a**2-(b/2)**2)**0.5가 정수이고, 둘레가 10억 이하인 "거의 정삼각형"을 계속 구했는데, 정상적으로 나와야 할 갯수보다 6개가 더 나와서 둘레의 합이 훨씬 크게 나오는 문제가 생겼다.

원인을 파악해 보니 (a**2-(b/2)**2)**0.5 값을 int(a**2-(b/2)**2)**0.5)와 비교해서 같으면 정수로 판별했는데, 제곱수와 차이가 매우 미세하면 제곱수가 아닌데도 두 값이 같게 나오는 문제 때문에 답을 6개나 더 구한 것으로 추정되었다.

is_integer() 등 몇 가지 방법을 적용했지만 해결되지 않아서, 제곱근을 씌운 상태에서 계산하지 않고 제곱인 상태에서 값을 비교해서 제곱수 여부를 판별하게 했더니 정답을 구할 수 있었다. 이전 문제에서 비슷한 경험이 있어 빨리 해결 가능했지, 로직의 문제가 아닌 프로그램 고유 특성에서 생기는 이런 현상은 찾기가 쉽지 않은 것 같다.

The points P (x1, y1) and Q (x2, y2) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,
0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

좌표 P (x1, y1)과 Q (x2, y2)은 정수 좌표에 있으며, 시작점인 O(0, 0)과 연결되어 삼각형 ΔOPQ를 만든다.

좌표가 0과 2 사이일 때, 정확히 14개의 직각삼각형을 구할 수 있다.

0 ≤ x1, y1, x2, y2 ≤ 2.

0과 50 사이(0 ≤ x1, y1, x2, y2 ≤ 50)일 때 몇 개의 직각삼각형이 있는가?

--------------------------------------------------------------------------

O, P, Q 간의 관계를 잘 설정하면 반복문을 통해 만들어지는 삼각형을 피타고라스 정리(a²+b²=c²)를 이용해 직각삼각형인지 판단하면 되는 문제로 파악되었다.

O를 기준으로 P는 오른쪽, Q는 위쪽에 있는 좌표로 계산하기로 설정하였고, 반복문을 통해 P, Q가 가능한 모든 좌표에 대해 OP, OQ, PQ 거리를 구해서 피타고라스 정리를 만족하는 삼각형의 갯수를 구하였다.

P, Q의 한계를 조금 더 세밀하게 설정하면 속도가 더 빨라질 것 같았지만, 크게 늦지 않게 답을 구할 수 있어 만족하기로 했다.

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

    12 cm: (3,4,5)
    24 cm: (6,8,10)
    30 cm: (5,12,13)
    36 cm: (9,12,15)
    40 cm: (8,15,17)
    48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

    120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

12cm는 선을 구부려서 만들 수 있는 세 변이 모두 정수인 직각삼각형 둘레의 최소값이다. 그리고, 더 많은 예가 있다:

    12 cm: (3,4,5)
    24 cm: (6,8,10)
    30 cm: (5,12,13)
    36 cm: (9,12,15)
    40 cm: (8,15,17)
    48 cm: (12,16,20)

이와 대비되게, 20cm 길이로는 변이 정수인 직각삼각형을 만들 수 없으며, 어떤 길이로는 1개 이상의 직각삼각형을 만들 수 있다. 예를 들어, 120cm로는 세가지의 변이 정수인 직각삼각형을 만들 수 있다.

    120 cm: (30,40,50), (20,48,52), (24,45,51)

L이 선의 길이이고 L이 150만 이하일 때, 1개의 직각삼각형만 만들 수 있는 L은 몇 개 있는가?

--------------------------------------------------------------------------

75번 문제인 것을 보면 좀 더 슬기롭게 해결하기를 요구하는 것 같은데, 문제와 관련되어 아는 공식은 피타고라스 정리 밖에 없으므로, 세 변의 길이가 L이고(a+b+c=L), 짧은 두 변 제곱의 합이 긴 변 제곱과 같다는(a²+b²=c²) 두가지를 이용해 문제를 해결하기로 했다.

실행시간이 너무 많이 걸려, L, a 기준으로 문제에서 제시한 공식을 다시 정리해서 c=(a²+(L-a)²)/2(L-a), b=L-a-c를 구하는 형태로 바꿔보았다.  이 경우에 L은 짝수인 경우에만 계산하도록 해서 시간도 조금 단축시킬 수 있었다. a값이 가장 큰 경우가 a와 b의 값이 같은 때이고, 이 경우 세 변의 합 L=(2+√2)a이며, a=L/(2+√2)a가 된다.

이렇게 범위를 가능한 줄여봤지만 L이 커지면서, a범위도 따라 커져서 실행시간은 여전히 만족스럽지 못했다. L이 10,000 커질때마다 실행시간이 15~20초씩 이전보다 늘어나고 있어 대략 50시간 정도 필요한 것으로 계산되었다.

어쩔수 없이 수학이론의 힘을 빌렸는데, m>n, m+n은 홀수, m과 n의 최대공약수는 1이라는 특성을 가지고 있으며, a=2mn, b=m²-n², c=m²+n²라는 공식이 있었다. 실제로 계산해보니 여기서 두 수의 값에 따라 제일 짧은 변이 a, b 중에 있을 수 있고, m=2, n=1일때 a=4, b=3, c=5(둘레 12)라는 직각삼각형을 구했으면, 전체 길이가 150만 이하일때까지 계속 곱해서 같은 비례를 가지는 직각삼각형을 모두 구해야 한다.

이렇게 구한 직각삼각형을 대상으로 둘레가 같으면서 a, b, c가 다른 경우를 제외하는 과정을 거치면 되는데, 참고로 150만 이하의 직각삼각형 조합이 백만개가 넘기 때문에 같은 값이 없을 때 리스트에 추가하는 것 보다는 집합을 이용하는 것이 속도가 월등히 빠르게 나왔다.

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

각 면이 정수 길이 {a, b, c}를 가지는 직각 삼각형의 둘레를 p라고 하면, p가 120일 때 정확하게 3가지 경우({20,48,52}, {24, 45, 51}, {30,40,50})만 있다.

p ≤ 1000일 때 p가 얼마인 경우에 가장 많은 경우의 직각 삼각형이 가능한가?

--------------------------------------------------------------------------

직각 삼각형의 속성으로는 a²+b²=c²가 있고, 문제에서 p=a+b+c로 되어 있는 전제 조건을 이용하여 해결해야 한다.

가장 긴 변을 c라고 할 때, a와 b는 같을 수도, 다를 수도 있다. 이 중 b가 더 클 수 있다고 생각하면 a≤b 관계가 생긴다. 그리고, c는 피타고라스의 정리에 의해 어떤 형태로든 a, b 보다는 크게 된다. 설정한 관계대로 정리하면 a≤b<c가 된다. 세 숫자가 모두 자연수인 직각삼각형 중 가장 작은 것은 3, 4, 5이고, 이것의 둘레는 12이다. 그리고, 보수적으로 계산해도 a, b 두 숫자 중 하나의 크기는 전체 둘레길이의 절반이 될 수 없다.

b를 기준으로 4부터 499까지 반복하면서, b보다 같거나 작은 a를 1부터 b까지 반복해서 피타고라스 정리에 따라 c를 구하고, c가 자연수이고, a+b+c가 1000이하인 경우를 모으면 된다.