From Puzzles to Programming

In the quadratic equation ax²+bx+c=0 what are the roots or possible equation solutions?

Answer

The method is to rewrite the equation into a form of (Dx+E)²=F and then the roots are easy to find.

To do so, multiply the above equation by 4a:

4a²x²+4abx+4ac=0

Now, add b² on both sides,

4a²x²+4abx+4ac+b²= b²

4a²x²+4abx+b²= b²-4ac

(2ax+b)²= b²-4ac

2ax+b = ± √(b²-4ac)

Hence, x = [-b± √(b²-4ac)]/(2a)

It is said that Al-Khwārizmī, Muhammad ibn Mūsā (780?-850?), an Arab mathematician, born in Khwārizm (now Khiva, Uzbekistan), had contributed to the solution of quadratic equations. His use of the expression 'al-jabr' in mathematics led later to the derivation of the English word 'algebra'. Also, the word 'algorithm' is derived from his name and is used now extensively in the art of computer programming.

On a hill, a cannon shoots a ball tangentially to the curve of the hill. The ball travels 2 meters in this direction and then falls down. What is the height reached by the ball from the ground knowing that the cannon is 2 meters from the ground and assuming that the hill makes a curve of the equation 4x²+2x+1?

Answer

To solve this problem we have to find first the equation of the tangent line to the hill curve because it is the route traveled by the cannon ball. To do that we need to find its slope with respect to the curve at the site of the cannon. The slope is nothing but the derivative of the hill curve function y = 4x²+2x+1.

Derivative of f(x) at x0 is the limit of the ratio of change in y to the change in x as x approaches x0. In mathematical terms it is written as y' =(dy)/(dx)as dx tends to zero and where dy = y-y0 and dx = x-x0.  In the figure above, as B approaches A, the segment AB approximates the tangent T. The change in yB as B approaches A is dy =yB - yA = y – y0 = BC. The change in xB will be dx = xB – xA = x - x0 = h. The ratio is dy / dx = BC/h. This is nothing but the slope of triangle ABC = AB. This slope will be that of T i.e. the value of dy / dx as x approaches x0.

For a curve of equation y = ax²+bx+c, the derivative dy/dx as x tends to x0 or dx tends to zero is:

 [(ax²+bx+c)–(ax0²+bx0+c)]/(x-x0) =

 [a(x-x0)(x+x0)+b(x-x0)]/(x-x0)= [a(x+x0)+b]

Now, as x tends to x0, then replacing x by x0 makes

y' = 2ax0+b. Therefore, derivative of the equation ax²+bx+c is 2ax+b.

Therefore, the slope of the tangent of the above curve at a point (x0 , y0) is(8x0+2). Now assume that the cannon is at abscissa zero i.e. it has the coordinates (0, 2) – remember that the cannon is at 2 meters from the ground. Hence, the slope of the tangent at that point will be 2. At that point the equation of the straight line will be

(y-y0)=(slope)(x-x0). Replacing for x0=0, y0=2 and slope = 2, we get y = 2x

The figure can be redrawn as:

Let d be the distance reached upwards by the ball from the hill. The height of the ball from the ground will equal to

d + 2. Now, y = 2x so d+2= 2x and x = d/2 + 1

Applying Pythagoras rule, we get d² = 4 - x². Replacing x for d/2 + 1, we get 5d² + 4d – 12 = 0. The possible solutions for this equation are d = 1.2 and d = -2 (this one is rejected) leaving the height that the ball reached above the ground as 2 + 1.2 = 3.2 m.

What is the quickest way to find the sum of numbers from 1 to n?

Answer

The usual way is to add the numbers serially. In the case when n = 10, Sum = 1+2+3+4+…………..10 = 55

Another way is to present these numbers geometrically in squares. Each number will present a set of squares. If n = 5 then n² = 25 and can be presented as shown in the figure.

The square can be written as n²/2 + n²/2

The sequence 1+2+3+….+n would be equal then to (half of the square + half of a diagonal) = n²/2  + n /2 = (n² + n) / 2 = n (n+1) / 2

If n = 10 then the sequence summation 1+2+3+….+10 = (100+10)/2 = 55.

Gauss, Carl Friedrich (1777-1855), the German mathematician who is famous for the Gaussian curve or the normal probability distribution graph developed another simple way to find the sum of sequence 1,2,3,…n-1,n. He placed the sequence in a decreasing order n,n-1,…3,2,1. Then he added both sequences to get (1+n)+(2+n-1)+(3+n-2)+…(n+1)= n(n+1). Now, each sequence is half this result i.e. n(n+1)/2

You have 20 boxes of balls. Each box contains 20 balls. You took one ball from the first box, two balls from the second box, three balls from the third box and so on until you reach the 20^th box where you took all the balls from it. How many balls did you take from the 20 boxes?

Answer:

Sum of balls taken can be written as: 1+2+3+4+5+…….+19+20

According to the formula (n² + n) / 2, this would be equal to (20²+20 ) / 2 = 420 / 2 = 210 balls.

The number of balls remaining would be 19+18+17+…..1+0 =  (19² + 19) / 2 = 190

A number of n close islands are connected with each other by bridges in a way that there is one bridge between two islands and every 2 islands are connected directly by a bridge. What is the number of these bridges?

Answer

To solve this problem, let us model it with a mathematical structure called "graph". A graph consists of set of points called vertices, and lines connecting the points called "edges". The islands problem can be represented by a graph where the islands are the vertices and the bridges are the edges of the graph.

Suppose you have 4 islands as shown in figure.

The number of bridges would be 6 bridges. We notice that from the first island, there are 3 bridges i.e. (n -1) bridges. The second island is also connected by 3 bridges, but since there is a common bridge with the first island then we have 2 additional bridges. The third island is connected by 3 bridges but it has 2 common bridges with the first and second islands which make only 1 extra bridge to be counted. The 4^th island has 3 bridges but all were counted before. Therefore, total number of bridges would be 3+2+1+0 = 6. In case of n islands, the number of bridges would be (n-1)+(n-2)+(n-3)+…..(n – n) =

n x n – (1+2+3+….n) = n² - (n² + n) / 2 = (n² - n) / 2 =  n²/2 – n/2 . If you have 100 islands then number of bridges would be (10000 – 100) / 2 = 9900 / 2 = 4950.

You have a square divided into 64 small squares as shown in the figure. What are the numbers that you have to put in a diagonal of squares so that their sum would be equal to 64?

Answer

1,3,5,7,9,11,13,15

The sum of odd numbers in such a sequence can be written as: 1+3+5+7+9+….(2n-1) =n². In our case, 1+3+5+7+9+11+13+15 = 8²= 64

How many integers in the set of numbers B = {1, 2, 3, 4, 5,….1000} are divisible by 3 or 5?

Answer

The numbers divisible by 5 are multiples of 5 i.e. of value = 5m where  1 < = m < = 200.

Thus, they count to 200. Similarly, the numbers divisible by 3 are of value 3n where 1 < = n < = 333. They count to 333. You may say now that there are 200 + 333 = 533 numbers in the set B which are divisible by 5 or 3, but this is wrong because there are numbers which are divisible by both 5 and 3 and thus we counted them twice. The count of those numbers divisible by both 3 and 5 is equal to the count of numbers divisible by (3 x 5) i.e. 15. This count is 1000 / 15 = 66. Thus, there are 533 – 66 = 467 numbers which are divisible by 5 or 3.

Consider a set of 10 positive integers whose sum is 100. Prove that there exist 2 numbers of this set whose sum is at least 20.

Answer

Let these numbers be a1, a2, a3, a4, a5, a6,…,a10. They can form 5 sets each having 2 numbers: {a1, a2}, {a3, a4}, {a5, a6}, {a7, a8}, {a9, a10}. The above can be proved by contradiction. In other words, we assume that there is no set of 2 numbers whose sum is equal or more than 20. It follows that the sum of any 2 numbers will be less than 20. Thus, {a1+a2} + {a3+a4} + {a5+a6} + {a7+a8} + {a9+a10} will be less than 5x20 or 100 which contradicts the statement that these numbers add to 100. Hence, there should be a set of 2 numbers that add to 20 or more.

This is the Pigeon-Hole principle in counting which states that if n objects are placed in m pigeon-holes or boxes where n > m, then some box will receive more than one object. In more general terms, if n and m are integers then some box will receive at least n/m objects because if all the m boxes contain less than n/m objects then the total number of objects will be less than m(n/m) < n objects.

The Magic Square:  

Try to fill the rest of the square by numbers from 1 to 9, in such a way that the sum of the numbers in each row, each column, and each diagonal is equal to 15. The numbers should not repeat.

Answer

 The number n of rows or columns is designated as order of the magic square. In the previous square, the order n = 3. The numbers of a magic square of order n are restricted to the sequence 1,2,3,4,……m where m is equal to n². Now, the sum of these numbers as we have seen in a previous case is equal to (m + m²) / 2 or m ( m + 1) / 2 or

n²( n²+1)/2. In the above square of order 3, then the sum of its numbers would be 45.

The sum of numbers in each of the n rows, each of the n column or each diagonal would be n(n²+1)/2. This is called the magic square constant. In the square above, this constant is equal to 15.

There might be many arrangements for a certain magic square of order n. But in one way or another, the combination of numbers in each row, each column or diagonals should sum to the square constant. In the above square, these combinations are: (1,5,9), (1,6,8), (2,4,9), (2,5,8), (2,6,7), (3,4,8), (3,5,7), and (4,5,6)

Another way to arrange numbers in the above square is as follows:

This is basically a flip-flop of the first row and the last row.

Can you prove for every integer n, that (n³ + n) is an even number? 

Answer

The integer n is either odd or even.

If it is even then it can be written as 2k. The above expression is written as 8k³ + 2k = 2(4k² + k) = even number.

If n is odd it can be written as 2k + 1, and the above expression is written as

(2k + 1)³ + 2k + 1 = (8k³ + 12k² + 6k + 1) + 2k + 1 = 2(4k³ + 6k² + 4k + 1) = even number.

You have 20 bags each containing 10 marbles. In 19 bags, each marble weighs 10 grams. In the remaining bag, each marble weighs 9 grams. Find this bag by using a digital scale only one time.

Answer

Label the bags by numbers from 1 to 20. Now take from the 1st bag 1 marble, from the 2^nd bag 2 marbles, and from the 3^rd bag 3 marbles, and so on...Then weigh these selected marbles. If all the marbles equally weigh 10 grams then the total weight of the selected marbles will be 10x[1+2+3+4+…20] = 10x[20(20+1)/2]  = 2100. However, the weight of some marbles from a bag j is 9xj and the weight of selected marbles will then be (2100 – j) grams. The difference in weight equals j where j = 1 to 20. So, if the difference is 18 then it is the 18^th bag that has marbles of 9 grams.