Problem 1259

To find the number of integers $k$ in the set $\{0, 1, 2, \dots, 2012\}$ such that $\binom{2012}{k}$ is a multiple of $2012$, we need to consider the prime factorization of $2012$.

First, we factorize $2012$:
$$2012 = 2^2 \times 503$$

Thus, $\binom{2012}{k}$ is a multiple of $2012$ if and only if it is a multiple of both $4$ and $503$.

### Step 1: Condition for $\binom{2012}{k}$ to be a multiple of $4$

We use the $p$-adic valuation, specifically $\nu_2$, which counts the number of factors of $2$ in a number. For $\binom{2012}{k}$ to be a multiple of $4$, we need:
$$\nu_2\left(\binom{2012}{k}\right) \geq 2$$

Using the property of $p$-adic valuation for binomial coefficients:
$$\nu_2\left(\binom{2012}{k}\right) = \nu_2(2012!) - \nu_2(k!) - \nu_2((2012-k)!)$$

From the lemma, $\nu_2(n!) = n - B(n)$, where $B(n)$ is the number of 1's in the binary representation of $n$. Therefore:
$$\nu_2(2012!) = 2012 - B(2012)$$
$$\nu_2(k!) = k - B(k)$$
$$\nu_2((2012-k)!) = (2012 - k) - B(2012 - k)$$

Thus:
$$\nu_2\left(\binom{2012}{k}\right) = (2012 - B(2012)) - (k - B(k)) - ((2012 - k) - B(2012 - k))$$
$$= 2012 - B(2012) - k + B(k) - 2012 + k + B(2012 - k)$$
$$= B(k) + B(2012 - k) - B(2012)$$

For $\binom{2012}{k}$ to be a multiple of $4$:
$$B(k) + B(2012 - k) - B(2012) \geq 2$$

### Step 2: Binary Representation Analysis

The binary representation of $2012$ is:
$$2012 = 11111011100_2$$
Thus, $B(2012) = 8$.

We need:
$$B(k) + B(2012 - k) \geq 10$$

### Step 3: Counting $k$ such that $B(k) + B(2012 - k) \geq 10$

We need to count the number of $k$ such that $B(k) + B(2012 - k) \geq 10$. This involves considering the cases where there is carrying in the binary addition of $k$ and $2012 - k$.

### Step 4: Condition for $\binom{2012}{k}$ to be a multiple of $503$

For $\binom{2012}{k}$ to be a multiple of $503$, $k$ must be a multiple of $503$. The possible values of $k$ are:
$$k = 0, 503, 1006, 1509, 2012$$

### Step 5: Combining Conditions

We need to combine the conditions from steps 1 and 4. We have:
- $512$ values of $k$ from the binary condition.
- $3$ values of $k$ from the multiple of $503$ condition.

Thus, the total number of $k$ that fail both conditions is:
$$512 + 3 = 515$$

### Conclusion

The number of integers $k$ such that $\binom{2012}{k}$ is a multiple of $2012$ is:
$$2013 - 515 = 1498$$