얼마전에 (크리스마스날!) 학원 수업 대타를 하루 했습니다. 이제 다시는 학원수업을 하지 않을줄 알았는데.. 오랜만에 올림피아드 문제좀 풀어볼까 하고 잠시 시간을 내어 수업을 했습니다. 그런데 그 전후로 너무 바빠서 생각보다 힘들었습니다..

그날 수업을 위해 준비한 문제중 다음과 같은 문제가 있습니다.

There are positive integer , need not to be different, in the blackboard. In each “step”, we can erase two numbers  and write greatest common divisor and least common multiple of in the blackboard. The “meaningful step” is a step which change the set of integers in the blackboard.

1. Prove that the possible number of meaningful steps is finite.
2. Regardless of the way we do steps, if we cannot do any meaningful steps, the possible set of integers in the blackboard is  unique.

원래 문제는 1번만 있었는데, 너무 쉬워서 내지 말까 고민했었습니다. 근데 왠지 더이상 할 수 없는 상태가 유일하지 않을까 싶어서 이리저리 고민해보니 적당한 난이도로 해결이 되고, 재미있는 toy problem인 것 같아서 출제했습니다. 풀이는 비밀로 ㅎㅎ.