Answer to Question #109031 in MatLAB for Adewale Gloria

Question

QUIZ 2

Imagine it takes 1 second to make 1 count. Each count can be a maximum of 5 persons (this is being realistic; we humans don’t have the capacity for more than this). If there are 4 billion people in the room, can you think of a method we can use to count them in under 50 seconds?

Answer 1

We will assume that each of the named number of people $N_{all}=4\cdot10^9$ will obey our counting rules. Then you can count five people and designate two of this number as the next counters. These new counters will have to act just like you - count the next 5 people and assign two of them to count the next more distant neighbors. You can start, for example, from the lower left corner of the room. Next counters are assigned along the left side up and along the right side to the right. Each new counter will have an indication that it should count only right and above. He assigns the extreme counted people to count in the same directions. If you denote by the number $n$ the number of the counting stage, then it is easy to see that the number of people counted will be a geometric progression.

(1) $S_n=5+2\cdot 5+4\cdot 5+...+2^n\cdot 5=(n=0, 1,...)=5\cdot\frac{2^{n+1}-1}{2-1}\simeq5\cdot 2^{n+1}$ . According to the problem condition, one second takes each step of the counting. Therefore, this number of people (1) will be counted in $n$+1 seconds. To count $N_{all}$ people will take so time that

$S_n=N_{all}$

$5\cdot2^{n+1}=4\cdot 10^9$ We determine $n+1=log2(0.8\cdot 10^9)\simeq \frac{log(10^9)}{log(2)}=\frac{9}{0.3}=30$

Answer: we can to count 4 billion people in about 30 seconds if we use the proposed algorithm with a geometrically increasing number of counters.