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..
더보기