From Puzzles to Programming

                               

 

1. Binary Tree

A woman had two girls. Each of these girls grew up and gave birth to 2 girls. Now each woman of these subsequent generations was giving birth to 2 girls and so on. What is the number of girls who were born in the 6^th generation?

Answer

Let each woman or girl be presented by a circle or node. Each node is connected with her 2 daughters by an edge. This will make a tree and since there are only 2 nodes out of each node then it is called binary tree. The level of each node will represent the generation's number.

Level 0

Level 1

Level 2

 

Let level 0 corresponds to first grandmother or generation 0. The number of girls at a generation n or level "n" will be equal to (2)ⁿ. At the 6^th generation, the number of girls would be 64.

 

2. In a little more difficult scenario, what would be the total number of all women in all the generations "n" assuming, of course, that none of the women died?

 

Answer

You can tell that this can be presented as sum of geometric progression 1+2+4+8+16+……+2ⁿ =  sum of 2ª as "a" goes from 0 to n. For example in case of 4 generations, the total number of women would be 2°+2¹+2²+2³ = 15. This sum would be equal to [(2ⁿ+¹) -1] or as in our case (2³+¹) – 1 = 15.

Let's find the sum of any geometric progression in general:

 

 

 

3. In the figure below, the first 5 of an infinite series of square. The outermost square has an area of 4, and each of the other inner squares is obtained by joining the midpoints of the sides of the square just outer (before) to it. Find the sum of the areas of all the squares.

 

Answer

If the length of a side of a square is "r" then the area is r².

The length "h" of sides in the immediate inner square can be calculated according to Pythagoras rule:

h² = r²/4  +  r²/4 = r² / 2 . h = r / √ 2. Hence, the area of the immediate inner area is h² =  r² / 2.

The sum of areas of all squares would be written as: r² + r²/2 +  r²/4  + r²/8 +   r²/16 +… =  r² (1 + 1/2 + 1/4 + 1/8 + …..) = (area of outermost square)(a + a X + a X²+……+ a Xⁿ).

It seems to be a problem of geometric progression with X = 1/2, a = 1, and n approaching infinity. We already found the formula of finding the sum of a geometric progression in example 16 (binary tree example), but let us find it in another way without using the ∑ notation:

Let S = a + a X + a X²+……+ a Xⁿ. Multiply both sides of the equation by X gives: X S = a X + a X²+……+ a Xⁿ + a Xⁿ+¹.

Subtracting these 2 equations, we get: S (1 - X) = a (1 - Xⁿ+¹). S = a (1 - Xⁿ+¹)/(1 – X). As n approaches infinity and if X is a ratio as in our example, then Xⁿ+¹ tends to zero and S = a/(1 – X).

Therefore, the sum of areas of the above infinite series of squares = 4 /(1 – 1/2) = 8

 

4. The circles ratio problems:

A huge ball of diameter 2R is squeezing onto a small ball in a corner as in the figure below. What is the diameter of the small ball?

 

 

 

 

4. A friend asked me one time to solve this case. I think you are familiar with the following spam email: “Bill Gates is sharing his fortune…Microsoft and AOL are now the largest Internet companies and in an effort to make sure that Internet Explorer remains the most widely used program, Microsoft and AOL are running an e-mail beta test. When you forward this e-mail to friends, Microsoft can and will track it (If you are a Microsoft Windows user)…. For every person that you forward this e-mail to, Microsoft will pay you $245.00. Now, for every email forwarded by each of these persons, Microsoft will pay you $243.00 and for every third person that receives it, you will be paid $241.00…and so on. Within few weeks, Microsoft will contact you for your address and then send you a check….”

 

Now, consider that an unemployed computer guy send this to, say 50 people, How many more forwardings (each recepient sending it to say 50 more people, each in turn send it to 50 more etc ) it would take to bankrupt Mr Gates, assuming his net worth is about 60 billion dollars?

 

Answer

Imagine the whole thing as a 'tree'. Let amount of money per person-email is 'a'. If the first person (node) send it to x number of people then he will get ax dollars. Suppose that each of these x persons will send it to an exactly x number of people and each of these will send it to an x number and so on... Then the total amount of money will be ax + ax^2 + ax^3 + ax^4 +... ax^n = Bill Gate money. Note n = number of generations of people in the tree or number of rounds. Applying geometric progression then this

sum = a [x^(n+1) - 1]/[x - 1]

{Note that x^(n+1) means x to power of (n+1)}

a[x^(n+1)-1]= sum(x-1).

x^(n+1) = 1+ [(x-1)sum/a]

n+1 = log [1+[(x-1)sum/a]] / log x

 

Now, sum = 60 billions, x = 50 persons allowed to be emailed per person, a = 243 $. putting these values, you will get n the number of rounds or generations.