Help please!

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) $.

#Combinatorics #IITJEE

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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.

Brian Charlesworth - 6 years 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. :)

Rohit Ner - 6 years 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.

Brian Charlesworth - 6 years ago

@Brian Charlesworth – 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) } }$

Rohit Ner - 6 years ago

@Rohit Ner – 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. :)

Brian Charlesworth - 6 years ago

@Brian Charlesworth – Thank you a lot for your help sir. :) .

Rohit Ner - 6 years ago

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

Brian Charlesworth - 6 years ago

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

Rohit Ner - 6 years ago

@Rohit Ner – I'm glad that you liked (and solved) it. :)

Brian Charlesworth - 6 years ago

Math	Appears 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}$