Author |
Topic: Factorial Puzzle (Read 962 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Factorial Puzzle
« on: Oct 17th, 2003, 3:14pm » |
 Quote  Modify
|
a,b,c are natural numbers – or positive integers if you're towr. 
Solve each of the equations:
(i) a!b!=a!+b!
(ii) a!b!=a!+b!+c!
(iii) a!b!=a!+b!+c2
(iv) a!b!=a!+b!+2c
|
|
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Factorial Puzzle
« Reply #1 on: Oct 17th, 2003, 6:50pm » |
Quote Modify
|
(i) is simple if you notice that in the symmetry of the equation a and be could be equal
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Factorial Puzzle
« Reply #2 on: Oct 17th, 2003, 6:53pm » |
Quote Modify
|
Wait a sec, do you want us to solve for a in terms of b and c or to find three natural numbers that are a solution to the equations?
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #3 on: Oct 17th, 2003, 9:57pm » |
Quote Modify
|
He can't want the same a, b, c to satisfy all three equations. Subtracting (i) from (ii) would then give us c! = 0, which is impossible.
Doing each one individually is pretty easy. Hmm, well, this is the easy forum, isn't it.
(i) a = 2, b = 2
(ii) a = 3, b = 1, c = 2 oops! a = 3, b = 3, c = 4
(iii) a = 3, b = 2, c = 2
(iv) a = 3, b = 2, c = 2
I didn't try to check if these are unique.
----
Edited to correct silly error pointed out by Sir Col.
|
| « Last Edit: Oct 18th, 2003, 10:57pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Factorial Puzzle
« Reply #4 on: Oct 18th, 2003, 2:36am » |
Quote Modify
|
TimMann, I think you need to rethink (ii): 3!1!=6, but 3!+...>6.
on Oct 17th, 2003, 9:57pm, TimMann wrote:| I didn't try to check if these are unique. |
|
Now there's an idea. 
I suggest that you initially find a strategy to solve (i): showing that the solution you have found is both deducible, without trial and improvement, and whether or not it is unique. The same principles for (i) can certainly be applied to (ii).
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Factorial Puzzle
« Reply #5 on: Oct 18th, 2003, 9:46am » |
Quote Modify
|
on Oct 17th, 2003, 3:14pm, Sir Col wrote:| a,b,c are natural numbers – or positive integers if you're towr. |
|
Thanks for the consideration
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #6 on: Oct 18th, 2003, 10:58pm » |
Quote Modify
|
Oops, I guess I wasn't awake yet when I worked on (ii). I've corrected my answer above.
For (i), I would show uniqueness by checking the small cases and observing that a!b! must grow much faster than a!+b! with increasing a or b, so the equation can't be true for cases beyond a certain size. This method fails for (ii) and following because of the term in c on the right, which could be arbitrarily large. Obviously I'm not seeing your approach, but I'll ponder it some more.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #7 on: Oct 18th, 2003, 11:13pm » |
Quote Modify
|
All four equations can be written as
f(c) = (a! - 1)(b! - 1) - 1
in each case for a different function f, namely f1(c) = 0, f2(c) = c!, f3(c) = c2, f4(c) = 2c.
This seems like it must be progress. At least it's pretty, and it makes it easy to see that (i) is unique.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Factorial Puzzle
« Reply #8 on: Oct 19th, 2003, 11:38am » |
Quote Modify
|
A couple hints for solving (i)...
Hint 1: Begin by dividing through by b!
Hint 2: For a>1, LHS is even...
However, I do like your general approach. I certainly hadn't thought about doing it like that and I'm not sure how much mileage we can get out of it. As a![equilv]0 mod 2,3,...,a, it follows that (a!–1)[equiv]-1 mod 2,3,...,a. Hmm...
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #9 on: Feb 18th, 2005, 3:05am » |
Quote Modify
|
I see no one has shown uniqueness yet. Here's a partial solution that I'm too sleepy to finish right now. WLOG, assume a >= b. Then we can divide through by b!
(i) a! = a!/b! + 1
Here if a >= b + 2, the left side is even and the right side is odd, so there is no solution. If a = b + 1, the equation reduces to a! = a + 1, and there is again no solution. If a = b, it reduces to a! = 2, so a = b = 2. QED.
(ii) a! = a!/b! + 1 + c!/b!
Here we must have c >= b or the right side would not be an integer. If a >= b + 2 and c >= b + 2, then the left side is even and the right side is odd, so there is no solution. There are still a few cases left to work out here...
(iii) a! = a!/b! + 1 + c2/b!
Here b! must divide c2. That's not hard, though, and the quotient doesn't have to be even. So I don't know where to go next with this one...
(iv) a! = a!/b! + 1 + 2c/b!
The only factorials of positive integers that can divide a power of 2 are 1! and 2!, so there are two cases: (1) b = 1, implying a! = a! + 1 + 2c, with no solution, or (2) b = 2, implying a!/2 = 1 + 2c-1. This has the solution a = 3, c = 2, but for any larger a, the left side is even and the right odd, so it has no other solutions. QED.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #10 on: Mar 5th, 2005, 4:48pm » |
Quote Modify
|
I can finish (ii) now, though I'd like to see a shorter proof. I'll start again from the beginning here.
First, note that a > 2, since a! + b! + c! is at least 3. Now, assume WLOG that a >= b and divide through by b!. We then have:
a! = a!/b! + 1 + c!/b!
Hence c >= b, or the right side would not be an integer.
Case (ii.1), a > b and c > b. Here the left-hand side is divisible by b+1, but the right-hand side is congruent to 1 modulo b+1 since a!/b! and c!/b! are both divisible by b+1, so there are no solutions in this case.
Case (ii.2), a > b and c = b. Here we have a! = a!/b! + 2. The lhs is divisible by a, but the rhs is congruent to 2 modulo a. Since a > 2, this is a contradiction, and there are no solutions in this case.
Case (ii.3), a = b and c = b. Here we have a! = 3, which has no solution.
Case (ii.4), a = b and c > b. Here we have c > a and a! = c!/a! + 2. We know a >= 3, so the lhs is divisible by 3. If c >= a + 3, c!/a! = c(c-1)(c-2)...(a+1) has at least 3 terms and hence has one that is divisible by 3, so the rhs is not divisible by 3 and there is no solution. If c = a + 2, we have a! = (a + 2)(a + 1) + 2, or a! = a2 + 3a + 4. The lhs is divisible by a, but the rhs is not, unless a divides 4. We already know a >= 3, and a = 4 does not work either, so there are no solutions in this subcase. If c = a + 1, we have a! = a + 3, giving the one and only solution: a = 3, b = 3, c = 4.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #11 on: Mar 5th, 2005, 5:28pm » |
Quote Modify
|
The following is all bogus, as pointed out below by SirCol. Oops.
Aha! The pretty formula I found earlier actually does lead to some short solutions.
To recap, the equation in each puzzle can be rewritten as f(c) = (a! - 1)(b! - 1) - 1 for some function f. Now, if a >= 4 and b >= 4, certainly a! and b! are divisible by 4, so we can rewrite this again as f(c) = (4m - 1)(4n - 1) - 1 = 16mn - 4m - 4n - 2. So f(c) is of the form 4k - 2 for some integer k; that is, f(c) is a multiple of 2 but not of 4.
(i) f1(c) = 0, so there are no solutions with a, b >=4. Checking the nine cases with a, b <= 3 yields the unique solution given above.
(ii) f2(c) = c!, so any solution with a, b >= 4 must have c = 2 or c = 3. Checking the nine cases with a, b <= 3 and the few cases where (a! - 1)(b! - 1) - 1 <= 3! = 6 yields the unique solution.
(iii) f3(c) = c2, so there are no solutions with a, b >= 4, as a perfect square can't be of the form 4k - 2. Checking the nine cases with a, b <= 3 yields the unique solution.
(iv) f4(c) = 2c, so there can be no solution with a, b >= 4 unless c = 1. Checking the nine cases with a, b <= 3 and the few cases where (a! - 1)(b! - 1) - 1 <= 21 = 2 yields the unique solution.
|
| « Last Edit: Mar 10th, 2005, 10:11am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Factorial Puzzle
« Reply #12 on: Mar 6th, 2005, 5:40am » |
Quote Modify
|
on Mar 5th, 2005, 5:28pm, TimMann wrote:| f(c) = (4m - 1)(4n - 1) - 1 = 16mn - 4m - 4n - 2 |
|
Actually, f(c) = (4m - 1)(4n - 1) - 1 = 16mn - 4m - 4n.
Cor! I'd completely forgotten about this problem. I recall that it was (ii) that inspired me to post this collection of problems: I saw it in the British Mathematical Olympiad Round 1 paper (December 2002):
http://www.bmoc.maths.org/home/bmo1-2003.pdf
I had a look through my mountain of pieces of paper that I keep and discovered that I solved (i), (ii), and (iv) in almost the same way you did. My solution to (ii), which is a variation of the published solution, is no better than your solution; it just requires exploration of many sub-cases. However, I can't find any reference to (iii) at all. What makes matters worse is that I have no idea how I solved it?! 
I've had a go and this is as far as I've got:
From a!b! = a!+b!+c2, and W.L.O.G., assume that b<a, so that a! = a!/b!+1+c2/b! and all terms are integer.
As RHS>=3, a!>=3, which means that a>=3, and LHS is even.
In which case, exactly one of (i) a!/b! or (ii) c2/b! is odd.
(i) If a!/b! is odd then either a=b or b=a-1 (and a is odd).
If a=b, a! = 2+c2/a!, (a!)2 = 2(a!)+c2.
This can be written as ((a!)-1)2 = c2+1, which has no solution: there is no square which is one more than another square.
If b=a-1 (and a is odd), a! = a+1+c2/(a-1)!
We know that a>=3.
If a=3, b=2, and we get 6 = 4+c2/2, leading to the solution c=2: 3!2! = 3!+2!+22.
If a>3, a!==0 mod 4, but as a is odd, a=4k+1 or a=4k+3, and c2/(a-1)! must be even.
[I don't know where to go from here]
(ii) If c2/b! is odd. Clearly b cannot be greater than c.
If b=c, c2/c! must be an odd integer, which only happens when b=c=1, giving a! = a!+2: no solution.
Also c cannot be odd, unless b=1, in which case a! = a!+1+c2, and we get c2+1=0: no solution.
Hence c must be even and b<c.
I am almost certain that there are no more solutions, but I don't know how to take it any further.
In summary we have reduced the two cases above to the following:
(i) a!/b! is odd, b=a-1, a is of the form 4k+1 or 4k+3, and c2/(a-1)! is even (c must be even).
(ii) c2/b! is odd, b<c, and c is even.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #14 on: Mar 10th, 2005, 9:40am » |
Quote Modify
|
Oops. I realized as I was waking up this morning that my whole post about the (a! - 1)(b! - 1) - 1 form was based on a silly sign error. SirCol, you caught me before I could go delete it.
Just logged in to note my error. I haven't read your posts yet.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Factorial Puzzle
« Reply #16 on: Mar 10th, 2005, 9:04pm » |
Quote Modify
|
I didn't spend much time on (iii), actually -- (ii) was hard enough, and (i) and (iv) were pretty easy, so I never really got around to working much on (iii).
|
|
IP Logged |
http://tim-mann.org/
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Factorial Puzzle
« Reply #17 on: Mar 20th, 2005, 8:24am » |
Quote Modify
|
(i)) a = 2, b = 2
There are no more, as this corresponds to the only solution in positive integers to xy = x + y
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Factorial Puzzle
« Reply #18 on: Mar 20th, 2005, 9:54am » |
Quote Modify
|
on Mar 20th, 2005, 8:24am, THUDandBLUNDER wrote:(i)) a = 2, b = 2
There are no more, as this corresponds to the only solution in positive integers to xy = x + y |
|
a = 0, b = 0
0*0 = 0+0 = 0
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Factorial Puzzle
« Reply #20 on: Mar 20th, 2005, 11:18am » |
Quote Modify
|
on Mar 20th, 2005, 10:42am, Sir Col wrote:| Are you positive about that Sjoerd? |
|
0 is positive 
But the answer is right, as I saw  !
I forgot those silly '!' signs! As well as the special case: 0! = 1 !
beaten
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print