Waste less time on Facebook — follow Brilliant.
×

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

Note by Rohit Ner
1 year, 10 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 · 1 year, 10 months ago

Log in to reply

@Brian Charlesworth 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 · 1 year, 10 months ago

Log in to reply

@Rohit Ner 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 · 1 year, 10 months ago

Log in to reply

@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 · 1 year, 10 months ago

Log in to reply

@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 · 1 year, 10 months ago

Log in to reply

@Brian Charlesworth Thank you a lot for your help sir. :) . Rohit Ner · 1 year, 10 months ago

Log in to reply

@Rohit Ner I posted a question inspired by this last question of yours. I hope you don't mind. :) Brian Charlesworth · 1 year, 10 months ago

Log in to reply

@Brian Charlesworth Its a very good question sir! A pleasure to see a question inspired by me! :) Rohit Ner · 1 year, 10 months ago

Log in to reply

@Rohit Ner I'm glad that you liked (and solved) it. :) Brian Charlesworth · 1 year, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...