Need help with a difficult math problem

[lewelma]

DS and I are working on the 2011 camp selection problems for the NZMO summer camp, and have run across one in the junior set that we could not answer. DS needs to practice this style of problem and I can't quite figure out *what* it is - it is not algebra or number theory exactly, but something else. Something that requires logic and not straight forward algebraic manipulation (ds can manipulate factorials). So if someone can classify this problem, I will go find some more of them for us to practice.

 

Thanks!

 

Ruth in NZ

 

 

Problem:

Find all pairs of positive integers m and n such that: (m+1)! + (n+1)! = (m^2)(n^2)

 

 

Proof:

Assume that we have a solution with m<=n. Then

 

(n+1)! = (n-1)! x n x (n+1) >= n^2 (n-1)!

 

So n^2(n-1)! <= (m^2)(n^2) and hence (n-1)! <= m^2 <= n^2. But, for n>= 6, (n-1)! > n^2. So 1<=n<=5.

 

Now by trial and error we can determine that the only possibility is m=3, n=4 (or by symmetry the reverse of this pair).

[MASHomeschooler]

The class where I had things closest to this was called Discrete and Combinatorial Algebra (aka Disco), but I can’t say whether that includes this exactly – it was one class a long time ago. I also noticed a couple small things in your proof, in bold below. They don’t change the answer or narrow it down better - plus it’s been very long since I did proofs so maybe not all necessary - but I noticed them so I thought I’d mention. Feel free to ignore. Wish I could be more help.

 

 

Problem:

Find all pairs of positive integers m and n such that: (m+1)! + (n+1)! = (m^2)(n^2)

 

Proof:

Assume that we have a solution with m<=n. Then, for n > 1 [for n=1, (n+1)! = n x (n+1)],

 

(n+1)! = (n-1)! x n x (n+1) > n^2 (n-1)! (not = because n is a positive integer, not 0)

 

So n^2(n-1)! < (m^2)(n^2) and hence (n-1)! < m^2 <= n^2. But, for n>= 6, (n-1)! > n^2. So 1<n<=5.

(And then n=1 has to be handled separately, but easily, since 2 + 2 =/= 1 x 1)

[lewelma]

Thanks for the correction to the proof. We were wondering about the equal sign, so I am glad to know that we were right!

 

Disco -- I like it! But everything I looked up looks like university math! Is there a gentle introduction to this type of thinking? Something accessible to my ds who has almost finished the intro series of AoPS (alg, geo, num theo, counting). It would be great if AoPS covered it. Does anyone know if later AoPS books cover this type of problem?

 

Thanks,

 

Ruth in NZ

[MASHomeschooler]

Yeah, sorry; the class I took was in college. I enjoyed the class, but I had never/have never seen or done similar things outside that class. I am not a mathematician and my oldest is not quite to pre-algebra so I don't have any knowledge of more accessible resources. Hopefully someone who does will come along and help you. If not, one of the introductory university-level books may be accessible enough since it is something many would have no prior experience with (I really don't know, though). Good luck!

[Kathy in Richmond]

Hi Ruth!

 

Equations with 2 or more unknowns for which you're only interested in integer solutions are called Diophantine equations. They're typically found in number theory textbooks. The trouble with them is that, outside of the linear case and a few special nonlinear cases (like the Pythagorean equation x^2 + y^2 = z^2 or the Pell equation x^2 - D*y^2 = +-1), they're totally devilish and hard to approach methodically. :tongue_smilie: Which is probably why they show up on Olympian math exams quite often!

 

Do you guys have Volume 2 of the original AoPS problem solving texts? Chapter 24 is probably the best intro to Diophantine equations that I've seen for kids. Also, take a look at Chapter 7.4 of Art & Craft of Problem Solving. Both books go over an assortment of these equations & will expose your son to the general methods used to attack them. But be warned, it's a tough topic, and none of the problems you see will really resemble your sample problem. It's messy!

[lewelma]

Oh, Kathy, you are wonderful! Yes I have the 2nd book. We are currently making a list of all the things you can try on problems like this including:

 

parity

squares

primes

multiples of 3

factoring

removing pieces of the equation

divisibility theorem

inequalities

unit digits

 

I figure that he can just work through the list when he hits one of these and try them all until he develops some intuition! But I will definitely have him start the AoPS chapter right away (assuming he has the background).

 

The 2012 camp selection junior problems were much easier than the 2011 and 2010 problems. And we have become a bit discouraged as we have worked through the older exams. sniff. Here's to hoping that the 2013 exam is closer to the 2012 exam! We have 2 months to go and I am feeling the need for review. He has covered quite a bit in just 3 months! 2/3rds of the number theory book, all of the counting book (minus 3 chapters on probability), chapters 11-15 in geometry book, and Chapters 1-4 in The Art and Craft of Problem Solving, plus the 2010-2012 previous exams! And now the science fair. :willy_nilly:

[lewelma]

dp

[Kathy in Richmond]

We are currently making a list of all the things you can try on problems like this including:

 

parity

squares

primes

multiples of 3

factoring

removing pieces of the equation

divisibility theorem

inequalities

unit digits

 

I figure that he can just work through the list when he hits one of these and try them all until he develops some intuition! But I will definitely have him start the AoPS chapter right away (assuming he has the background).

 

Having a list like this is a very good way to approach these problems. It's so difficult trying to find just the right approach; it takes an element of creativity most of the time, but this gives him a concrete list to go through in his head.

 

Many of these Diophantine equations at the starter level involve something along the lines of factoring like this:

 

(1) Find all positive integer pairs (x,y) solving 1/x + 1/y = 1/15

 

The action plan involves: simplify; factor in the form (...)*(...) = integer; use prime factorization:

 

Clear fractions: 15 x + 15 y = xy

Bring all terms to one side: xy - 15x - 15 y = 0

 

We'd like to factor: (x - 15) * (y - 15), but we need an extra 225 on each side:

(x - 15)*(y - 15) = 225

 

Since x & y must be positive integers, and since 225 = 3^2 * 5^2, the left hand side must be in one of these forms:

1*225, 3*75, 5*45, 9*25, 15*15

 

then you just substitute & solve:

(x,y) = (16, 240), (18, 90), (20, 60), (24,40), (30, 30) and by symmetry also (240, 16), (90, 18), (60,20), (40, 24).

 

 

Other beginner level problems are along these lines:

 

(2) Find all positive integer pairs (x,y) solving 1! + 2! + ...+ x! = y^2 (from AoPS)

 

Try this one by making a table listing values of the left hand side for different x values. See if you can find a couple of solutions easily, and try to explain why there aren't any more.

 

The answer should be in your AoPS text, but here's a hint: If n is an integer, what unit digits can possibly appear in n^2?

 

If your ds can follow/reproduce arguments like these and also the problem you shared above, then I'd say he's made good progress!

 

The 2012 camp selection junior problems were much easier than the 2011 and 2010 problems. And we have become a bit discouraged as we have worked through the older exams. sniff. Here's to hoping that the 2013 exam is closer to the 2012 exam! We have 2 months to go and I am feeling the need for review. He has covered quite a bit in just 3 months! 2/3rds of the number theory book, all of the counting book (minus 3 chapters on probability), chapters 11-15 in geometry book, and Chapters 1-4 in The Art and Craft of Problem Solving, plus the 2010-2012 previous exams! And now the science fair. :willy_nilly:

 

You are amazing, Ruth!! Wishing good luck to your ds in both his math and science endeavors. :)

[lewelma]

Thanks Kathy for taking the time to type all that out. I will print it and show it to ds.