wu :: forums - Print Page


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

        riddles >> easy >> An Ingenious Quadratic Puzzle
        
(Message started by: K Sengupta on Oct 23^rd, 2006, 8:30am)

Title: An Ingenious Quadratic Puzzle
Post by K Sengupta on Oct 23^rd, 2006, 8:30am

Consider three positive whole numbers x, y and z in arithmetic sequence with :
x< y< z.

Given that p is a positive whole number;

(I) Determine the minimum possible value of p such that the equation :
z^2 – x^2 – y^2 = p possesses precisely two distinct solutions.

(II) Determine the minimum possible value of p such that the equation :
z^2 – x^2 – y^2 = p possesses precisely five distinct solutions.

Title: Re: An Ingenious Quadratic Puzzle
Post by Aryabhatta on Oct 23^rd, 2006, 1:29pm

Set x = s, y = s+t, z = s+2t

Then we get

(3t-s)(s+t) = p

So we are looking for factorizations of p, p = ab, such that a+b is divisible by 4.
(Each such factorization gives either 1 or 2 solutions depending on where 3a > b and 3b > a)

For I) I get [hide] p = 27 [/hide] gives exactly 2 solutions.

Haven't tried II)

Title: Re: An Ingenious Quadratic Puzzle
Post by K Sengupta on Oct 23^rd, 2006, 7:59pm

On Today at 1:29pm; Aryabhatta wrote:

Quote:

I get [hide]p = 27 [/hide]gives exactly 2 solutions

I am confused. I cannot find any discrepancy in your proceedure.

However, I have observed that:

19^2 - 15^2 - 11^2
= 7^2 - 5^2 - 3^2
= 15

Accordingly, IMHO [hide]p= 27 [/hide] does not seem to be the desired minimum value of p for PART I.

Title: Re: An Ingenious Quadratic Puzzle
Post by Astrix on Oct 23^rd, 2006, 8:41pm

Sengupta, did you also notice that
5^2 - 3^2 - 1^2 = 15

Title: Re: An Ingenious Quadratic Puzzle
Post by K Sengupta on Oct 23^rd, 2006, 9:33pm

On Today at 8:41pm; Astrix wrote:

Quote:

...did you also notice that
5^2 - 3^2 - 1^2 = 15

I stand corrected. In view of your comment, [hide]p =15[/hide] seems to be the minimum possible positive integer value such that the given equation possesses three rather than two distinct solutions.

Accordingly , [hide]p=27[/hide] does appear to be the correct solution to PART- I.

Title: Re: An Ingenious Quadratic Puzzle
Post by Aryabhatta on Oct 23^rd, 2006, 11:08pm

For part II) I get [hide] p = 135 [/hide]

[edited typo]

Title: Re: An Ingenious Quadratic Puzzle
Post by Sameer on Nov 3^rd, 2006, 5:21pm

Any methodology hints to get the solution?

Title: Re: An Ingenious Quadratic Puzzle
Post by Barukh on Nov 7^th, 2006, 11:01am

on 11/03/06 at 17:21:35, Sameer wrote:

Any methodology hints to get the solution?

1. Consider the odd p's.

2. The sum of the exponents of the prime divisors of p that are of the form 4k+3 is odd.

3. If the required number of solutions is M, search for p that has 2(M-1) divisors.

Title: Re: An Ingenious Quadratic Puzzle
Post by Sameer on Nov 7^th, 2006, 6:50pm

on 11/07/06 at 11:01:56, Barukh wrote:

1. Consider the odd p's.

2. The sum of the exponents of the prime divisors of p that are of the form 4k+3 is odd.

3. If the required number of solutions is M, search for p that has 2(M-1) divisors.

How did you come to that conclusion?

Also for point 3. do you mean divisors besides 1 and p?

Here's how I started. Take values x,y,z as
a-t, a, a+t

Thus the equation reduces to 4at - a^2 =p or
a^2 - 4at + p =0.

Now I went through some calculations and reached p =15 which was a wrong answer as you get the value of p for a certain t, but there exists another t that produces a third solution.

Just looking at the equation for quadratice decomposition of middle term we can see that it cannot be decomposed into -at - 3at and -2at - 2at

So based on this equation, I don't know how to connect your hints or I am missing something really basic and also can't apply the same logic of decomposition for 5 solutions.

???

Title: Re: An Ingenious Quadratic Puzzle
Post by Barukh on Nov 7^th, 2006, 11:34pm

on 11/07/06 at 18:50:14, Sameer wrote:

How did you come to that conclusion?

I looked at the formula derived by Aryabhatta. Consider values a, b modulo 4.

Quote:

Also for point 3. do you mean divisors besides 1 and p?

No. All divisors.

Sameer, please forgive me: it's late here in California, and I am still struggling through the jet-leg. So, let's postpone the explanation til tomorrow.

Title: Re: An Ingenious Quadratic Puzzle
Post by Sameer on Nov 8^th, 2006, 9:36am

on 11/07/06 at 23:34:29, Barukh wrote:

Sameer, please forgive me: it's late here in California, and I am still struggling through the jet-leg. So, let's postpone the explanation til tomorrow.

Thanks for the hints... you didn't have to reply straight away!! :) This has been posted for a while so I can wait... it will definitely take me some days to digest this..

Title: Re: An Ingenious Quadratic Puzzle
Post by Barukh on Nov 8^th, 2006, 9:50am

on 11/07/06 at 18:50:14, Sameer wrote:

How did you come to that conclusion?

I looked at the Aryabhatta’s factorization for p: (3t-s)(t+s) = ab = p. For this to yield integer solution, both a+b and 3b-a should be divisible by 4. It is easy to see that this is accomplished for the following cases:

1. ab = -1 mod 4
2. a = b = 2k mod 4

The first case simply means p = -1 mod 4, which means the number of prime divisors contributing -1 mod 4 should be odd. This also means that p cannot be a perfect square, and therefore it has an even number D of divisors (including 1 and p).

Next: every factorization p = ab s.t. 3b > a, will certainly yield a solution in positive integers. Because there are exactly D/2 factorizations where b > a, there are at least D/2 solutions.

What follows next, is rather a “methodology”, and not an algorithm (but that’s what you asked for, right? ;D). It may happen that there will be more solutions satisfying 3b > a. I added as a rule of thumb one more solution (getting the 3-rd rule). This doesn’t work always, though: if p = qⁿ, there will be exactly (n+1)/2 solutions (as in our case with 2 solutions). I am not sure if there may be two or more solutions with b < a, but 3b > a.

I leave to you the analysis of the second case as an exercise. ;)

Title: Re: An Ingenious Quadratic Puzzle
Post by Aryabhatta on Nov 29^th, 2006, 10:33am

All I did was take a multiple of 4. split it as a+b and then consider other factoizations of p = ab. Laborious, but easily done by a computer :-D

For the first part, it is easily done by hand. For the second part, it can be done by hand in around 15-20 minutes (given the nature of the solution)

Title: Re: An Ingenious Quadratic Puzzle
Post by Sameer on Nov 29^th, 2006, 1:13pm

I would love to see the calculations/conclusions you used to work out the answer

Title: Re: An Ingenious Quadratic Puzzle
Post by Aryabhatta on Nov 30^th, 2006, 11:10am

on 11/29/06 at 13:13:54, Sameer wrote:

I would love to see the calculations/conclusions you used to work out the answer

If x = s, y = s+t, and z = s+2t

then (3t-s)(t+s) = ab = p. This gives rise to two set of equations:

3t-s = a
t+s = b

and

3t-s = b
t+s = a

If there is a solution then a+b must be divisible by 4. Also, for any factorization of p = mn such that m+n is divisible by 4, there is at least one solution. If 3m > n and 3n > m and m <> n then there are exactly two solutions. Otherwise there is exactly one solution.

Thus by looking at the factorizations of p, we pick the factors which sum to 4. For each such pair, we get either 1 or 2 solutions depending on whether 3*smaller > greater. If the factors are equal then there is only one solution.

For the part I) exactly 2 solutions...

Consider a+b =4
1,3 => p = 3 , 1x3 which gives only 1 solution.
2,2 => p =4 1x4, 2x2 which gives only 1 solution.

Consider a+b = 8
1,7 => p = 7 one solution.
2,6 => p = 12, 1x12, 2x6, 3x4, of which only 2x6 is relevant => 1 solution (as 3*2 <= 6)
3,5 => p = 15, 1x15, 3x5 => 1x15 gives one solution while 3x5 gives two solutions (as 3*3 > 5). Total 3.
4,4 => p=16, 1x16, 2x8, 4x4. Only 4x4 is relavant and this gives exactly one solution.

Consider a+b = 12
1+11 => p = 11, one solution
2+10 => p = 20 = 1x20, 2x10,4x5 only 2x10 is relevant, gives one solution.
3+9 => p = 27, 1x27, 3x9 => exactly two solutions.
No need to consider anything else for a+b = 12 as the resulting p will be higher than 27.

We still have to consider others
a+b=16
1+15 (no need to consider 2+14 etc as p > 27)
p = 15 , 3 solutions
a+b = 20
(1+19)
p = 19, 1 solution
a+b = 24
(1+23)
p = 23, one solution.

So p = 27 is smallest such that there are exactly two solutions.

for the other, I just wrote a program. There might be easier ways to do it by hand...