Author |
Topic: Triangular Numbers (Read 970 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Triangular Numbers
« on: Sep 21st, 2002, 8:57am » |
 Quote  Modify
|
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.
|
| « Last Edit: Nov 7th, 2002, 8:50am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: TRIANGULAR NUMBERS
« Reply #1 on: Oct 11th, 2002, 10:38pm » |
Quote Modify
|
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PROBLEM: TRIANGULAR NUMBERS
« Reply #2 on: Oct 13th, 2002, 9:17am » |
Quote Modify
|
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! 
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: TRIANGULAR NUMBERS
« Reply #3 on: Oct 15th, 2002, 12:43am » |
Quote Modify
|
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) = (i2 + 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)i2 + (m/2)i + n = f(i)2/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)2, 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)i2 + (m/2)i + n = (pi + q)2/2 + (pi + q)/2 = (p2/2)i2 + (pq + p/2)i + (q2 + q)/2.
Setting the coefficients of corresponding powers of i equal, we have
m = p2
m = 2pq + p
n = (q2 + q)/2
Combining the first two and cancelling a p, we have p = 2q + 1.
So for any q >= 0, choosing m = (2q + 1)2 and n = (q2 + q)/2 will work. For example, m=9, n=1 works.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PROBLEM: TRIANGULAR NUMBERS
« Reply #4 on: Oct 15th, 2002, 7:38pm » |
Quote Modify
|
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)2, n = (q2+q)/2 into the formula mt + n, we can see that, for t = (j2+j)/2 (i.e. triangular), we have:
mt + n = (2q+1)2(j2+j)/2 + (q2+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.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: TRIANGULAR NUMBERS
« Reply #5 on: Oct 15th, 2002, 11:56pm » |
Quote Modify
|
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: TRIANGULAR NUMBERS
« Reply #6 on: Oct 16th, 2002, 12:32am » |
Quote Modify
|
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 = a2/b2 + a/b,
and 2ub - a = a2/b.
The LHS is an integer, so the RHS must be too. Therefore b divides a2. But if b divides a2, 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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print