더북(TheBook)

그래프를 펼치는 방법을 익히고 싶다면 별 위의 동전 퍼즐(2.034)을 풀어보자.

방정식을 풀거나 어떤 함수의 최댓값 또는 최솟값을 구하는 수학 문제로 환원해 풀 수 있는 퍼즐도 있다. 다음과 같은 퍼즐을 예로 들 수 있다.

파이 자르기 최적화 직사각형 파이를 직선 모양으로 n번 잘라 만들 수 있는 최대 조각 수는? 이때 자르는 방향은 반드시 파이의 수직 또는 수평 방향과 평행해야 한다.

파이를 수평 방향으로 h번, 수직 방향으로 v번 자르면 조각 수는 (h + 1)(v + 1)개가 된다. 파이를 자른 횟수 h + vn과 같으므로 이 문제는 다음 식의 최댓값을 구하는 문제로 환원할 수 있다.

(h + 1)(v + 1) = hv + (h + v) + 1 = hv + n + 1 = h(n - h) + n + 1

이때 0 ≤ hn이다. h(n - h)는 h에 대한 2차식이므로 n이 짝수이면 h = n/2일 때, n이 홀수이면 h = n/2에서 내린 값(⌊n/2⌋로 표기), 또는 올린 값(⌈n/2⌉로 표기)일 때 최댓값이 나온다. 따라서 n이 짝수이면 해는 n/2 하나뿐이고 n이 홀수이면 해는 h = ⌊n/2⌋, v = ⌈n/2⌉, 또는 h = ⌈n/2⌉, v = ⌊n/2⌋로 두 개가 된다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.