from apmc

For discussing Olympiad Level Number Theory problems
the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

from apmc

Unread post by the arrivals » Sat Jan 15, 2011 10:01 pm

find triples (p,q,n) with p,q primes and n an integer which is greater or equal 1
satisfying the awkward( :evil: ) relation
p(p+1)+q(q+1)=n(n+1)
the arrivals
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: from apmc

Unread post by Moon » Sat Jan 15, 2011 11:13 pm

Nice problem:
Hint (I'll post complete solution later)
Use some inequalities to impose some bounds. You should get $(p,q)=(5,3)$.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

Re: from apmc

Unread post by Avik Roy » Sun Jan 16, 2011 12:14 am

Some basic number theory also performs well :)
Try with $q(q+1) = (n-p)(n+p+1)$
and don't forget: q is a PRIME
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

Re: from apmc

Unread post by the arrivals » Sun Jan 16, 2011 8:07 am

(2,2,3) perhaps a solution also. :idea:
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: from apmc

Unread post by Moon » Sun Jan 16, 2011 1:16 pm

Yup...the solutions are $(p,q,n)=(2,2,3),(5,3,6)$.

Case 1: $p=q$
We have $2p(p+1)=n(n+1)$.

Case 1(a): $p | n$
So, $n \geq 2p \iff n+2 \geq 2(p+1)$ ($n=p$ is not possible). We also have $2(p+1)=k(n+1)$. So, $k(n+1) \leq n+2$. Checking some values of $k$ we can see that this case is not possible.

Case 1(b): $p |(n+1)$
So, $(n+1) \geq 2p \iff n+3 \geq 2(p+1)=kn \iff (k-1)n \leq 3 $. Only $k=1$ is possible. We have $(p,q,n)=(2,2,3)$.

Case 2: $p >q$
The equation rearranges to $p(p+1)=(n-q)(n+q+1)$.

Case 2(a): $p | (n-q)$
Then $ p \leq (n-q) \iff p+1 \leq n-q+1 < n+q+1$. Contradiction!

Case 2(b): $p | (n+q+1)$
As $n-q< n+q+1$, $n+q+1 \geq 2p$. Then we have $n-q <p \iff n+q+1 <p+2q+1 <3p$.

Finally we have $3p>n+q+1 \geq 2p \iff n+q+1=2p$. So, $2(n-q)=p+1$. From these two equalities we have $3n-5q=3$. So $3 |q$ and recall that $q$ is a prime. So $q=3$. From the equalities we also have $4q+3=3p$; so, $p=5$.
We are done! :D

Remark: When writing more official solution you can not just write, "it is easy to check that..." you must complete write how to check as well.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

Re: from apmc

Unread post by Avik Roy » Mon Jan 17, 2011 12:33 pm

I just got a combinatorial proof of the problem :D
The given relation can be written as: \[\begin{pmatrix}
n+1\\2

\end{pmatrix} = \begin{pmatrix}
p+1\\2

\end{pmatrix} +\begin{pmatrix}
q+1\\2

\end{pmatrix}\]
Now, since $p<n$, lets consider that we choose $n-p$ elements from available $n+1$ elements and keep them aside in choosing elements. So we have $p+1$ elements to choose from. In the following cases, we choose elements from the kept aside $n-p$ elements in all possible combinations to keep or not to keep them in our selection to complete the quota. However, we have only $2$ elements to select, so $n-p$ can't exceed $2$. Choosing $n-p=2$, we have the following equation to satisfy:$\begin{pmatrix}
p+1\\2

\end{pmatrix}+2\begin{pmatrix}
p+1\\1

\end{pmatrix}+1=\begin{pmatrix}
n+1\\2
\end{pmatrix}$
and putting $n=p+2$ here leads one to complete gibberish. Hence $n=p+1$ is to satisfy. Comaring the given equation with the identity: \[\begin{pmatrix}
n+1\\r

\end{pmatrix} = \begin{pmatrix}
n\\r

\end{pmatrix} +\begin{pmatrix}
n\\r-1

\end{pmatrix}\]
we hereby obtain
$\begin{pmatrix} q+1\\2 \end{pmatrix} = \begin{pmatrix} p+1\\1 \end{pmatrix}$
$\Rightarrow q(q+1) = 2(p+1)$
Now, we have to consider the following cases-
C1: $q=2$ which leads to the solution $(2,2,3)$
C2: $q|p+1$ implying the following set of equations:
$p+1 = kq$
$q+1 = k.2$
Adding them we receive-
$p+q+2 = k(q+2)$
$\Rightarrow k = 1 + \frac {p}{q+2}$
since $p$ is a prime $p=q+2$ and $k=2$
This leads us to the solution $(5,3,6)$
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

Re: from apmc

Unread post by the arrivals » Mon Jan 17, 2011 12:36 pm

oow!! awesome!! what make you approching like this?? very cool instead.appreciating.
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

User avatar
Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

Re: from apmc

Unread post by Avik Roy » Mon Jan 17, 2011 12:45 pm

@the arrivals, whom did you address??
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: from apmc

Unread post by Moon » Mon Jan 17, 2011 12:46 pm

The approach is really unorthodox and cool! :ugeek:
However, to me these explanations are not clear.
Avik Roy wrote:Now, since $p<n$, lets consider that we choose $n-p$ elements from available $n+1$ elements and keep them aside in choosing elements. So we have $p+1$ elements to choose from. In the following cases, we choose elements from the kept aside $n-p$ elements in all possible combinations to keep or not to keep them in our selection to complete the quota. However, we have only $2$ elements to select, so $n-p$ can't exceed $2$. Choosing $n-p=2$
BTW you need not use \pmatrix, you may use \binom or \dbinom
I mean $\dbinom{n+1}{2}$
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

Re: from apmc

Unread post by the arrivals » Mon Jan 17, 2011 5:33 pm

nobody just myself @avik roy ;)
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

Post Reply