7월의 퍼즐에 참여해주신 모든 분들께 감사드립니다!
7월의 퍼즐에 참여해주신 분 중 정답과 함께 좋은 풀이를 보내주신 이호준님께
HORIZON에서 준비한 선물을 전달드릴 예정입니다.
이 문제는 브래스웰Leigh Marie Braswell과 코바노바Tanya Khovanova의 논문 “On the Cookie Monster Problem”의 결과를 이용하였다.
문제에서 제시된 1, 2, 4, 7, 13, 24, 44는 연속한 세 항의 합이 다음 수가 되는 트리보나치 수열Tribonacci sequence로 다음과 같이 다섯 번만에 모든 쿠키를 먹어치울 수 있다. 물론 이 과정은 유일하지 않다.
일반적으로 1, 2, 4로 시작하여 트리보나치 수열의 항 \(k\)개가 주어진 경우, 쿠키를 모두 먹을 수 있는 최소 횟수는 \(\lfloor \frac{2k}{3} \rfloor + 1\)이다. 이 문제에서는 트리보나치 수열의 일곱 개 항이 주어졌으므로 쿠키를 모두 먹을 수 있는 최소 횟수는 \(\lfloor \frac{2 \times 7}{3} \rfloor + 1 = 5\)가 된다.
트리보나치 수열을 비롯한 다양한 패턴에 대한 쿠키 몬스터 수는 앞서 소개한 브래스웰과 코바노바의 논문이나 브래스웰의 강연 자료를 참고하라.
다음은 7월의 정답자로 선정된 이호준님의 해설입니다.
