wu :: forums « wu :: forums - Triangular Numbers » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 3:52pm RIDDLES SITE WRITE MATH! Home Help Search Members Login 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 Notify of replies Send Topic Print
 Author Topic: Triangular Numbers  (Read 942 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/
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »