Let $a, b, c$ be three distinct positive integers. Define $S(a, b, c)$ as the set of all rational roots of $px^2 + qx + r = 0$ for every permutation $(p, q, r)$ of $(a, b, c)$. For example, $S(1, 2, 3) = \{ -1, -2, -1/2 \}$ because the equation $x^2+3x+2$ has roots $-1$ and $-2$, the equation $2x^2+3x+1=0$ has roots $-1$ and $-1/2$, and for all the other permutations of $(1, 2, 3)$, the quadratic equations formed don't have any rational roots. Determine the maximum number of elements in $S(a, b, c)$.
Problem
Source: INAMO 2023 P8 (OSN 2023)
Tags: algebra, polynomial, quadratic equation, quadratics, maximization, Indonesia
30.08.2023 12:09
.
30.08.2023 14:17
INAMO 2023/8 wrote: Given three distinct positive integers $a,b$, and $c$. Define $S(a,b,c)$ as the set of all rational roots of the equation $px^2 + qx + r = 0$, where $(p,q,r)$ is a permutation of $(a,b,c)$. For instance, $S(1, 2, 3) = \left \{ -1, -2, -\frac{1}{2} \right \}$ because the equation $x^2 + 3x + 2 = 0$ has roots $-1$ and $-2$, the equation $2x^2 + 3x + 1 = 0$ has roots $-1$ and $-\frac{1}{2}$, whereas the other permutations do not produce quadratic equations with rational roots. Determine the maximum number of elements in $S(a,b,c)$. My problem. I'm really surprised (and slightly disappointed) that this got into problem 8, when I suggested this version as problem 2 instead... The following problem is the original problem I suggested for problem 8. Too bad they didn't go with this version. Original Problem wrote: Given three distinct positive integers $a,b$, and $c$. Define $S(a,b,c)$ as the set of all rational roots of the equation $px^2 + qx + r = 0$, where $(p,q,r)$ is a permutation of $(a,b,c)$. For instance, $S(1, 2, 3) = \left \{ -1, -2, -\frac{1}{2} \right \}$ because the equation $x^2 + 3x + 2 = 0$ has roots $-1$ and $-2$, the equation $2x^2 + 3x + 1 = 0$ has roots $-1$ and $-\frac{1}{2}$, whereas the other permutations do not produce quadratic equations with rational roots. Find all positive integers $k \not= 6$ such that there exists distinct positive integers $a,b,c$ such that $S(a,b,c)$ has exactly $k$ elements. I will only write my solution for the original INAMO 2023/8 problem. The answer is $\boxed{8}$, achieved by $(a,b,c) = (2,17,35)$. We can see that in this case, \[ S(a,b,c) = \left \{-17, - 5, -\frac{7}{2}, -2, - \frac{1}{2}, - \frac{1}{5}, - \frac{2}{7}, - \frac{1}{17} \right \} \]To prove this bound, we see that for $px^2 + qx + r$ to have rational solutions, we need $q^2 - 4pr \ge 0$. Note that there exists a permutation $(d,e,f)$ of $(a,b,c)$ such that $d < e < f$. In this case, $d^2 - 4ef < 0$ and thus both $ex^2 + dx + f$ and $fx^2 + dx + e$ won't contribute any rational roots. Therefore, we can only get a maximal of $2 \cdot 4 = 8$ rational root contributions from the remaining $4$ quadratic equation, as desired. Remark. The original problem I proposed deliberately ignore the case $k = 6$ because this case is equivalent to a theorem proved by Euler which states that all integer solutions of $x^3 + y^3 = 2z^3$ are of the form $(\ell, -\ell,0)$ and $(\ell, \ell, \ell)$. Remark. The main difficulty of this problem is the construction, which I think is actually pretty motivated. You start by doing cases for $\min(a,b,c)$, from which you can easily prove that $\min(a,b,c) = 1$ doesn't work. Then when you try $\min(a,b,c) = 2$, i.e. when you want $b^2 - 8c$ and $c^2 - 8b$ are squares, the most "natural" thing to try is to force $b$ to be a polynomial in terms of $c$ such that $b^2 - 8c$ is a square of a polynomial in $c$, which means we would like something like $b = 2c + 1$, then the rest is easy: you would want $c^2 - 8(2c + 1) = (c - 8)^2 - 72$ to be a square.
30.08.2023 17:23
The stats shows that the contestant do much better in P7 than in P8. So the order is somewhat justified
30.08.2023 19:27
I'm here only to add that you can find $|S(a, b, c)| = 8$ whatever choice of $\min\{a, b, c\}$ you choose, as long as it is not $1$. WLOG let $a = \min\{a, b, c\} > 1$. Now solving for $b^2 - 4ac = (b - 2)^2$ yields $4ac = 4b - 4 \iff b = ac + 1$. Then $c^2 - 4ab = c^2 - 4a(ac + 1) = c^2 - 4a^2 c - 4a$, and you want it to be a square. Complete the squares: \[ c^2 - 4 a^2 c - 4a = (c - 2 a^2)^2 - 4(a^4 + a). \]We want this to be a square, and I am going to factor the latter as $2(a^2 + a) \cdot 2(a^2 - a + 1)$. Thus we pick $c$ such that \[ c - 2a^2 = (a^2 + a) + (a^2 - a + 1) = 2a^2 + 1 \iff c = 4a^2 + 1. \]In summary, now I just need to test the case where \[ (a, b, c) = (a, 4a^3 + a + 1, 4a^2 + 1). \]By some bashing, we get that \[ ax^2 + (4a^3 + a + 1) x + (4a^2 + 1) = (ax + 1)(x + 4a^2 + 1), \]\[ ax^2 + (4a^2 + 1) x + (4a^3 + a + 1) = (x + 2a + 1)(ax + 2a^2 - a + 1). \]That means... \[ S(a, 4a^3 + a + 1, 4a^2 + 1) = \left\{-\frac{1}{a}, -(4a^2 + 1), -a, -\frac{1}{4a^2 + 1}, -(2a + 1), -\left(2a - 1 + \frac{1}{a}\right), -\frac{1}{2a + 1}, -\frac{a}{2a^2 - a + 1}\right\}. \]Now you just check that for $a > 1$, we have $4a^2 + 1 > 2a + 1 > 2a - 1 + 1/a > a > 1$, which ensures that the above set has size $8$.
31.08.2023 04:45
You have two AOPS account? wkwkkwkw BlazingMuddy wrote: I'm here only to add that you can find $|S(a, b, c)| = 8$ whatever choice of $\min\{a, b, c\}$ you choose, as long as it is not $1$. WLOG let $a = \min\{a, b, c\} > 1$. Now solving for $b^2 - 4ac = (b - 2)^2$ yields $4ac = 4b - 4 \iff b = ac + 1$. Then $c^2 - 4ab = c^2 - 4a(ac + 1) = c^2 - 4a^2 c - 4a$, and you want it to be a square. Complete the squares: \[ c^2 - 4 a^2 c - 4a = (c - 2 a^2)^2 - 4(a^4 + a). \]We want this to be a square, and I am going to factor the latter as $2(a^2 + a) \cdot 2(a^2 - a + 1)$. Thus we pick $c$ such that \[ c - 2a^2 = (a^2 + a) + (a^2 - a + 1) = 2a^2 + 1 \iff c = 4a^2 + 1. \]In summary, now I just need to test the case where \[ (a, b, c) = (a, 4a^3 + a + 1, 4a^2 + 1). \]By some bashing, we get that \[ ax^2 + (4a^3 + a + 1) x + (4a^2 + 1) = (ax + 1)(x + 4a^2 + 1), \]\[ ax^2 + (4a^2 + 1) x + (4a^3 + a + 1) = (x + 2a + 1)(ax + 2a^2 - a + 1). \]That means... \[ S(a, 4a^3 + a + 1, 4a^2 + 1) = \left\{-\frac{1}{a}, -(4a^2 + 1), -a, -\frac{1}{4a^2 + 1}, -(2a + 1), -\left(2a - 1 + \frac{1}{a}\right), -\frac{1}{2a + 1}, -\frac{a}{2a^2 - a + 1}\right\}. \]Now you just check that for $a > 1$, we have $4a^2 + 1 > 2a + 1 > 2a - 1 + 1/a > a > 1$, which ensures that the above set has size $8$.
28.09.2023 04:59
barra wrote: The stats shows that the contestant do much better in P7 than in P8. So the order is somewhat justified I think, the bias that P8 is the hardest also make less participants approach this problem.