2018 AIME1 12번

$3,~6,~9,~12,~15,~18$은 원소의 합이 $3$의 배수인 데 영향을 미치지 않는다. 

나머지 수를 원소로 갖는 부분집합의 원소의 합이 $3$의 배수가 되는 개수를 세어 보자.

약간의 치환을 이용하여 해결해보면 

$i->2^i $으로 바꿨을 때, $i$가 홀수이면 $2^i$는 $3$으로 나눈 나머지가 $2$이고, 짝수이면 $3$으로 나눈 나머지가 $1$가 되어서 

$1=2^0 , 2=2^1 , 4=2^2 , 5=2^3 , \cdots 17 = 2^{11} $로 치환하자. 

그러면 각 부분집합의 원소의 합은 이진법으로 표현되며

이때 원소의 합이 $0$부터 $4095$까지 각각 대응된다. 그래서 구하고자 하는 부분집합의 개수는 $1366$이며

나머지 $3$의 배수는 각각에 대해 $2$가지 경우가 있으므로 $3$의 배수인 부분집합의 개수는 

$1366 \times 2^6$ 이 된다. 그러므로 확률은 $\dfrac{683}{2048}$이 된다. 

구하고자 하는 정답은 $683$

사실은 $2$는 $\pmod 3$ 에 대한 원시근이기 때문에 위 풀이가 가능하다. 

예로 만약 $2$가 원시근인 모든 수에 대해 다음의 방법은 가능하다.