퀴즈 469 18의 배수
모든 자연수 n 에 대하여 2^{2n} + 24n -10 이 18로 나누어 떨어짐을 보여라
풀이
이 문제를 푸는 것에는 여러가지 방법이 있을 수 있겠다.
가장 쉬운(?) 방법인 수학적 귀납법을 통해 보여보자.
먼저 n=1 일 때 2^2 + 24 -10 = 18 이니까 이는 18로 나누어 떨어진다.
n=k 일 때 18 로 나누어 떨어진다고 하고 n=k+1 일때 18로 나누어 떨어질지 확인해보자.
다른 방법으로는 18=2x9 이니까 이 수가 2의 배수이고 또 9의 배수임을 보여도 된다. 2의 배수인 것은 2의 곱으로 되어 있으니 자명하다. 사실 9의 배수도 이항정리와 정수론의 법을 알면 쉽게 보일 수 있다. 2=3-1 인 것을 이용하고 이항정리를 전개하여 9 로 나누어 떨어지는 것을 다 지우고 3이 곱해진 first order 와 3의 zeroth order 만 고려하면 된다.
즉 두 식을 합하면 9로 나눈 나머지가 0이라는 것을 알 수 있다. 준 식이 2와 9의 배수이니 최소공배수인 18의 배수가 된다.
퀴즈 470 동전 쌓기
특정한 두 개의 동전이 인접하지 않도록, n 개의 서로 다른 동전을 쌓는 방법은 모두 몇가지인가?
일반화해서 접근하기 힘들다면 n=5개인 경우를 생각해보자.
풀이
사실 이 문제는 함정이 하나 숨어져 있다. 일단 여사건을 생각하는 것 하나와 동전에는 양면이 있다는 점이다.
먼저 여사건, 즉 특정한 두개의 동전이 인접하도록 n 개의 서로 다른 동전을 쌓는 방법을 생각해보자.
즉 동전 2개를 하나로 보고 n-1 개를 쌓는 방법을 생각하면 된다. 즉 (n-1)! 개가 된다.
근데 동전 2개를 하나로 봤을 때 이 동전을 배열하는 방법이 두가지이다. [A-B 혹은 B-A 순서, 서로 다른 동전이라고 했으니 A-B 순서와 B-A 순서는 당연히 다르다.]
즉 전체 동전을 나열하는 방법은 2x(n-1)! 이 될 것이고 전체 n! 에서 빼면 (n-2)(n-1)! 이 된다.
자 여기서 한가지 빼먹은 사실이 하나 있다. 동전에는 양면이 존재한다는 것이다. 즉 각각의 동전을 쌓아올리는 방법에서 2가지(앞면, 뒷면) 가 되고 이는 n 개의 동전 모두에게 적용되는 것이기 때문에 전체 경우의 수는 2^n x(n-2)x(n-1)! 이 된다.