| Solution to Puzzle 3:
Each one contributed $30, amounting
to $360. Basically, you want me to solve the equation 41m - 12n = 9 in integers { and you have given that m and n are greater than 0 and m < 12 }. Look at that equation. 12n is divisible by 3, 9 is divisible 3, so 41m also must be divisible by 3, which means m is divisible by 3. Putting m = 3k, we get a simpler equation 41k - 4n = 3. Such equations are called indeterminate or Diophantine equations and there are many methods to solve them. I give two of them. |
Correct Answer was sent by : |
Solution 1:I am using the symbol == to denote "is congruent to" as there is no symbol for congruence in standard ASCII set. So, 41k == 3 (mod 4). { We can consider 4n == 3 (mod 41) also, but in that case we need to consider a set 40 residues, 0,1,2,...40, whereas here we need to consider only 3 residues } Since 41 and 4 are mutually prime, this is soluble by considering the complete residue system. Thus, by putting k = 0, 1, 2, 3, we get 41k is congruent to 0, 1, 2, 3 respectively (mod 4). { 0, 41, 82 and 123 give remainders 0, 1, 2, 3 on dividing by 4 }. So k = 3 is a solution to the congruence 41k == 3 (mod 4). So k = 3, which means n = (41.3 - 3) / 4 = 30 and m = 3.3 = 9. Solution 2:To solve 41k - 4n = 3. Express (41/4) as a continued fraction in such a way that there are an odd number of terms in the expansion. Now, leave the last term and evaluate the fraction. Let it be (a/b). Now 41b - 4a = 1. Multiplying all the terms of the equation by 3, we get the solution to 41k - 4n = 3. The continued fraction expansion of (41/4) is 10 + (1/4), giving the values (10/1) and (41/4). The penultimate fraction is (10/1). So 41.1 - 4.10 = 1. Multiplying it by 3, we get 41.3 - 4.30 = 3. Thus k = 3, n = 30. So m = 3.3 = 9. { What if we want to solve 4a - 41b = 3 ? Now, (4/41) = 0+(1/(41/4)) = 0+(1/(10+(1/4))) = 0+(1/(10+(1/3+(1/1)))), giving the successive terms 0, (1/10), (3/31) and (4/41). Hence, 4.31 - 41.3 = 1, or 4.93 - 41.9 = 3 So, a = 93, b = 9. } General Solution:In fact, there are infinite number of solutions to this problem. Since (1,10) is a solution to 41k - 4n = 1, all numbers of the form (4j+1, 41j+10), where j is an integer, is the general solution to it. So, (12j+3, 123j+30) is the general solution to 41k - 4n = 3, So, (36j+9, 123j+30) is the general solution to 41m - 12n = 9. When j = 0, m = 9, n = 30, our required solution. When j = 1, m = 45, n = 153 When j = 2, m = 81, n = 276 and so on. We can find the solution in negative numbers also. Thus: When j = -1, m = -27, n = -93 When j = -2, m = -63, n = -216 and so on. This type of equations was first solved by Brahmagupta and Bhaskara II. The principle is basically the same as solution (2) above, the method is a little more laborious. The method is called "kuttakaram". In fact, continued fractions were invented by these Indian mathematicians, but is attributed to Lagrange, Euler and others, who lived several centuries later. If you have questions, contact Umesh
Solution 3:Let
x be the original contribution thrown in by the 12
people. Note that x is a positive integer [x > 0] |
|
Correct
Answer was given by : |
Solution to Puzzle 4: The
following solution is sent by Umesh
PN Note
1: I used SQRT(x) to mean the positive square root of x,
as I could not find a square root symbol in any font
which will work in all the web browsers on various
platforms. I like this problem very much. This problem can be stated in different ways, leading to surprisingly different puzzles. It is interesting to observe the relationships between certain sets of numbers possessing certain properties. Ramanujan was a keen observer of behaviors of numbers and had done lot of research on it. I believe Ramanujan had observed the relationship between the numbers that form the solution to this problem and the continued fraction expansion of SQRT(2). So, the 'superhuman' powers of Ramanujan to solve this problem while stirring vegetables can be explained. First of all, let us assume that there were n houses in the street, and the number of the house in question is m. The problem is to : Find m and n (greater than 50 but less than 500) such that 1 + 2 + ... + (m-1) = (m+1) + (m+2) + ... + n. Using the well-known result that the
sum of the first k natural numbers is k(k+1)/2, we can
rewrite the equation as (m-1)m/2 = n(n+1)/2 - m(m+1)/2.
It follows that n(n+1) = m(m-1+m+1) = 2m2.
That is So, if we get n, m = SQRT((n(n+1)/2), or if we get m, n = (-1 + SQRT(1 + 8 m2))/2 .... (ii) Thus, this problem can be stated in two other ways. Find a triangular number (greater than 1275 but less than 125250) that is a perfect square. Its square root will give an m, and n can be found out by (ii). Find n (greater than 50 but less than 500) such that the sum of the first n natural numbers is a perfect square. This will give n, from which m can be found out using (ii). |
| Method 1:
Starting from 1, add each natural number and check
whether the sum is a perfect square. If it is, the last
number added is a solution giving n. Example: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, ... and only two of them so far, 1 and 36, are perfect squares, giving (m, n) as (1, 1) and (6, 8). But this method is too laborious. We cannot continue this 500 times, and again, 10000 times. So let us find another method. Now, look at (i). Either n or (n+1) is an even number. If n is even, let n = 2k. Then (i) becomes p(2k+1) = m2. Now, since k and (2k+1) cannot have a common factor greater than 1, each of them must be a perfect square in order that their product is a perfect square. Let (2k+1) = a2 and k = b2. This means a2 - 2b2 = 1. Similarly, if (n+1) is even and (n+1) = 2k, then (2k - 1)k = m2; (2k-1) and k must be squares. Let (2k - 1) = a2 and k = b2, a2 - 2b2 = -1. Combining the two cases, a2 - 2b2 = ± 1 .... (iii) Then m = ab, and n is given by (ii). So, our problem can be restated as Solve the integer equation a2 - 2b2 = ± 1 (such that ab > 35 and < 354). This is Brahmagupta-Bhaskara equation, wrongly known as Pell's equation (In fact, John Pell (1611-1685) did nothing for this equation, as we see later) in the western world. The equation x2 - Dy2 = 1 was considered as a challenging problem since the beginning of arithmetic. Archimedes' famous cattle problem reduces to x2 - 4729494y2 = ± 1. This type of equations was first solved by Brahmagupta (AD 7th century) using his "Chakravala" method. Later, Bhaskara II (AD 12th century) simplified this method. In the Western world, mathematicians like Fermat and Frenicle devised many such equations as a challenge to other mathematicians.(Brahmagupta states "A person who can solve the equation x2 - 92y2 = 1 within a year, is a mathematician"), and it was Wallis and Brouncker who solved it with all generality. In 1768, Lagrange gave the first complete proof of the solvability of x2 - Dy2 = 1, based on continued fractions. Euler, though discussed this equation in his famous book 'Algebra', did nothing to its theory other than giving its credit wrongly to Pell, thinking that Wallis' proof was Pell's. We will ignore the trivial solution (± 1, 0) to this equation. x2 - Dy2 = 1, where D is not a perfect square, is always soluble and has infinite number of solutions. If (p, q) is the smallest positive solution (called the fundamental solution), then all solutions are given by the equation x + y.SQRT(D) = (p + q. SQRT(D))k, k = 1, 2, 3, .... .... (iv) We know that (3, 2) is the fundamental solution to x2 - 2y2 = 1. So, if you know any solution (p, q), the next solution is obtained by (x + y.SQRT(2))= (p + q.SQRT(2)) (3 + q.SQRT(2)), which means x = (3p + 4q), y = (2p + 3q) .... (v) Method 2a: Starting from (p, q) = (1, 0), find the next solution (a, b) = (3p + 4q, 2p+3q). This set will give half of the solutions. Using (v), m = a.b and (ii), (a,
b) = (3.1 + 4.0, 2.1 + 3.0) = (3, 2); m = 6, n = 8 So, we got half the solutions where n < 10000. We can continue it any further. x2 - Dy2 = -1, where D is not a perfect square, is not always soluble. (For example, x2 - 3y2 = -1 doesn't have a non-trivial solution). When it is soluble, it also has infinite number of solution. If (p, q) is the smallest positive solution (the fundamental solution) to x2 - Dy2 = -1, then all solutions are given by the equation (iv) By inspection, we can find (1, 1) is the fundamental solution to x2 - 2y2 = -1. So, if we know one solution (p, q), the next solution is given by (v). So, Method 2b: Starting from (p, q) = (1, 1), find the next solution (a, b) = (3p + 4q, 2p+3q). This set will give the other half of the solutions. Using (v), m = a.b and (ii), (a,
b) = (3.1 + 4.1, 2.1 + 3.1) = (7, 5); m = 35, n = 49 So, we got the other half solutions where n < 10000. So, the final solution is (m, n) = (1, 1), (6, 8), (35, 49), (204, 288), (1189, 1681), (6930, 9800) This means 0
= 0 Now, let us consider the solution to (iii). They are, put in the ascending order, (1, 0), (1,1), (3, 2), (7, 5), (17, 12), (41, 29), (99, 70), (239, 160), (577, 408),..... Do you find any relation between these values. We may observe the following. These values (a, b) are the solutions to the equation (x + ySQRT(2)) = (1+SQRT(2))k, k = 0, 1, 2, ..... In other words, If (p, q) is any solution to a2 - 2b2 = ± 1, the next solution is given by (p+2q, p+q). So, Method 3: Starting from (p, q) = (1, 0), find the next solution (a, b) = (p+2q, p+q). This set will give all the solutions. A little theory : Now, having described all the methods, let us discuss some theory. The methods I described are based on the western treatment of this so-called "Pell's equation". For more information, you may refer to any book on Number Theory. The proof of (iv) may be found in any of these books. Brahmagupta's Chakravala method, though simplified by Bhaskara, is too laborious to describe here. In 1768, Lagrange gave the first complete proof of the solvability of x2 - Dy2 = 1, based on continued fractions. I skip the proof, but describe the method. Method 4: In order to solve a2 - 2b2 = 1, express SQRT(D) as a periodic infinite continued fraction. Let n be the periodic length of the expansion. Let (p/q) be (n-1)th convergent in any period. Then, p2 - Dq2 = (-1)n. This condition, giving one solution per period, will give all the solutions. When D = 2, SQRT(2) = 1 + (1 + 1/(2 + 1 / (2 + 1 / (2 +......)))))) = [1;2]. Since n = 1, all convergents are solutions. The convergents of this continued fraction are (1/1), (3/2), (7/5), (17/12), (41/29),....., giving the same numbers we found above. The other results are also obtained from this easily. Questions ? Ask Umesh |
