교차하는 사다리 문제(Crossed Ladders Problem)의 정수해

교차하는 사다리 문제 (Crossed ladders problem)

Wikipedia의 영어판에 있는 Crossed ladders problem 입니다만 일본어 번역이 없기 때문에 일본에서는 그다지 익숙하지 않을지도 모릅니다. 폭이 w로 벽에 끼인 도로에 길이가 a와 b의 사다리를 걸었을 때 h를 요구하라는 문제입니다.

이 문제의 정수해

Wolfram MathWorld에도 비슷한 기사 가 있지만 여기에 매우 흥미로운 설명이 있습니다. 변수를 쓰는 방법이 다르지만, 요점은 모든 변이 정수로되어 있다는 것입니다. 이번에는 다른 예제를 찾고 싶습니다.

이러한 해중에는 l_1, l_2, h_1, h_2, h 뿐만 아니라, d_1이나 d_2도 정수가 되는 것이 있습니다. 한 가지 예는 (l_1,l_2,h_1,h_2,h,d_1,d_2)=(119,70,105,42,30,40,16)입니다.

【문제】 0<a<b<300일 때 a, b, A, B, w, h, wa, wb (w를 h의 수직선으로 나눈 것)이 모두 정수인 것을 열거하라.

스텝 1 피타고라스 수

직각 삼각형으로 변이 정수라고 하는 것으로,
1. 기본 피타고라스 수를 발생시켜 갑니다. 이것에 대해서는 참고 코드가 많이 있다고 생각하므로 설명 생략합니다.
2. 기본 피타고라스 수를 정수배하여 삼각형의 장변이 N 미만인 것을 모두 만듭니다.
3. 직각을 끼우는 2변을 한쪽을 Key로 해 DICT에 더해 리스트로 합니다. 이것에 의해 w를 하고 있을 때, A와 B의 후보를 알 수 있습니다. 예를 들어 w=16일 때는 [12,30,63]이 후보이므로 여기에서 2개 선택하는 조합은 [12,30], [30,63],[63,12]이므로 이것을 A,B 로서 정수 판정을 실시합니다.
코드는 다음과 같습니다.

from collections import defaultdict
import itertools, math
## Generate Pythagorean triple
def pyth():  
  for m in itertools.count(2):
    for n in range(1,m):
      if (m%2)==(n%2): continue
      if math.gcd(m,n) != 1: continue
      yield m*m - n*n, 2*m*n, m*m + n*n

N = 300
ptall = defaultdict(list)
g = pyth()
for _ in range(N):
  t = next(g)
  for i in range(1,(N-1)//t[2]+1): # Multiples up to N
    t1 = (t[0]*i,t[1]*i,t[2]*i)
    for j in range(2):             # Add to dict (both small edges)
      ptall[t1[j]].append(t1[1-j])
print(len(ptall), ptall[16])
# 159 [12, 30, 63]

단계 2. h를 구하여 정수 판정을 실시한다

앞의 위키에서 h를 구하는 것은 다음 공식을 가지고 있습니다. h의 정수 판정을 행한 후, wa, wb를 구해 정수 판정을 실시하면 완료입니다.

$\Large\frac{1}{A}+\frac{1}{B}=\frac{1}{h}$
$\Large h =\frac{A*B}{A+B} $

count = 0
for w in ptall.keys():
  if len(ptall[w]) < 2: continue
  for A, B in itertools.combinations(ptall[w],2): 
    if (A*B) % (A+B) == 0:     # check h is integer
      h =  (A*B) // (A+B) 
      if w*h % A == 0 and w*h % B ==0: #check wa, wb are integers
        wa, wb = w*h//A, w*h//B
        a = int(math.sqrt(w**2+A**2))
        b = int(math.sqrt(w**2+B**2))
        count += 1
        print(count, ":", a, b, A, B, h, w, wa, wb)
#1 : 70 119 42 105 30 56 40 16
#2 : 104 296 40 280 35 96 84 12
#3 : 140 238 84 210 60 112 80 32
#4 : 175 119 140 56 40 105 30 75
#5 : 210 182 126 70 45 168 60 108

이 코드를 달리면 답의 모두 정수가 되는 조합은 5개 있는 것을 알 수 있습니다. (1과 3과 같이 유사형의 것을 포함합니다)

덧붙여서 Project Euler의 Problem 309: Integer Ladders는 wa, wb가 정수는 갖지 않기 때문에 그 판정을 제외한 것이 됩니다.