What's His Street Address? How Many Neighbors Does He Have?Date: 09/29/2010 at 12:42:43 From: Kevin Subject: 1+2+3+4+5... more than 20, less than 500... I'm working on a word problem and I'm having trouble getting started. Imagine a street with houses numbered 1, 2, 3, 4, and so on. There are more than 20 houses but less than 500. A resident who lives in one of the houses on this street finds that if he adds the numbers from the first house up to his house, the total is exactly half the sum of all the houses from the first one to the end of the street. What is the number of the man's house, and how many houses are on the street? I added the numbers from 1 to 21 as the lowest possible number of houses; then I added the numbers from 22 on up ... but it seems I'm just pursuing a brute force strategy with a lot of addition. Can you show me how to begin? Is there a formula that will help me? Date: 09/30/2010 at 02:30:48 From: Doctor Greenie Subject: Re: 1+2+3+4+5... more than 20, less than 500... Hi, Kevin -- I have been thinking about this problem, off and on, for a couple of hours now. I don't yet see a nice algebraic approach to finding the solution (or perhaps "a" solution; there might be more than one). I used a spreadsheet to generate a bunch of numbers and then visually scanned the numbers to find one solution -- but that is not a very satisfying way to solve the problem. I will make some comments about the problem and invite other volunteers here at Dr. Math to see it. Perhaps one of them will see an algebraic path to a solution. Let's use "n" for the number of the man's house and "m" for the total number of houses on the street. It appears you need to add the numbers from 1 to n and then add the numbers from n + 1 to m, and try to get the two sums the same. I'm guessing that will be a harder path to follow than trying to find two sums, one from 1 to n and another from 1 to m, with the second sum being twice the first. The sum of the numbers from 1 to k is given by a well-known formula: k(k + 1)/2 To solve the problem, we need to have n(n + 1)/2 equal to half of m(m + 1)/2 n(n + 1)/2 = [m(m + 1)/2]/2 n(n + 1)/2 = m(m + 1)/4 Or just 2n(n + 1) = m(m + 1) To find integers n and m that satisfy this equation, we can (1) look at the prime factorization of the quantity (n * (n + 1)); (2) add another factor of 2; and (3) recombine the factors into two consecutive numbers m and m + 1 But this seems to be a method that is almost pure trial and error.... - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ Date: 09/30/2010 at 02:44:40 From: Doctor Greenie Subject: Re: 1+2+3+4+5... more than 20, less than 500... Hello again, Kevin -- I used a slightly different approach with my spreadsheet and discovered there is only one solution if the number of houses is less than 500. There is, however, a solution outside the specified range where the man's house number is less than 500 but the total number of houses is greater than 500. I'm still thinking about possible algebraic approaches.... - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ Date: 09/30/2010 at 07:42:42 From: Doctor Anthony Subject: Re: 1+2+3+4+5... more than 20, less than 500... The formula for the sum of the first n integers is 1 + 2 + 3 + ... + n = n(n + 1)/2 So if the man's house number is m - 1 and the number of houses on the street is n - 1, then we require the following: Values on n and m for which P(m,2) = C(n,2) n = 20 C(n,2) = 190 m = 14 P(m,2) = 182 = 21 = 210 = 15 = 210 His house number is 14 and the number of houses is 20 <------ Check: 20 x 21/2 = 210 and 14 x 15/2 = 105 As desired, the sum of the first 14 numbers is half the sum of all 20 on the street. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 09/30/2010 at 09:25:41 From: Doctor Jacques Subject: Re: 1+2+3+4+5... more than 20, less than 500... Hi Kevin, This is deeper than it looks. In fact, if you ignore the condition on the number of houses, there are infinitely many solutions. As Doctor Greenie wrote, we must find integer solutions to this equation: 2n(n + 1) = m(m + 1) [1] When dealing with quadratic equations, it is often a good idea to complete the squares. Use this identity: (2a + 1)^2 = 4a^2 + 4a + 1 Now multiply [1] by 4 ... 2(4n^2 + 4n) = 4m^2 + 4m ... and use the above identity to get this: 2((2n + 1)^2 - 1) = ((2m + 1)^2 - 1) Let u = 2n + 1 [2] v = 2m + 1 Then we obtain: 2(u^2 - 1) = v^2 - 1 v^2 - 2u^2 = -1 [3] There are well-known methods for solving quadratic Diophantine equations like [3]. See, for example: http://mathforum.org/library/drmath/view/66725.html http://mathforum.org/library/drmath/view/70344.html Here are the general ideas. We will use the fact that v^2 - 2u^2 = (v + u*sqrt(2))(v - sqrt(2)) Equation [3] has the obvious solution u = v = 1. To find other solutions, we look at the related equation ("Pell's equation") v^2 - 2u^2 = +1 [4] With a little trial and error (there are also more sophisticated methods), you will find that this equation has the solution u = 3, v = 2. This means that we have: (3 + 2*sqrt(2)(3 - 2*sqrt(2)) = 1 [5] Now, if (u,v) is any solution of [3] and we multiply by [5], we have (u + v*sqrt(2))(u - v*sqrt(2))(3 + 2sqrt(2)(3 - 2sqrt(2)) = -1 We can regroup the terms in this to obtain (u + v*sqrt(2))(3 + 2sqrt(2))(u - v*sqrt(2))(3 - 2sqrt(2)) = -1 We multiply together each pair of factors ... ((3u + 4v) + (2u + 3v)sqrt(2))*((3u + 4v) - (2u + 3v)*sqrt(2)) = -1 ... and, writing u' = 3u + 4v, v' = 2u + 3v: (u' + v'*sqrt(2))(u' - v'*sqrt(2)) = -1 (u')^2 - 2(v')^2 = -1 [6] This shows that (u',v') is another solution of the equation [3]; in other words, starting with any solution (u,v) we can find another solution: (u' = 3u + 4v, v' = 2u + 3v) For example, starting with the obvious solution (1,1), we get: v | u -----+----- 1 | 1 7 | 5 41 | 29 239 | 169 It is possible to prove that this procedure will give you all solutions, but this involves much deeper stuff. To get the answer to the original problem, you must retrieve m and n using the equations [2]. This means that you must only consider the solutions where u and v are both odd, but it is not difficult to show that all solutions will satisfy this condition. The first solutions in (n,m) are: 0,0 a trivial case 2,3 we have indeed 1 + 2 + 3 = 2(1 + 2) 20,14 I will let you find the next one, i.e., to satisfy the condition 20 < m < 500. Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 09/30/2010 at 17:11:27 From: Kevin Subject: Thank you (1+2+3+4+5... more than 20, less than 500...) Hi, Thanks for your help! I finally slogged through it on my own and came up with an answer I can defend. I appreciate all your advice and counsel; I may call on you again some day. Your website is terrific! Kevin |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/