Exponential Growth: Solving for n in 500 000 Citizens

[Bassalisk]

Homework Statement

City has 500 000 citizens. One citizen knows a gossip. After 10 minutes, he tells that gossip to another 2 citizens. Those 2 citizens tell that gossip to another 2 citizens(both of them tell 2 citizens). After what time whole city will know the gossip?

Homework Equations

The Attempt at a Solution

Problem here is after how much iterations, whole city will know the gossip.

\sum 2^{i}= 500 000 where sum goes from i=0 to n. n are number of iterations i am looking for.

1+2+4+8+...=500 000

Problem is, I don't know how to find them, without using c++ :)

 

[daveb]

Do you know how to represent 500,000 in binary?

 

[Bassalisk]

Do you know how to represent 500,000 in binary?

Yes but I don't know where are you going with this. Its 1111010000100100000.

 

[daveb]

Say there are 10 people. Then 1 + 2 + 4 + 8 people covers everyone. So the binary representation 1111 means 4 iterations. The binary number 111 (7 people) means 3 iterations. Can you see now?

 

[Bassalisk]

I see but. What do I do if I have zeroes in the middle? Does this still hold? 500 000 is not a "nice" number in binary.

 

[daveb]

True, but using my analogy, if you need to tell only 10 people, three iterations (binary 111) only gets you 7 people. So you must have another iteration, and it means some of the people in the last iteration will either tell someone that already knows, or not tell anyone at all. That's why you have zeros in the binary representation, because 10 isn't a "nice" binary number.

 

[Bassalisk]

True, but using my analogy, if you need to tell only 10 people, three iterations (binary 111) only gets you 7 people. So you must have another iteration, and it means some of the people in the last iteration will either tell someone that already knows, or not tell anyone at all. That's why you have zeros in the binary representation, because 10 isn't a "nice" binary number.

I get it. I will try to figure the answer out.

Thank you.