제켄도르프 정리 과제 (Zeckendorf’s Theorem)

제켄도르프 정리 (Zeckendorf’s Theorem)

안녕하세요. 멘토 교사 이민재입니다. 여러분들은 주어진 읽기자료를 통해 제켄도르프 분해가 어떤 것인지 이해했을 것입니다. 다시 말하면, ‘모든 자연수는 연속하지 않는 피보나치의 합으로 표현할 수 있고, 그 합의 표현은 유일하다.’는 정리입니다. 이해를 돕기 위해 자연수 몇 개를 선정하여 제켄도르프 분해를 해보겠습니다.

1=1

2=2

3=3

4=3+1

5=5

6=5+1

7=5+2

 위의 예시와 같이 작은 자연수에 한하여 살펴보면 제켄도르프 분해가 가능하고, 그 합의 표현이 유일하다는 것을 알 수 있을 것입니다. 제켄도르프 정리에 의하면 제켄도르프 분해는 모든 자연수에 대해 가능합니다. 예를 들면 9999도 제켄도르프 분해가 가능하고, 9999999도 제켄도르프 분해가 가능하다는 이야기입니다. 그러나 숫자가 매우 커지면 인간의 능력으로는 제켄도르프 분해를 하는 것이 불가능합니다. 그래도 여전히 제켄도르프 분해는 가능합니다. 참 신기하죠? 이 제켄도르프 정리를 증명하는 것이 바로 2차과제입니다. 이 정리를 혼자만의 힘으로 증명하는 것은 매우 어렵겠지만, 도전해볼 만한 가치가 있는 문제입니다. 증명은 수학의 가장 기본이 되는 것입니다. 여러분이 완벽하게 증명해낸다면, 아마 이 정리를 증명한 최초의 중학생이 될지도 모릅니다. 증명을 완벽하게 하는 것을 바라는 것이 아닙니다. 다음에 제시된 두 문제 중에서 한 문제라도 끄적거리시면 됩니다. 혹시 두 문제 모두 풀기 어렵다면 “어떻게 증명할 수 있겠다.” 라는 아이디어라도 제시해주세요.

 

1.   모든 자연수에 대해서 제켄도르프 분해가 존재한다는 것을 증명하시오.

힌트 : 수학적 귀납법을 이용하여 증명할 것

2.   위에서 증명했듯이, 제켄도르프 분해가 존재한다고 했을 때 그것이 유일하다는 것을 증명하시오.

힌트 : 귀류법을 이용하여 증명할 것

 

l  제출방법 : 한글파일로 작성하여 업로드 하거나, 자필로 작성하여 스캔한 파일을 올려도 됩                    니다.

l  제출기한 : 2015년 8월 5일 (수)