Find the number of even numbers among the following 1001 numbers: $$\left( \begin{matrix} 1000 \\ 0 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 1 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 2 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 3 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 4 \end{matrix} \right) . . . \left( \begin{matrix} 1000 \\ 1000 \end{matrix} \right)$$.

Note by Rohit Ner
3 years, 8 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

It is probably easiest to use a consequence of Lucas's theorem. Since the base 2 expansion of $$1000$$ is $$1111101000,$$ those values $$n$$ between $$0$$ and $$1000$$ inclusive that have a $$1$$ in their base 2 expansion in at least one place where the expansion of $$1000$$ has a $$0$$ will render $$\binom{1000}{m}$$ even.

Now it will be easier to count the complement here, i.e., the number of values which have $$0$$'s in their binary expansion wherever the binary expansion of $$1000$$ does, and then subtract this from $$1001.$$ So after fixing the four $$0$$'s in place, we have six other digit positions which can be filled by either a $$0$$ or a $$1.$$ Thus there will be $$2^{6} = 64$$ values $$m$$ which will render $$\binom{1000}{m}$$ odd, and thus there are $$1001 - 64 = 937$$ numbers in the given list that are even.

- 3 years, 8 months ago

Thank you sir for posting such a beautiful approach! Please let me know if there is any alternative method as many jee aspirants are unaware of Lucas theorem. :)

- 3 years, 8 months ago

You're welcome. :) Yes, I noticed the JEE hashtag and wondered if this was a suitable approach for that exam, but I don't know of any other way of solving this problem without resorting to brute force. I'll be interested to see if anyone else knows of a JEE-friendly method.

- 3 years, 8 months ago

Can you help me finding the value of : $\huge\sum _{ r=0 }^{ n }{ \frac { { \left( -1 \right) }^{ r } }{ \left( \begin{matrix} n \\ r \end{matrix} \right) } }$

- 3 years, 8 months ago

First note that $$\dbinom{n}{r} = \dbinom{n}{n - r}.$$

Then if $$n$$ is odd, we would also have $$(-1)^{r} = -((-1)^{n-r}),$$ which would mean that all the terms in the sum would cancel pairwise, leaving us with an answer of $$0.$$

It gets more interesting if $$n$$ is even. I found formula #34 in this link, which is complicated, but with $$p = 1$$ it would appear to give a general solution of

$$S_{n} = (1 + (-1)^{n})\dfrac{(n + 1)}{n + 2}.$$

So for $$n$$ odd we have $$S_{n} = 0$$, (as found before), and for $$n$$ even we have $$S_{n} = \dfrac{2(n + 1)}{n + 2}.$$

I found another excellent resource here which confirms this result, (and much more).

Great question; I've never encountered this type of sum before. :)

- 3 years, 7 months ago

Thank you a lot for your help sir. :) .

- 3 years, 7 months ago

I posted a question inspired by this last question of yours. I hope you don't mind. :)

- 3 years, 7 months ago

Its a very good question sir! A pleasure to see a question inspired by me! :)

- 3 years, 7 months ago

I'm glad that you liked (and solved) it. :)

- 3 years, 7 months ago