어느 날, solved.ac 디스코드에 흥미로운 주제가 날아왔다. 수학을 나름 사랑하는 사람으로서 절대 물지 않고 넘어갈 수 없던 떡밥이라 얌전히 물어 보기로 했다. 피보나치 수의 합과 자연수의 합 중 어느 쪽이 더 크냐는 질문이었고, 이 질문을 던진 분은 세 가지 케이스에 대해서 다음과 같은 근거를 달았다(정확하게는, 약간의 윤색을 거쳤다.).모든 피보나치 수의 합과 모든 자연수의 합이 같다 : 딱히 주장할 만한 근거가 떠오르지 않는다.모든 피보나치 수의 합 쪽이 더 크다 : \(n>4\)이면 \(n\le F_n\)임을 보일 수 있고, 이를 이용하여 \(n>6\)이면 \(\sum_{i=0}^ni모든 피보나치 수의 합 쪽이 더 작다 : 피보나치 수를 원소로 가지는 집합이 자연수를 원소로 가지는 집합의 부..

아직 上편을 본 적이 없다면, 일단 보고 오자. Part II. 페르마의 두 제곱수 정리 이번에는 사원수 대신에 복소수를 가져와 보자. 사원수 때와 유사하게, 복소수 \(z=x+iy\)의 norm은 \(\text{N}(z)=z\overline z=x^2+y^2\)로 정의된다. 또한 \(\text{N}(zw)=\text{N}(z)\text{N}(w)\) 역시 사원수 때와 마찬가지로 성립하므로, 어떤 자연수를 두 제곱수로 나타낼 수 있음의 필요조건은 그 자연수의 모든 소인수가 두 제곱수의 합으로 표현될 수 있음이다. 모든 소수가 두 제곱수의 합으로 표현될 수는 없다. 당장 \(3\)만 해도 두 제곱수의 합으로 표현될 수 없는 소수이다. 임의의 제곱수는 \(4\)로 나눈 나머지가 \(0, 1\)이므로, 두 제..

디오판토스. 그러니까 3세기부터 수학자들의 관심을 끈 문제가 하나 있다. 어떤 자연수 하나를 최대 몇 개의 제곱수의 합으로 나타낼 수 있을까? 일단 3개 이상일 것 같다. \(3=1^2+1^2+1^2\)로 나타낼 수 있으니까. 조금만 더 나아가면 4개 이상일 것 같다. \(7=2^2+1^2+1^2+1^2\)이니까. 그러면 다섯 개일 수는 있을까? 여섯 개일 수는? 일단 답이 그렇게 크지는 않을 것 같다. 직감만으로 생각을 해 본다면. 한 자리 수 안에서 정리되지 않을까. 이 문제가 본격적으로 주류 수학계의 화두에 오른 것은 디오판토스의 산술을 클로드 가스파르 바셰가 라틴어로 번역한 1621년이었다. 그리고 이 문제는 조제프-루이 라그랑주가 답이 4라는 증명을 내놓은 1770년까지 약 150년 동안이나 미..

근래 다시 출시하여 뭇 어린이와 어른이를 미치게 했던 포켓몬 빵을 기억하는가? 스티커만 가지고 빵을 버리는 사람, 편의점에서 산 빵을 개당 3000원에 되팔이하는 사람은 양반이었다. 빵 공장에서 일하는 사람이 수백 장의 스티커를 되팔 작정으로 횡령했다 뉴스에도 나왔지. 포켓몬 빵이 처음 나왔을 때도 지금도, 관건은 모든 스티커를 모을 때 필요한 빵의 갯수였다. n종류의 스티커를 모을 때 필요한 빵의 갯수는 몇 개인가? 어라... 어디서 많이 본 문제 아니던기? 그렇다, 26217번 문제에서 한 번 다루었던 쿠폰 수집가 문제이다. 해당 포스트에서 한 증명은 사실 엄밀하지 않다. \(\mathbb{E}(i+1)\)을 구하는 방법을 약간 어물쩡하게 넘긴 감이 있다. 여기서 완벽하게 한 번 짚고, 그 다음 원래..

피보나치 수에 관한 여러 가지 성질은 7677번 문제에서 예를 들었듯이 행렬과, 그리고 크게 상관은 없어 보이지만 황금비와도 큰 연관이 있다. 이번 포스트에서는 그 쪽과 관련하여 다루어 볼 예정이다. 먼저 피보나치 수의 일반항부터 시작하도록 하자. 일반항을 구하기 위해서 점화식을 이런 등비수열 닮은 꼴의 식으로 나타내 보자. \(F_{n+2}-aF_{n+1}=b(F_{n+1}-aF_n)\)의 형태로 말이다. 그러면 \(F_{n+2}=F_{n+1}+F_n\)과 비교해 보면 \(a+b=1, ab=-1\)이 된다. \(a>b\)라고 둔다면, \(a=\frac{1+\sqrt5}{2}\)가 되고, 이것은 황금비이다! 자, 그럼 지금부터는 \(a=\phi, b=\psi\)로 나타내 보자. \(\phi\)는 황금비를..

피보나치 수는 막 배우기 시작하는 초보 프로그래머와 뗄래야 뗄 수 없는 관계이다. 범위가 아주 작을 때는 재귀함수, 어느 정도 커질 때는 다이나믹 프로그래밍, 그리고 감당할 수 없을 정도로 커지면 분할 정복을 이용한 거듭제곱까지. 피보나치 수열에 관한 문제는 7677번 문제뿐만이 아니다. 대충 세어도 백준에만 50개가 넘는 피보나치 수열 관련 문제가 있다. 그렇게나 자주 나오는 피보나치 수열인 만큼, 단순히 N번째 피보나치 수를 계산하는 것에서 그치지 않고 피보나치 수열의 합이라거나, 제곱 합이라거나, 최대공약수라거나 이것저것 (뇌절로 읽힐 수도 있는) 바리에이션을 보여 준다. 그 중 간단하게 증명 가능한 것들을 하나씩 증명해 보자. 간단한 녀석들은 두어 줄로 끝이 나니 편하게, 편하게 보자. 우선 20..