Difference between revisions of "1991 OIM Problems/Problem 5"

Latest revision as of 08:41, 23 December 2023

Problem

Let $P(x,y) = 2x^2 - 6xy + 5y^2$ . We will say that an integer $a$ is a value of $P$ if there exist integers $b$ and $c$ such that $a=P(b,c)$ .

i. Determine how many elements of {1, 2, 3, ... ,100} are values of $P$ .

ii. Prove that the product of values of $P$ is a value of $P$ .

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

Part i.

Let $x$ , $y$ , $P$ be integers

$2x^2 - 6xy + 5y^2-P=0$ , then solving for $x$ using the quadratic equation we have:

$x=\frac{3y \pm \sqrt{2P-y^2}}{2}$

Let $K$ be an integer and $K^2=2P-y^2$ . Therefore, $P=\frac{K^2+y^2}{2}$ Since $1 \le P \le 100$ , then $0 \le K \le 14$ , $-14 \le y \le 14$ because $15^2/2>100$

Since $(-y)^2=y^2$ we can look at the combinations of $y$ with $K$ for non-negative values. So, we can use: $0 \le y \le 14$ to find the values of $P$

Since $x=\frac{3y \pm K}{2}$ , $P=\frac{K^2+y^2}{2}$ , then to get integers $x$ and $P$ , both expressions $K^2+y^2$ and $3y \pm K$ need to be even. This happens when either $K$ and $y$ are both odd, or both even. Thus we will try both cases:

Case 1: Both $K$ and $y$ are even.

Let $K=2n$ , $y=2m$ where integers $n$ and $m$ with $0 \le n \le 7$ and $0 \le m \le 7$

$P=\frac{K^2+y^2}{2}=\frac{4n^2+4m^2}{2}=2(n^2+m^2)$

Now we try the possible combinations of $n$ and $m$ :

$\begin{cases} m=0\text{; }n=0\text{; }P=2(0^2+0^2)=0; & \text{NO}\\ m=0\text{; }n=1\text{; }P=2(0^2+1^2)=2; & \text{YES}\\ m=0\text{; }n=2\text{; }P=2(0^2+2^2)=8; & \text{YES}\\ m=0\text{; }n=3\text{; }P=2(0^2+3^2)=18; & \text{YES}\\ m=0\text{; }n=4\text{; }P=2(0^2+4^2)=32; & \text{YES}\\ m=0\text{; }n=5\text{; }P=2(0^2+5^2)=50; & \text{YES}\\ m=0\text{; }n=6\text{; }P=2(0^2+6^2)=72; & \text{YES}\\ m=0\text{; }n=7\text{; }P=2(0^2+7^2)=98; & \text{YES}\\ m=1\text{; }n=1\text{; }P=2(1^2+1^2)=4; & \text{YES}\\ m=1\text{; }n=2\text{; }P=2(1^2+2^2)=10; & \text{YES}\\ m=1\text{; }n=3\text{; }P=2(1^2+3^2)=20; & \text{YES}\\ m=1\text{; }n=4\text{; }P=2(1^2+4^2)=34; & \text{YES}\\ m=1\text{; }n=5\text{; }P=2(1^2+5^2)=52; & \text{YES}\\ m=1\text{; }n=6\text{; }P=2(1^2+6^2)=74; & \text{YES}\\ m=1\text{; }n=7\text{; }P=2(1^2+7^2)=100; & \text{YES}\\ m=2\text{; }n=2\text{; }P=2(2^2+2^2)=16; & \text{YES}\\ m=2\text{; }n=3\text{; }P=2(2^2+3^2)=26; & \text{YES}\\ m=2\text{; }n=4\text{; }P=2(2^2+4^2)=40; & \text{YES}\\ m=2\text{; }n=5\text{; }P=2(2^2+5^2)=58; & \text{YES}\\ m=2\text{; }n=6\text{; }P=2(2^2+6^2)=80; & \text{YES}\\ m=2\text{; }n=7\text{; }P=2(2^2+7^2)=106; & \text{NO}\\ m=3\text{; }n=3\text{; }P=2(3^2+3^2)=36; & \text{YES}\\ m=3\text{; }n=4\text{; }P=2(3^2+4^2)=50; & \text{YES}\\ m=3\text{; }n=5\text{; }P=2(3^2+5^2)=68; & \text{YES}\\ m=3\text{; }n=6\text{; }P=2(3^2+6^2)=90; & \text{YES}\\ m=3\text{; }n=7\text{; }P=2(3^2+7^2)=116; & \text{NO}\\ m=4\text{; }n=4\text{; }P=2(4^2+4^2)=64; & \text{YES}\\ m=4\text{; }n=5\text{; }P=2(4^2+5^2)=82; & \text{YES}\\ m=4\text{; }n=6\text{; }P=2(4^2+6^2)=104; & \text{NO}\\ m=4\text{; }n=7\text{; }P=2(4^2+7^2)=130; & \text{NO}\\ m=5\text{; }n=5\text{; }P=2(5^2+5^2)=100; & \text{YES}\\ m=5\text{; }n=6\text{; }P=2(5^2+6^2)=122; & \text{NO}\\ m=5\text{; }n=7\text{; }P=2(5^2+7^2)=148; & \text{NO}\\ m=6\text{; }n=6\text{; }P=2(6^2+6^2)=144; & \text{NO}\\ m=6\text{; }n=7\text{; }P=2(6^2+7^2)=170; & \text{NO}\\ m=7\text{; }n=7\text{; }P=2(7^2+7^2)=196; & \text{NO} \end{cases}$

Case 2: Both $K$ and $y$ are odd.

Let $K=2n+1$ , $y=2m+1$ where integers $n$ and $m$ with $0 \le n \le 7$ and $0 \le m \le 7$

$P=\frac{K^2+y^2}{2}=\frac{4n^2+4m^2+4n+4n+2}{2}=2(n^2+m^2)+2(n+m)+1$

Now we try the possible combinations of $n$ and $m$ :

$\begin{cases} m=0\text{; }n=0\text{; }P=2(0^2+0^2)+2(0+0)+1=1; & \text{YES}\\ m=0\text{; }n=1\text{; }P=2(0^2+1^2)+2(0+1)+1=5; & \text{YES}\\ m=0\text{; }n=2\text{; }P=2(0^2+2^2)+2(0+2)+1=13; & \text{YES}\\ m=0\text{; }n=3\text{; }P=2(0^2+3^2)+2(0+3)+1=25; & \text{YES}\\ m=0\text{; }n=4\text{; }P=2(0^2+4^2)+2(0+4)+1=41; & \text{YES}\\ m=0\text{; }n=5\text{; }P=2(0^2+5^2)+2(0+5)+1=61; & \text{YES}\\ m=0\text{; }n=6\text{; }P=2(0^2+6^2)+2(0+6)+1=85; & \text{YES}\\ m=0\text{; }n=7\text{; }P=2(0^2+7^2)+2(0+7)+1=113; & \text{NO}\\ m=1\text{; }n=1\text{; }P=2(1^2+1^2)+2(1+1)+1=9; & \text{YES}\\ m=1\text{; }n=2\text{; }P=2(1^2+2^2)+2(1+2)+1=17; & \text{YES}\\ m=1\text{; }n=3\text{; }P=2(1^2+3^2)+2(1+3)+1=29; & \text{YES}\\ m=1\text{; }n=4\text{; }P=2(1^2+4^2)+2(1+4)+1=45; & \text{YES}\\ m=1\text{; }n=5\text{; }P=2(1^2+5^2)+2(1+5)+1=65; & \text{YES}\\ m=1\text{; }n=6\text{; }P=2(1^2+6^2)+2(1+6)+1=89; & \text{YES}\\ m=1\text{; }n=7\text{; }P=2(1^2+7^2)+2(1+7)+1=117; & \text{NO}\\ m=2\text{; }n=2\text{; }P=2(2^2+2^2)+2(2+2)+1=25; & \text{YES}\\ m=2\text{; }n=3\text{; }P=2(2^2+3^2)+2(2+3)+1=37; & \text{YES}\\ m=2\text{; }n=4\text{; }P=2(2^2+4^2)+2(2+4)+1=53; & \text{YES}\\ m=2\text{; }n=5\text{; }P=2(2^2+5^2)+2(2+5)+1=73; & \text{YES}\\ m=2\text{; }n=6\text{; }P=2(2^2+6^2)+2(2+6)+1=97; & \text{YES}\\ m=2\text{; }n=7\text{; }P=2(2^2+7^2)+2(2+7)+1=125; & \text{NO}\\ m=3\text{; }n=3\text{; }P=2(3^2+3^2)+2(3+3)+1=49; & \text{YES}\\ m=3\text{; }n=4\text{; }P=2(3^2+4^2)+2(3+4)+1=65; & \text{YES}\\ m=3\text{; }n=5\text{; }P=2(3^2+5^2)+2(3+5)+1=85; & \text{YES}\\ m=3\text{; }n=6\text{; }P=2(3^2+6^2)+2(3+6)+1=109; & \text{NO}\\ m=3\text{; }n=7\text{; }P=2(3^2+7^2)+2(3+7)+1=137; & \text{NO}\\ m=4\text{; }n=4\text{; }P=2(4^2+4^2)+2(4+4)+1=81; & \text{YES}\\ m=4\text{; }n=5\text{; }P=2(4^2+5^2)+2(4+5)+1=101; & \text{NO}\\ m=4\text{; }n=6\text{; }P=2(4^2+6^2)+2(4+6)+1=125; & \text{NO}\\ m=4\text{; }n=7\text{; }P=2(4^2+7^2)+2(4+7)+1=153; & \text{NO}\\ m=5\text{; }n=5\text{; }P=2(5^2+5^2)+2(5+5)+1=121; & \text{NO}\\ m=5\text{; }n=6\text{; }P=2(5^2+6^2)+2(5+6)+1=145; & \text{NO}\\ m=5\text{; }n=7\text{; }P=2(5^2+7^2)+2(5+7)+1=173; & \text{NO}\\ m=6\text{; }n=6\text{; }P=2(6^2+6^2)+2(6+6)+1=169; & \text{NO}\\ m=6\text{; }n=7\text{; }P=2(6^2+7^2)+2(6+7)+1=197; & \text{NO}\\ m=7\text{; }n=7\text{; }P=2(7^2+7^2)+2(7+7)+1=225; & \text{NO}\\ \end{cases}$

Combining all of the YES results cases on both cases above we have the possible elements of {1, 2, 3, ... ,100} that are values of $P$ and are not repeated as:

{1, 2,4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100}

Which give a total of $43$ elements.

NOTE: There is probably a better method than grinding the results. for all combinations of odds and evens on the values and finding the combinatorial equations. However, since some of the combinations repeat values, then I couldn't find a proper way to find how many elements without actually finding all of the elements.

Part ii.

$P=2x^2 - 6xy + 5y^2=(x^2-4xy+4y^2)+(x^2-2xy+y^2)=(x-2y)^2+(x-y)^2$

Therefore we can re-write $P$ as $P=A^2+B^2$ where $A=x-2y$ and $B=x-y$ and are both integers.

Thus we can now pick two integers $C=x_2-2y_2$ and $D=x_2-y_2$ , thus $P=C^2+D^2$ .

We now find their products:

$(A^2+B^2)(C^2+D^2)=(AC)^2+(AD)^2+(BC)^2+(BD)^2+2(ABCD)^2-2(ABCD)^2$

$=(AC+BD)^2-(AD-BC)^2$

Let $Q=AC+BD$ and $R=AD-BC$ then the product of two values of $P$ is $Q^2+R^2$ which is also a value of $P$ because it is also written as the sum of two squares.

Note. I actually competed at this event in Argentina when I was in High School representing Puerto Rico. I have no idea what I did on this one nor how many points they gave me. Probably close to zero on this one.

~Tomas Diaz. ~orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Page

Toolbox

Search

Difference between revisions of "1991 OIM Problems/Problem 5"

Latest revision as of 08:41, 23 December 2023

Problem

Solution

See also

@@ Line 22: / Line 22: @@
 Since <math>(-y)^2=y^2</math> we can look at the combinations of <math>y</math> with <math>K</math> for non-negative values.  So, we can use: <math>0 \le y \le 14</math> to find the values of <math>P</math>
-Since
+Since <math>x=\frac{3y \pm K}{2}</math>, <math>P=\frac{K^2+y^2}{2}</math>, then to get integers <math>x</math> and <math>P</math>, both expressions <math>K^2+y^2</math> and <math>3y \pm K</math> need to be even.  This happens when either <math>K</math> and <math>y</math> are both odd, or both even. Thus we will try both cases:
+'''Case 1:''' Both <math>K</math> and <math>y</math> are even.
+Let <math>K=2n</math>, <math>y=2m</math> where integers <math>n</math> and <math>m</math> with <math>0 \le n \le 7</math> and <math>0 \le m \le 7</math>
+<math>P=\frac{K^2+y^2}{2}=\frac{4n^2+4m^2}{2}=2(n^2+m^2)</math>
+Now we try the possible combinations of <math>n</math> and <math>m</math>:
+<math>\begin{cases}
+m=0\text{; }n=0\text{; }P=2(0^2+0^2)=0; & \text{NO}\\
+m=0\text{; }n=1\text{; }P=2(0^2+1^2)=2; & \text{YES}\\
+m=0\text{; }n=2\text{; }P=2(0^2+2^2)=8; & \text{YES}\\
+m=0\text{; }n=3\text{; }P=2(0^2+3^2)=18; & \text{YES}\\
+m=0\text{; }n=4\text{; }P=2(0^2+4^2)=32; & \text{YES}\\
+m=0\text{; }n=5\text{; }P=2(0^2+5^2)=50; & \text{YES}\\
+m=0\text{; }n=6\text{; }P=2(0^2+6^2)=72; & \text{YES}\\
+m=0\text{; }n=7\text{; }P=2(0^2+7^2)=98; & \text{YES}\\
+m=1\text{; }n=1\text{; }P=2(1^2+1^2)=4; & \text{YES}\\
+m=1\text{; }n=2\text{; }P=2(1^2+2^2)=10; & \text{YES}\\
+m=1\text{; }n=3\text{; }P=2(1^2+3^2)=20; & \text{YES}\\
+m=1\text{; }n=4\text{; }P=2(1^2+4^2)=34; & \text{YES}\\
+m=1\text{; }n=5\text{; }P=2(1^2+5^2)=52; & \text{YES}\\
+m=1\text{; }n=6\text{; }P=2(1^2+6^2)=74; & \text{YES}\\
+m=1\text{; }n=7\text{; }P=2(1^2+7^2)=100; & \text{YES}\\
+m=2\text{; }n=2\text{; }P=2(2^2+2^2)=16; & \text{YES}\\
+m=2\text{; }n=3\text{; }P=2(2^2+3^2)=26; & \text{YES}\\
+m=2\text{; }n=4\text{; }P=2(2^2+4^2)=40; & \text{YES}\\
+m=2\text{; }n=5\text{; }P=2(2^2+5^2)=58; & \text{YES}\\
+m=2\text{; }n=6\text{; }P=2(2^2+6^2)=80; & \text{YES}\\
+m=2\text{; }n=7\text{; }P=2(2^2+7^2)=106; & \text{NO}\\
+m=3\text{; }n=3\text{; }P=2(3^2+3^2)=36; & \text{YES}\\
+m=3\text{; }n=4\text{; }P=2(3^2+4^2)=50; & \text{YES}\\
+m=3\text{; }n=5\text{; }P=2(3^2+5^2)=68; & \text{YES}\\
+m=3\text{; }n=6\text{; }P=2(3^2+6^2)=90; & \text{YES}\\
+m=3\text{; }n=7\text{; }P=2(3^2+7^2)=116; & \text{NO}\\
+m=4\text{; }n=4\text{; }P=2(4^2+4^2)=64; & \text{YES}\\
+m=4\text{; }n=5\text{; }P=2(4^2+5^2)=82; & \text{YES}\\
+m=4\text{; }n=6\text{; }P=2(4^2+6^2)=104; & \text{NO}\\
+m=4\text{; }n=7\text{; }P=2(4^2+7^2)=130; & \text{NO}\\
+m=5\text{; }n=5\text{; }P=2(5^2+5^2)=100; & \text{YES}\\
+m=5\text{; }n=6\text{; }P=2(5^2+6^2)=122; & \text{NO}\\
+m=5\text{; }n=7\text{; }P=2(5^2+7^2)=148; & \text{NO}\\
+m=6\text{; }n=6\text{; }P=2(6^2+6^2)=144; & \text{NO}\\
+m=6\text{; }n=7\text{; }P=2(6^2+7^2)=170; & \text{NO}\\
+m=7\text{; }n=7\text{; }P=2(7^2+7^2)=196; & \text{NO}
+\end{cases}</math>
+'''Case 2:''' Both <math>K</math> and <math>y</math> are odd.
+Let <math>K=2n+1</math>, <math>y=2m+1</math> where integers <math>n</math> and <math>m</math> with <math>0 \le n \le 7</math> and <math>0 \le m \le 7</math>
+<math>P=\frac{K^2+y^2}{2}=\frac{4n^2+4m^2+4n+4n+2}{2}=2(n^2+m^2)+2(n+m)+1</math>
+Now we try the possible combinations of <math>n</math> and <math>m</math>:
+<math>\begin{cases}
+m=0\text{; }n=0\text{; }P=2(0^2+0^2)+2(0+0)+1=1; & \text{YES}\\
+m=0\text{; }n=1\text{; }P=2(0^2+1^2)+2(0+1)+1=5; & \text{YES}\\
+m=0\text{; }n=2\text{; }P=2(0^2+2^2)+2(0+2)+1=13; & \text{YES}\\
+m=0\text{; }n=3\text{; }P=2(0^2+3^2)+2(0+3)+1=25; & \text{YES}\\
+m=0\text{; }n=4\text{; }P=2(0^2+4^2)+2(0+4)+1=41; & \text{YES}\\
+m=0\text{; }n=5\text{; }P=2(0^2+5^2)+2(0+5)+1=61; & \text{YES}\\
+m=0\text{; }n=6\text{; }P=2(0^2+6^2)+2(0+6)+1=85; & \text{YES}\\
+m=0\text{; }n=7\text{; }P=2(0^2+7^2)+2(0+7)+1=113; & \text{NO}\\
+m=1\text{; }n=1\text{; }P=2(1^2+1^2)+2(1+1)+1=9; & \text{YES}\\
+m=1\text{; }n=2\text{; }P=2(1^2+2^2)+2(1+2)+1=17; & \text{YES}\\
+m=1\text{; }n=3\text{; }P=2(1^2+3^2)+2(1+3)+1=29; & \text{YES}\\
+m=1\text{; }n=4\text{; }P=2(1^2+4^2)+2(1+4)+1=45; & \text{YES}\\
+m=1\text{; }n=5\text{; }P=2(1^2+5^2)+2(1+5)+1=65; & \text{YES}\\
+m=1\text{; }n=6\text{; }P=2(1^2+6^2)+2(1+6)+1=89; & \text{YES}\\
+m=1\text{; }n=7\text{; }P=2(1^2+7^2)+2(1+7)+1=117; & \text{NO}\\
+m=2\text{; }n=2\text{; }P=2(2^2+2^2)+2(2+2)+1=25; & \text{YES}\\
+m=2\text{; }n=3\text{; }P=2(2^2+3^2)+2(2+3)+1=37; & \text{YES}\\
+m=2\text{; }n=4\text{; }P=2(2^2+4^2)+2(2+4)+1=53; & \text{YES}\\
+m=2\text{; }n=5\text{; }P=2(2^2+5^2)+2(2+5)+1=73; & \text{YES}\\
+m=2\text{; }n=6\text{; }P=2(2^2+6^2)+2(2+6)+1=97; & \text{YES}\\
+m=2\text{; }n=7\text{; }P=2(2^2+7^2)+2(2+7)+1=125; & \text{NO}\\
+m=3\text{; }n=3\text{; }P=2(3^2+3^2)+2(3+3)+1=49; & \text{YES}\\
+m=3\text{; }n=4\text{; }P=2(3^2+4^2)+2(3+4)+1=65; & \text{YES}\\
+m=3\text{; }n=5\text{; }P=2(3^2+5^2)+2(3+5)+1=85; & \text{YES}\\
+m=3\text{; }n=6\text{; }P=2(3^2+6^2)+2(3+6)+1=109; & \text{NO}\\
+m=3\text{; }n=7\text{; }P=2(3^2+7^2)+2(3+7)+1=137; & \text{NO}\\
+m=4\text{; }n=4\text{; }P=2(4^2+4^2)+2(4+4)+1=81; & \text{YES}\\
+m=4\text{; }n=5\text{; }P=2(4^2+5^2)+2(4+5)+1=101; & \text{NO}\\
+m=4\text{; }n=6\text{; }P=2(4^2+6^2)+2(4+6)+1=125; & \text{NO}\\
+m=4\text{; }n=7\text{; }P=2(4^2+7^2)+2(4+7)+1=153; & \text{NO}\\
+m=5\text{; }n=5\text{; }P=2(5^2+5^2)+2(5+5)+1=121; & \text{NO}\\
+m=5\text{; }n=6\text{; }P=2(5^2+6^2)+2(5+6)+1=145; & \text{NO}\\
+m=5\text{; }n=7\text{; }P=2(5^2+7^2)+2(5+7)+1=173; & \text{NO}\\
+m=6\text{; }n=6\text{; }P=2(6^2+6^2)+2(6+6)+1=169; & \text{NO}\\
+m=6\text{; }n=7\text{; }P=2(6^2+7^2)+2(6+7)+1=197; & \text{NO}\\
+m=7\text{; }n=7\text{; }P=2(7^2+7^2)+2(7+7)+1=225; & \text{NO}\\
+\end{cases}</math>
+Combining all of the YES results cases on both cases above we have the possible elements of {1, 2, 3, ... ,100} that are values of <math>P</math> and are not repeated as:
+{1, 2,4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100}
+Which give a total of <math>43</math> elements.
+'''NOTE:''' There is probably a better method than grinding the results. for all combinations of odds and evens on the values and finding the combinatorial equations.  However, since some of the combinations repeat values, then I couldn't find a proper way to find how many elements without actually finding all of the elements.
+'''Part ii.'''
+<math>P=2x^2 - 6xy + 5y^2=(x^2-4xy+4y^2)+(x^2-2xy+y^2)=(x-2y)^2+(x-y)^2</math>
+Therefore we can re-write <math>P</math> as <math>P=A^2+B^2</math> where <math>A=x-2y</math> and <math>B=x-y</math> and are both integers.
+Thus we can now pick two integers <math>C=x_2-2y_2</math> and <math>D=x_2-y_2</math>, thus <math>P=C^2+D^2</math>.
+We now find their products:
+<math>(A^2+B^2)(C^2+D^2)=(AC)^2+(AD)^2+(BC)^2+(BD)^2+2(ABCD)^2-2(ABCD)^2</math>
+<math>=(AC+BD)^2-(AD-BC)^2</math>
+Let <math>Q=AC+BD</math> and <math>R=AD-BC</math> then the product of two values of <math>P</math> is <math>Q^2+R^2</math> which is also a value of <math>P</math> because it is also written as the sum of two squares.
 * Note.  I actually competed at this event in Argentina when I was in High School representing Puerto Rico.  I have no idea what I did on this one nor how many points they gave me.  Probably close to zero on this one.
+~Tomas Diaz. ~orders@tomasdiaz.com
 {{Alternate solutions}}
 == See also ==
+[[OIM Problems and Solutions]]
 https://www.oma.org.ar/enunciados/ibe6.htm