wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Factorial Puzzle
        
(Message started by: Sir Col on Oct 17^th, 2003, 3:14pm)

Title: Factorial Puzzle
Post by Sir Col on Oct 17^th, 2003, 3:14pm

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!+c²
(iv) a!b!=a!+b!+2^c

Title: Re: Factorial Puzzle
Post by aero_guy on Oct 17^th, 2003, 6:50pm

(i) is simple if you [hide]notice that in the symmetry of the equation a and be could be equal[/hide]

Title: Re: Factorial Puzzle
Post by aero_guy on Oct 17^th, 2003, 6:53pm

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?

Title: Re: Factorial Puzzle
Post by TimMann on Oct 17^th, 2003, 9:57pm

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) [hide]a = 2, b = 2[/hide]

(ii) [hide]~~a = 3, b = 1, c = 2~~ oops! a = 3, b = 3, c = 4[/hide]

(iii) [hide]a = 3, b = 2, c = 2[/hide]

(iv) [hide]a = 3, b = 2, c = 2[/hide]

I didn't try to check if these are unique.
----
Edited to correct silly error pointed out by Sir Col.

Title: Re: Factorial Puzzle
Post by Sir Col on Oct 18^th, 2003, 2:36am

TimMann, I think you need to rethink (ii): 3!1!=6, but 3!+...>6.

on 10/17/03 at 21:57:39, 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).

Title: Re: Factorial Puzzle
Post by towr on Oct 18^th, 2003, 9:46am

on 10/17/03 at 15:14:49, Sir Col wrote:

a,b,c are natural numbers – or positive integers if you're towr. ;)

Thanks for the consideration ;)

Title: Re: Factorial Puzzle
Post by TimMann on Oct 18^th, 2003, 10:58pm

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.

Title: Re: Factorial Puzzle
Post by TimMann on Oct 18^th, 2003, 11:13pm

All four equations can be written as

f(c) = (a! - 1)(b! - 1) - 1

in each case for a different function f, namely f₁(c) = 0, f₂(c) = c!, f₃(c) = c², f₄(c) = 2^c.

This seems like it must be progress. At least it's pretty, and it makes it easy to see that (i) is unique.

Title: Re: Factorial Puzzle
Post by Sir Col on Oct 19^th, 2003, 11:38am

A couple hints for solving (i)...
Hint 1: [hide]Begin by dividing through by b![/hide]
Hint 2: [hide]For a>1, LHS is even...[/hide]

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...

Title: Re: Factorial Puzzle
Post by TimMann on Feb 18^th, 2005, 3:05am

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 + c²/b!

Here b! must divide c². 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 + 2^c/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 + 2^c, with no solution, or (2) b = 2, implying a!/2 = 1 + 2^c-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.

Title: Re: Factorial Puzzle
Post by TimMann on Mar 5^th, 2005, 4:48pm

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! = a² + 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.

Title: Re: Factorial Puzzle
Post by TimMann on Mar 5^th, 2005, 5:28pm

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) f₁(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) f₂(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) f₃(c) = c², 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) f₄(c) = 2^c, 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 <= 2¹ = 2 yields the unique solution.

Title: Re: Factorial Puzzle
Post by Sir Col on Mar 6^th, 2005, 5:40am

on 03/05/05 at 17:28:23, 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!+c², and W.L.O.G., assume that b<a, so that a! = a!/b!+1+c²/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) c²/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+c²/a!, (a!)² = 2(a!)+c².
This can be written as ((a!)-1)² = c²+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+c²/(a-1)!
We know that a>=3.
If a=3, b=2, and we get 6 = 4+c²/2, leading to the solution c=2: 3!2! = 3!+2!+2².
If a>3, a!==0 mod 4, but as a is odd, a=4k+1 or a=4k+3, and c²/(a-1)! must be even.
[I don't know where to go from here]

(ii) If c²/b! is odd. Clearly b cannot be greater than c.
If b=c, c²/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+c², and we get c²+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 c²/(a-1)! is even (c must be even).
(ii) c²/b! is odd, b<c, and c is even.

Title: Re: Factorial Puzzle
Post by Sir Col on Mar 9^th, 2005, 12:08pm

If you're interested, I've uploaded my solutions to (i), (ii), and (iv) on my website. Any comments are welcomed.

a!b! = a! + b! (http://mathschallenge.net/index.php?section=problems&show=true&titleid=factorial_symmetry&full=true#solution)

a!b! = a! + b! + c! (http://mathschallenge.net/index.php?section=problems&show=true&titleid=factorial_equation&full=true#solution)

a!b! = a! + b! + 2^c (http://mathschallenge.net/index.php?section=problems&show=true&titleid=factorial_and_power_of_2&full=true#solution)

Title: Re: Factorial Puzzle
Post by TimMann on Mar 10^th, 2005, 9:40am

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.

Title: Re: Factorial Puzzle
Post by Sir Col on Mar 10^th, 2005, 10:39am

I'm sorry about (iii), TimMann, and all the time that you may have spent on it. (I hope you enjoyed the others though.)

As this thread has been read by a good number, and it's been here since October 2003, it seems that no one has had any better ideas on how to solve (iii), so I've started a fresh topic in the Hard section for it.
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1110472380

Title: Re: Factorial Puzzle
Post by TimMann on Mar 10^th, 2005, 9:04pm

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).

Title: Re: Factorial Puzzle
Post by THUDandBLUNDER on Mar 20^th, 2005, 8:24am

(i)) a = 2, b = 2
There are no more, as this corresponds to the only solution in positive integers to xy = x + y

Title: Re: Factorial Puzzle
Post by Sjoerd Job Postmus on Mar 20^th, 2005, 9:54am

on 03/20/05 at 08:24:10, 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

Title: Re: Factorial Puzzle
Post by Sir Col on Mar 20^th, 2005, 10:42am

Are you positive about that Sjoerd? ;)

Title: Re: Factorial Puzzle
Post by Sjoerd Job Postmus on Mar 20^th, 2005, 11:18am

on 03/20/05 at 10:42:11, Sir Col wrote:

Are you positive about that Sjoerd? ;)

0 is positive :P

But the answer is right, as I saw :(!

I forgot those silly '!' signs! As well as the special case: 0! = 1 :(!

beaten :(