HMMT 2023년 02월 Combinatorics 7번 문제

문제

칠판에 147이 적혀 있다. 만약 칠판에 $n$이라는 수가 적혀 있다면, 다음 행동 중 하나를 할 수 있다.

1. $n$이 짝수라면, $n/2$를 적는다.
2. $n$이 홀수라면, $(n+255)/2$를 적는다.
3. $n$이 64 이상이라면, $n-64$를 적는다.

여러 번의 행동을 했을 때, 칠판에 최대 몇 개의 수를 적을 수 있을까?

해설

행동 중, 1, 2번의 행동이 사실 “같은 것”임에 주목할 필요가 있다. 바로 8자리 2진수의 Bit rotation이다.

홀수인 147을 2진수로 나타내면, 10010011가 된다. 그리고 147은 홀수이므로 $(147 + 255)/2 = 201$인데, 201을 2진수로 나타내면, 11001001가 된다. 가장 오른쪽의 비트 1을 빼서 가장 왼쪽에 두고, 나머지 비트가 하나씩 오른쪽으로 이동하는 것이다. 이것이 bit rotation이다. 짝수인 경우는 자명하다.

이 경우, 몇가지 특징이 있다. 하나는 값의 상한이 8자리라는 것이다. 그렇기 때문에 적을 수 있는 수는 0에서 255 까지 중 일부라고 볼 수 있다. 다만 여기서 255는 나올 수 없다. 그 이유는, 위의 행동에서 값을 증가시키는 것이 두번째 밖에 없는데, 두 번째 값의 결과 값이 255의 이상이 되려면 처음의 $n$도 255 이상이 되어야 하기 때문이다.