wu :: forums
wu :: forums - Triangular Numbers

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 3:52pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: william wu, SMQ, towr, Eigenray, Icarus, Grimbal)
   Triangular Numbers
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Triangular Numbers  (Read 942 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Triangular Numbers  
« on: Sep 21st, 2002, 8:57am »
Quote Quote Modify 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
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: TRIANGULAR NUMBERS  
« Reply #1 on: Oct 11th, 2002, 10:38pm »
Quote Quote Modify 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.
 
 Embarassed
IP Logged

http://tim-mann.org/
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: NEW PROBLEM: TRIANGULAR NUMBERS  
« Reply #2 on: Oct 13th, 2002, 9:17am »
Quote Quote Modify 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! Smiley
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
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: TRIANGULAR NUMBERS  
« Reply #3 on: Oct 15th, 2002, 12:43am »
Quote Quote Modify 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
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: NEW PROBLEM: TRIANGULAR NUMBERS  
« Reply #4 on: Oct 15th, 2002, 7:38pm »
Quote Quote Modify Modify

  Good work! Exact same way I did it, though I suspect I was stuck longer... Smiley 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
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: TRIANGULAR NUMBERS  
« Reply #5 on: Oct 15th, 2002, 11:56pm »
Quote Quote Modify 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
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: TRIANGULAR NUMBERS  
« Reply #6 on: Oct 16th, 2002, 12:32am »
Quote Quote Modify 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/
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board