공간 풀이법 : 의미가 똑같은 다른 표현방식을 찾아라.
오늘은 한국 수학 올림피아드 KMO 문제를 풀어보겠습니다.
문제는 간단하네요. 2023부터 4046까지의 수들에 대해서 각각의 가장 큰 홀수 약수를 구하고 그들의 합을 구하라는 문제입니다.
관건은 여기서 공통성을 발견할 수 있느냐 하는 것입니다.
1000개가 넘는 짝수를 하나하나 처리할 수는 없으니까요.
먼저 발견할 수 있는 사항이 있습니다. 예를 들어 n=2024를 생각합니다. 2024의 가장 큰 홀수 약수는 2024/2 = 1012의 가장 큰 홀수 약수와 같습니다.
그러니까 이를 일반화하면 어떤 수가 주어졌을 때 그 수의 최대인 홀수 약수는 그 수를 2로 여러 번 나누더라도 변치 않습니다. 반대로 2를 여러 번 곱한다고 해도 최대인 홀수 약수는 변하지 않습니다.
그래서 다음과 같이 문제의 조건을 변형할 수 있습니다.
어떤 수가 주어져 있을 때, 그 수에 적당히 2로 여러 번 나누거나 2를 여러 번 곱한 수로 바꾸어도 된다.
조건의 변형을 발견했으니 이제 문제를 변형시키겠습니다.
각각의 단계에서 홀수만 남겨놓고 짝수는 다시 2로 나누어가는 작업을 반복하면 됩니다. 이제 최종 결과를 추론할 수 있습니다.
1,3,5,…, 2023, 2023, … 4045
2023만 중복이 되고 1부터 4045의 홀수가 차례로 남습니다.
이제 목표공간으로 내려갈까요? 답은 고2 과정인 수열의 합을 이용하면 간단히 됩니다.
정답은 552입니다.
공간 학습법 : 조건의 변형을 찾아라
주어진 조건을 그대로 사용한다고만 생각하지 말고
새로운 변형을 찾아야 합니다.
그리고 그 변형을 사용하여 문제를 변형시켜 가면서 풀 수 있습니다.
이 문제에서는
각각의 짝수에 대해서 가장 큰 홀수 인수를 찾는다고 하면 나누어야 하는 2의 거듭제곱수가 제각각이어서 간단하고 일관된 규칙을 찾기가 힘듭니다.
주어진 짝수를 2로 나눌때 여러 번에 걸쳐 나누어도 가장 큰 홀수 인수는 변치 않는다는 사실을 이용하면
필요할 때마다 2로 나눔으로써 규칙성을 쉽게 찾을 수 있답니다.
주어진 조건을 적절하게 변형해서 사용해 보면 어떨까요?
오늘은 여기까지 입니다. 다음에 더 재미있는 문제로 만나요!