[8월의 퍼즐] N등급 충명 소환술

매월 응모자 중 한 분을 선정하여 문화상품권을 드립니다.
8월 26일까지 댓글로 참여하실 수 있으며, 9월 초에 해설과 함께 선정된 정답자가 공개됩니다. (이름, 이메일과 전화번호를 포함한 연락처를 남겨주시면 채택시 연락을 드립니다.)

당신은 흑마술로 지옥에서 충명을 소환해 세계를 멸망시키고자 한다. 충명들은 모두 수학과 퍼즐을 좋아하기 때문에 엄격한 규칙을 지켜 흑마술을 시행해야만 소환에 응한다. N등급 충명을 소환하기 위한 흑마술에는 양초 N개가 필요하며, 시행하는 법은 다음과 같다.

커다란 원을 그리고, 붉은색 양초 하나를 포함하여 총 N개의 양초를 원주를 따라 등간격으로 배열한다. 이 붉은색 양초를 0번 양초라고 하고, 0번 양초부터 시계 방향으로 1번 양초, 2번 양초, …, (N – 1) 번 양초라고 하자. 당신은 원하는 양초들을 골라 각각의 양초에 “토글 의식”을 진행할 수 있다.

k번 양초에 토글 의식을 진행한다는 것은 k번 양초부터 시작하여 시계 방향으로 k개의 양초의 상태를 바꾸는 것을 말한다. 즉 해당 양초의 불이 켜져 있었으면 끄고, 불이 꺼져 있었으면 켜야 한다. 모든 양초가 꺼져 있는 상태에서 시작해서 토글 의식만으로 모든 양초가 켜져 있는 상태를 만들면 원의 중앙에서 충명이 소환된다. 당연하지만 0번 양초에는 토글 의식을 진행할 수 없다.

예를 들어 5개의 양초를 사용할 경우, 4번 양초에 토글 의식을 진행하는 것은 4번, 0번, 1번, 2번 양초의 상태를 바꾸는 것이다. 원래 2번 양초 하나만 켜져 있는 상태에서 4번 양초에 토글 의식을 진행하면 0번, 1번, 4번 양초만 켜져 있는 상태가 될 것이다. 이 상태에서 2번 양초에 토글 의식을 거듭 진행하면 모든 양초가 켜지게 된다.

당신은 원하는 등급의 충명을 소환하기 위해서 정확히 무슨 양초들에 토글 의식을 진행해야 하는지 알고 싶다. 다음 물음에 답하여라.

1. 6등급 충명을 소환할 수 있을까? 가능하다면 그 방법을 1개만 찾고, 불가능하다면 불가능하다고 답하여라.

2. 7등급 충명을 소환할 수 있을까? 가능하다면 그 방법을 1개만 찾고, 불가능하다면 불가능하다고 답하여라.

3. 8등급 충명을 소환할 수 있을까? 가능하다면 그 방법을 1개만 찾고, 불가능하다면 불가능하다고 답하여라.

4. 19999999등급 충명을 소환할 수 있을까? 가능하다면 그 방법을 1개만 찾고, 불가능하다면 불가능하다고 답하여라. (참고: 19999999는 소수이며, 동시에 (4N+3) 꼴의 자연수기도 하다.)

보너스) 임의의 N에 대해 N등급 충명을 소환하는 모든 방법을 찾는 체계적인 전략을 구상할 수 있을까?