wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Triangular Numbers
        
(Message started by: Pietro K.C. on Sep 21^st, 2002, 8:57am)

Title: Triangular Numbers
Post by Pietro K.C. on Sep 21^st, 2002, 8:57am

Here's a good one: prove that there is an infinite number of distinct ordered pairs (m, n) of integers such that, for every positive integer t, the number mt + n is a triangular number if and only if t is one as well. For instance, the pair (1, 0) trivially satisfies the requirement, because 1*t + 0 = t is a triangular number if and only if t is.

Title: Re: NEW PROBLEM: TRIANGULAR NUMBERS
Post by TimMann on Oct 11^th, 2002, 10:38pm

Just so you know your problem is generating interest, I've been thinking about it, but haven't made much progress. In fact, I haven't found even one such pair other than 1,0. I spent some time wondering if the problem was misstated and trying to prove that there are none, but didn't manage that either.

:-[

Title: Re: NEW PROBLEM: TRIANGULAR NUMBERS
Post by Pietro K.C. on Oct 13^th, 2002, 9:17am

No, it's quite right. I got it from the Putnam archive which Yournamehere pointed out. I printed out the exams and leafed through them, and found this one interesting. Good luck! :)

Title: Re: NEW PROBLEM: TRIANGULAR NUMBERS
Post by TimMann on Oct 15^th, 2002, 12:43am

Hmm, not sure why I was stuck on this one for so long. It doesn't seem so hard now that I've solved it.

The ith triangular number t(i) = (i² + i)/2.

If mt(i) + n is triangular, then it equals t(j) for some j depending on i. Let j = f(i); then mt(i) + n = t(f(i)). Expanding, we have (m/2)i² + (m/2)i + n = f(i)²/2 + f(i)/2.

Since the left hand side is a 2nd degree polynomial in i, and the rhs has a term in f(i)², it seems at least a good guess that we'll find solutions by assuming f(i) is a linear polynomial in i, so let's guess that f(i) = pi + q for some integers p, q. Expanding again, we have (m/2)i² + (m/2)i + n = (pi + q)²/2 + (pi + q)/2 = (p²/2)i² + (pq + p/2)i + (q² + q)/2.

Setting the coefficients of corresponding powers of i equal, we have

m = p²
m = 2pq + p
n = (q² + q)/2

Combining the first two and cancelling a p, we have p = 2q + 1.

So for any q >= 0, choosing m = (2q + 1)² and n = (q² + q)/2 will work. For example, m=9, n=1 works.

Title: Re: NEW PROBLEM: TRIANGULAR NUMBERS
Post by Pietro K.C. on Oct 15^th, 2002, 7:38pm

Good work! Exact same way I did it, though I suspect I was stuck longer... :) Unfortunately, I succeeded, right away, in proving that relations of the type f(i) = C*i for constant C could never lead to a solution, except for C = 1. This sort of misled me for a good while.

As a side point, plugging our answer of m = (2q+1)², n = (q²+q)/2 into the formula mt + n, we can see that, for t = (j²+j)/2 (i.e. triangular), we have:

mt + n = (2q+1)²(j²+j)/2 + (q²+q)/2 =

(2qj+q+j)(2qj+q+j+1)/2 (i.e. triangular).

However, I'm not too sure if we proved the reverse implication: if mt+n is triangular, then so is t. This shouldn't be too hard. I'll give it some more thought at home.

Title: Re: NEW PROBLEM: TRIANGULAR NUMBERS
Post by TimMann on Oct 15^th, 2002, 11:56pm

Yes, as you verified, the if part of the theorem follows by the way m and n are constructed from p and q. But I wasn't sure when I posted whether I'd presented enough to make the only-if part of the theorem trivial to finish off. It was another case of "post what you've got and go to bed." Right now I'm thinking the only-if part still needs a proof.

I think the lemma we need to prove this direction is as follows: Consider the function t^-1(u), obtained by extending the domain of t(i) to the positive reals and taking its inverse. If u is an integer that is not triangular, then t^-1(u) is irrational.

This lemma is similar to the well-known theorem that the nth root of an integer that is not a perfect nth power is irrational. I'm not seeing how to prove the lemma right now, though.

Why does this help? The last equation in your post can be written out even if t is not triangular. If the lemma is true, this makes j irrational. Because mt + n is purported to be triangular, t^-1(mt + n) = 2qj + q + j has to be an integer. But it can't be, because j is irrational and q is an integer.

Title: Re: NEW PROBLEM: TRIANGULAR NUMBERS
Post by TimMann on Oct 16^th, 2002, 12:32am

Oh, OK, the lemma is easy to prove.

Let t^-1(u) = a/b, with u, a, b integers and a/b in lowest terms; i.e., a and b have no common factor.

Then 2u = a²/b² + a/b,
and 2ub - a = a²/b.

The LHS is an integer, so the RHS must be too. Therefore b divides a². But if b divides a², and a and b have no common factor, then b = 1. (If you don't see that instantly, you can hit it with my favorite hammer, the unique factorization theorem.)

So if t^-1(u) is rational, it is an integer; i.e., if it is not an integer, it is irrational.