Help please!

Find the number of even numbers among the following 1001 numbers: (10000),(10001),(10002),(10003),(10004)...(10001000)\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
4 years, 1 month ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 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 10001000 is 1111101000,1111101000, those values nn between 00 and 10001000 inclusive that have a 11 in their base 2 expansion in at least one place where the expansion of 10001000 has a 00 will render (1000m)\binom{1000}{m} even.

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

Brian Charlesworth - 4 years, 1 month 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 - 4 years, 1 month 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 - 4 years, 1 month ago

Log in to reply

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

Rohit Ner - 4 years, 1 month ago

Log in to reply

@Rohit Ner First note that (nr)=(nnr).\dbinom{n}{r} = \dbinom{n}{n - r}.

Then if nn is odd, we would also have (1)r=((1)nr),(-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.0.

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

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

So for nn odd we have Sn=0S_{n} = 0, (as found before), and for nn even we have Sn=2(n+1)n+2.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 - 4 years, 1 month ago

Log in to reply

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

Rohit Ner - 4 years, 1 month 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 - 4 years, 1 month ago

Log in to reply

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

Rohit Ner - 4 years, 1 month ago

Log in to reply

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

Brian Charlesworth - 4 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...