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