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
2 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
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} \)

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 - 2 years, 8 months ago

Log in to reply

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 - 2 years, 8 months ago

Log in to reply

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 - 2 years, 8 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 - 2 years, 8 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 - 2 years, 8 months ago

Log in to reply

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

Rohit Ner - 2 years, 8 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 - 2 years, 8 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 - 2 years, 8 months ago

Log in to reply

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

Brian Charlesworth - 2 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...