Author |
Topic: An Ingenious Quadratic Puzzle (Read 1245 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
An Ingenious Quadratic Puzzle
« on: Oct 23rd, 2006, 8:30am » |
 Quote  Modify
|
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.
|
| « Last Edit: Oct 23rd, 2006, 8:35am by K Sengupta » |
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #1 on: Oct 23rd, 2006, 1:29pm » |
Quote Modify
|
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 p = 27 gives exactly 2 solutions.
Haven't tried II)
|
|
IP Logged |
|
|
|
K Sengupta
Senior Riddler
Gender:
Posts: 371
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #2 on: Oct 23rd, 2006, 7:59pm » |
Quote Modify
|
On Today at 1:29pm; Aryabhatta wrote:
Quote:| I get p = 27 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 p= 27 does not seem to be the desired minimum value of p for PART I.
|
| « Last Edit: Oct 23rd, 2006, 8:08pm by K Sengupta » |
IP Logged |
|
|
|
Astrix
Newbie
Posts: 37
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #3 on: Oct 23rd, 2006, 8:41pm » |
Quote Modify
|
Sengupta, did you also notice that
5^2 - 3^2 - 1^2 = 15
|
|
IP Logged |
|
|
|
K Sengupta
Senior Riddler
Gender:
Posts: 371
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #4 on: Oct 23rd, 2006, 9:33pm » |
Quote Modify
|
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, p =15 seems to be the minimum possible positive integer value such that the given equation possesses three rather than two distinct solutions.
Accordingly , p=27 does appear to be the correct solution to PART- I.
|
| « Last Edit: Oct 23rd, 2006, 9:34pm by K Sengupta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #5 on: Oct 23rd, 2006, 11:08pm » |
Quote Modify
|
For part II) I get p = 135
[edited typo]
|
| « Last Edit: Oct 24th, 2006, 12:42am by Aryabhatta » |
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #6 on: Nov 3rd, 2006, 5:21pm » |
Quote Modify
|
Any methodology hints to get the solution?
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #7 on: Nov 7th, 2006, 11:01am » |
Quote Modify
|
on Nov 3rd, 2006, 5:21pm, 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.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #8 on: Nov 7th, 2006, 6:50pm » |
Quote Modify
|
on Nov 7th, 2006, 11:01am, 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.
|
| « Last Edit: Nov 7th, 2006, 6:56pm by Sameer » |
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #9 on: Nov 7th, 2006, 11:34pm » |
Quote Modify
|
on Nov 7th, 2006, 6:50pm, 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.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #10 on: Nov 8th, 2006, 9:36am » |
Quote Modify
|
on Nov 7th, 2006, 11:34pm, 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..
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #11 on: Nov 8th, 2006, 9:50am » |
Quote Modify
|
on Nov 7th, 2006, 6:50pm, 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?  ). 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 = qn, 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. 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #12 on: Nov 29th, 2006, 10:33am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #13 on: Nov 29th, 2006, 1:13pm » |
Quote Modify
|
I would love to see the calculations/conclusions you used to work out the answer
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: An Ingenious Quadratic Puzzle
« Reply #14 on: Nov 30th, 2006, 11:10am » |
Quote Modify
|
on Nov 29th, 2006, 1:13pm, 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...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print