Remark that $2012 = 2^2 \cdot 503$, so $2012_{10} = 40_{503}$. Thus $503 | \dbinom{2012}{k} \Longleftrightarrow 503 \nmid k$ by Lucas's Theorem. Now we develop criteria for $4 | \dbinom{2012}{k}$. Now: $v_2 ( \dbinom{2012}{k} ) = v_2(2012!) - v_2(k!) - v_2((2012-k)!)$ However, $v_2(a!) = a - b$, where $b$ is the number of $1$'s in $a$'s base 2 representation. Hence it follows $v_2 ( \dbinom{2012}{k} ) \ge 2$ iff when you add $k$ and $2012-k$ in binary, there are at least 2 carries. Alternatively, when subtracting $k$ from $2012$ you have at least 2 carries. We count the number of times you have either $0$ or $1$ carries. $2012 = 11111011100_2$ It follows $2^8 = 256$ numbers carry exactly zero times, and $2^7 \cdot 2 = 256$ numbers carry exactly once. Thus $2013 - 512 = 1501$ of the $\dbinom{2012}{k}$ are divisible by $4$. Now it suffices to examine $\dbinom{2012}{503}, \dbinom{2012}{1026}, \dbinom{2012}{1539}$. Using the fact that $\frac{a}{\gcd(a,b)} | \dbinom{a}{b}$, we know the first and third are divisible by $4$. By grinding out binary forms, we get $2^8 | \dbinom{2012}{1026}$, so it follows $1501 - 3 = \boxed{1498}$ of them are divisible by $2012$. (Hopefully no silly calculation errors... the ideas are correct though) EDIT : oops can't do arithmetic to save my life.

hm the answer was 1498... i was off by two (1496) on the actual test. darn.

dinoboy wrote: It follows $2^8 = 256$ numbers carry exactly zero times, and $2^7 \cdot 2 = 256$ numbers carry exactly once. Thus $1500$ of the $\textstyle\binom{2012}{k}$ are divisible by $4$. I think this ought to be $2013-256-256 = 1501$, which would fix the off-by-one error. But yeah, this is definitely a better fit for AIME #15 (or as early as 13) than CGMO #8.

We begin with the following lemma: Lemma. $\nu_2(n!) = n - a$, where $a$ equals the number of 1's in the binary representation of $n$. Proof. Consider multiplying $n!$ by $n+1$. If $n+1$ is a multiple of 2 but not 4, then adding 1 to $n$ does not change the number of 1's in the binary representation. If $n+1$ is a multiple of $2^n$, then the number of 1's in the binary representation decreases by $n$ -- if $n$ is even, then the number of 1's increases by 1. The rest is a simple induction argument. Hence we need $$\nu_2(2012!)-\nu_2(k!)-\nu_2((2012-k)!) \leq 1$$for the condition \alert{not to hold}. Let $B(x)$ denote the number of 1's in the binary representation of $x$. Then we must have $$2012-B(2012)-2012+B(k)+B(2012-k) \leq 1 \implies B(k)+B(2012-k) - B(2012) \leq 1.$$Observe that $B(k)+B(2012-k) \geq B(2012)$, with equality if and only if there is no carrying. By carrying once, we increase the number of 1's in $B(2012)$ by 1 while would have counted that digit twice, hence increasing the total by one. Thus, the condition is equivalent to counting the number of integers $k$ such that $k+(2012-k)$ carries at most once. To do so, consider the binary representation of $$2012=11111011100_2.$$In the first case, if there is no carrying, we can assign each digit to either one of $k$ or $2012-k$. This gives us $2^8=256$ such assignations, and thus 256 such numbers. In the second case, the carrying must be to a 0-digit right next to a 1-digit. There are 2 ways to select this digit, and another $128$ ways to assign the other digits, for 256 more such numbers $k$. Next notice that $503$ does not divide ${2012 \choose k}$ if and only if $k$ is a multiple of 503. Observe that the three numbers ${2012 \choose 503}, {2012 \choose 1006}, {2012 \choose 1509}$ all pass the mod 2 test -- thus there are $512+3 = 515$ integers $k$ that fail. The answer is then $\boxed{1498}$.

The answer is $1498$. In order for $2012 | \binom{2012}{k}$, we must have $503 | \binom{2012}{k}$ and $4| \binom{2012}{k}$. Since $503$ is prime, it is easy to see that all $k$ satisfy $503 | \binom{2012}{k}$ except $k = 0, 503, 1006, 1509, 2012$. Now for $4| \binom{2012}{k}$, consider binary. An alternate form of Legendre's Theorem states that $$v_p(n!) = \frac{n-s_p(n)}{p-1}$$where $s_p(n)$ is the sum of digits in base $p$. This can be proven by summing in two ways. Write $\binom{2012}{k} = \frac{2012!}{k!(2012-k)!}$, so $v_2(2012!) = 2004$ and $v_2(k!(2012-k)!) = v_2(k!)+v_2((2012-k)!) = 2012 -s_2(k) - s_2(2012-k)$. Therefore the problem is equivalent to finding all $k$ satisfying $$s_2(k) + s_2(2012-k) \geq 10.$$We do this by complementary counting. Since $2012 = 11111011100_2$ and carrying will always increase the amount of $1$s, we just need to find $s_2(k) + s_2(2012-k) = 8$ or $9$. For $9$ there cannot be carry, so for the digits with $1$, there are $2^8$ cases. For $9$, there are two subcases on which digit to have carry, which results in $2^7+2^7$ ways. Now, subtracting from the total: $$2013 - (2^8+2^7+2^7) = 1501.$$Now, $0$ and $2012$ were already subtracted, but $503, 1006, 1509$ were not. Thus the answer is $1501-3 = \boxed{1498}$, as desired.

Hi; what is the issue in this solution? From OTIS We have $\binom{2012}{k} = \frac{2012!}{k!(2012-k)!}$. In order for $2012$ to divide this quantity, the numerator must have at least one more factor of $2012$ than the denominator. Note that $2012 = 2^2 \cdot 503$, so by Legendre's Formula, we can see that $2012!$ has $4$ factors of $2012$. Thus, it remains to find all possible values of $k$ such that the denominator has $3$ or less factors of $2012$. Clearly $k=0, 2, 4, 503, 1006, 1509, 2012, 2010, 2008$ doesn't work, but $k=3, 2009$ does. If $503 < k < 1509$ and $k \neq 1006$, then the denominator will always have a $2 \cdot 1006$ term and two $4 \cdot 503$ terms. That makes a total of $3$ factors of $2012$, which works. This gives a total of $1004$ possibilities. If $4 < k < 503$ or $1509 < k < 2008$, we have the same scenario as above, for a total of $498 \cdot 2 = 996$ possibilities. Summing gives $2000$, but $3$ and $2009$ also work, for a total of $2002$, the answer.

Quote: In order for $2012$ to divide this quantity, the numerator must have at least one more factor of $2012$ than the denominator. Not true. Do you see why?

Great computational exercise! Note that if $4 \cdot 503 \mid \binom{2012}{k}$, we require $v_2\left(\binom{2012}{k}\right) \geq 2$ and $v_{503}\left(\binom{2012}{k}\right) \geq 1$. Let's consider $p = 2$ first. We have $$v_2\left(\frac{2012!}{k!(2012-k)!}\right) = v_2(2012!) - v_2(k!) - v_2((2012-k)!) \geq 2$$Since $v_2(2012!) = 2004$ we have $$v_2(k!)+v_2((2012-k)!) \leq 2002$$Using the fact that $v_2(k!) = k-s(k)$ where $s(k)$ denotes the sum of the digits in the binary representation of $k$, we see that the above simplifies to $$s(k)+s(2012-k) \geq 10$$ To count the number $k$ that satisfies this relation, the key is to complementary count and find the number of $k$ such that $s(k)+s(2012-k) < 10$. Since $2012 = 11111011100_2$, we have $s(k) + s(2012-k) \geq 8$. One can imagine $k$ and $2012-k$ as $11$ digit binary numbers with leading zeroes allowed. Case 1: $s(k)+s(2012-k) = 8$ There are $2^8$ ways to achieve this because we cannot have carries. Case 2: $s(k) + s(2012-k) = 9$ Note that we cannot have the units digit of $k$ and $2012-k$ in binary be $1$ or else $s(k)+s(2012-k) \geq 10$. So we have 2 possible places to carry - one at the leftmost zero and the other at the middle zero. Thus there are $2^7 \cdot 2 = 2^8$ ways. Since there are $2^8+2^8 = 512$ bad cases, the amount of good values of $k$ is $2013-512 = 1501$. However, we still need to check $p = 503$. It's easy to see that $503 \mid \binom{2012}{k}$ when $503 \mid k$. We've already removed $0$ and $2012$ when considering $v_2$ but we still need to remove $503, 1006, 1509$. Removing these 3 yields an answer of $1501-3 = 1498$.

solved with hint on alternate legendre formula; my writeup for this is shambles Note that $v_22012!=2004$. We want $$4\cdot503\mid\binom{2012}k\implies v_2k!+v_2(2012-k)!\le 2002,k\ne503n$$for nonnegative n. Now, I quote a proof from Wikipedia about an alternate form of Legendre's Theorem, which states that $v_p(n!) = \frac{n-s_p(n)}{p-1}$: attached below So we want $$2012 -s_2(k) - s_2(2012-k)\le2002\implies s_2k-s_2(2012-k)\ge10.$$Then, we can complementary count this; let $2012 = 11111011100_2=S$. In particular, in strings S',S'' in base 2 with values k,2012-k in base 10, their respective digits will sum to the respective digit in the binary version of 2012, which means if there's a 1 in the $i$th digit of S there will be a 1 in at least one of S',S'' in their $i$th digits, meaning the sum of the digits in S' and S'' is at least 8 (the digit sum of S) (since you could have two 1s that sum to a 0 in the respective digit of S, it'd just carry, but that adds 2 to the total sum but only subtracts 1 from total of S' and S'', which means it could be 9). If $s(k)+s(2012-k) = 8$, there are $2^8$ ways because no carrying. If $s(k) + s(2012-k) = 9$, we see that there cannot be a 1 in S' or S'' in the units since you'd need another 1 in S' or S'' in the second digit (read from right to left) in order to get a 0 by carrying; this would add 3 to the total sum and subtract 1 but that would result in at least 10. So it can only have a carry in the other two 0s, whence there are 2^7*2=2^8 ways. In total, there are 512 ways that don't work; excluding 503,1006,1509 as k, we get $2013-512-3=1498$ as our final answer.

Consider powers of $2$. By Legendre's, we have \[\nu_p(n!) = \frac{n - s_p(n)}{p-1}\]\[\implies \nu_2\left(\binom{2012}{k}\right) = s_2(k) + s_2(2012-k) - s_2(2012)\] which needs to be at least $2$. To count the number of such $k$, we use the complement. This is equivalent to $k_2+(2012-k)_2$ having $0$ or $1$ carries when considering addition. For $0$ carries, we merely distribute the eight $1$'s to $k_2$ and $(2012-k)_2$, doable in $2^8=256$ different ways. For $1$ carry, the answer lies in blocks where $1+1=0$ carries over to $0+0+1=1$. As there are two such blocks, there are $2\cdot2^7=256$ ways here. For powers of $503$, Legendre makes it clear that only $k \equiv 0 \pmod{503}$ will fail, so our answer is $2013-256-256-4+1=\boxed{1498}$ by PIE.

We instead find the invalid values of $k$. Note that $2012 = 2^2 \cdot 503$, so we must take care of these primes separately. For $p=503$, it's easy to see (through Lucas, for instance) that only multiples of 503 will not work, giving us 5 values. Using Legendre's on $p=2$, we want \[1 \ge \left(2012-s_2(2012)\right) - \left(k-s_2(k)\right) - \left((2012-k)-s_2(2012-k)\right)\]\[\implies s_2(k)+s_2(2012-k) = 8,9,\] where $s_2(n)$ denotes the number of 1's in $n$. With $s_2(2012)=s_2(11111011100_2)=8$, this is equivalent to the binary representations of $k$ and $2012-k$ having at most 1 carry upon addition. No carries: We distribute the 1's in $2^8=256$ ways. 1 carry: One of the two zeros in the $2^5$ or $2^1$ place value will be split into two 1's, while 1 in front will be forced to become two 0's. Thus we have $2 \cdot 2^7=256$ more ways. Finally, we see that the two overlaps in both $p=503$ and $p=2$ are 0 and 2012, giving us our answer of \[2013-(512+5-2)=\boxed{1498}.\]

Note that $2012=4(503)$. So we need $4 \mid \binom{2012}{k}$ and $503 \mid \binom{2012}{k}$. First let us examine $503 \mid \binom{2012}{k}$. By Lucas' theorem, suppose $k=m_1 503 + m_0$ then $$\binom{2012}{k} \equiv \binom{4}{m_1}\binom{0}{m_0} \mod{503}$$Clearly, we are fine when $m_0 \neq 0$. Otherwise, we aren't fine so all $k=0, 503, 1006, 1509, 2012$ do not work. Now we examine $4 \mid \binom{2012}{k}$. This means we must have \begin{align*} \nu_2(2012!)-\nu_2(k!)-\nu_2((2012-k)!) &\geq 2\\ 2012-s_2(2012)-k+s_2(k)-2012+k+s_2(2012-k) &\geq 2 \end{align*}Since $2012=11111011100_2$, we have that $s_2(k)+s_2(2012-k) \geq 10$. Note that if $k_2$ has a $1$ or a $0$ in places where $2012_2$ has a $1$, then whatever value it takes from $s_2(2012)$ will just be added back with $s_2(k)$, thus not changing the total $s_2$ when we need to increase it from $s_2(2012)$ by at least $2$. Note now that the only way for $s_2(k)+s_2(2012-k) > s_2(2012)$ is if $k_2$ is $1$ at a place where $2012_2$ is $0$. Thus, the amount we increase $s_2$ by is just the amount of times $s_2(k)+s_2(2012-k)$ carries a digit. We need it to carry at least twice. So now we can proceed by complementary counting. (We count front to back) If no carrying happens, then we have $2^8$ ways to make $k$ and none exceed $2012$. If one carry happens, then $k_2$ can't have a $1$ at the $11$th place as that creates two carries at least, and at the $5$th and $6$th place or the $9$th and $10$th place, $k_2$ must be $01$ in order to ensure only one carry happens. Thus if $k_2$ is $01$ at the $5$th, $6$th places, then it must be $0$ at $10$th and $11$th places as well which means we have $2^7$ ways to make $k$, and due to $5$th being a $0$, $k$ never exceeds $2012$. Similarly, we have $2^7$ ways to make $k$ for the other distribution of $01$. Now note that $503, 1509$ are both odd which means they will have at least two carries, and $1006=1111101110_2$ with $1$s at both the second to last place and the $6$th place counting back to front, which ensures at least two carries as well. Thus these three numbers are not in the bad values we just calculated so we must subtract them separately. In total, we have then $2013-256(2)-3=2013-515=1498$ integer $k$ that work. Remark: Apparently the neat little insight I had about digit carrying is just a special case of Kummer's theorem, what a way to ruin the fun.

The answer is $\fbox{1498}$. Since $2012 = 2^2 \cdot 503$, we examine $\nu_2$ and $\nu_{503}$ separately. By Kummer's theorem, we have \[\nu_{503}\left(\binom{2012}{k}\right) = \frac{s_{503}(k) + s_{503}(2012 - k) - 4}{502},\]which is $0$ if and only if $503 \mid k$. Similarly, \[\nu_2\left(\binom{2012}{k}\right) = s_2(k) + s_2(2012 - k) - 8,\]so if $2012 \mid \binom{2012}{k}$ then the addition $k + (2012 - k)$ produces at least $2$ carries in binary. We'll instead count the number of integers $k$ that give $0$ or $1$ carry. By writing $2012 = 11111011100_2$, we see that $2^8 = 256$ values of $k$ give no carries. If some $k$ produces exactly $1$ carry, it's either in the $4$s place or $64$s place, since $01$ occurs in sequence from right to left after the carry. Both subcases yield a total of $2^7 = 128$ possible values, so we get a total of \[2013 - 256 - 128 - 128 = 1501\]values of $k$ for which $\nu_2\left(\binom{2012}{k}\right) \geq 2$. Among these integers, only $503, 1006, 1509$ invalidate the constraint on $\nu_{503}$, so we're left with a total of $1501 - 3 = 1498$. $\square$ Remark. Originally I was off by one, since I counted $2012$ integers in total instead of $2013$...