ZeusDM wrote: Find all triples of non-negative integers \((a, b, c)\) such that \[a^{2}+b^{2}+c^{2} = a b c+1.\] W.l.o.g. $a\leq b\leq c$. By Vieta-Jumping we can assume $c\leq\frac{ab}{2}$ or $a^2+b^2-1<0\Rightarrow(a,b,c)=(0,0,1)$. If $c\leq\frac{ab}{2}$ we have \begin{align*} abc+1=a^2+b^2+c^2\leq a^2+b^2+\frac{abc}{2}\\ \frac{abc}{2}\leq a^2+b^2-1\\ c\leq\frac{2(a^2+b^2-1)}{2ab}<\frac{4b^2}{2ab}=\frac{2}{a}b\leq\frac{2}{a}c\\ a<2\\ c\leq\frac{ab}{2}<b\leq c \end{align*}which is impossible. All solutions are $(0,0,1),(0,1,0),(1,0,0)$.

Actually $(0,0,1), (0,1,0), (1,0,0)$ are solutions.

I am confused here. Let $a\le b\le c$. Setting the quadratic \[ c^2-(ab)c+a^2+b^2-1=0, \]indeed if $c'$ is the other solution (keeping $a,b$ fixed), then $c+c'=ab$. However, how can you assume $c\le ab/2$? If $c=\max\{c,c'\}$ then actually $c\ge ab/2$, whereas otherwise how do you know if $a\le b\le c$ then $ab-c\ge a,b$ too?

grupyorum wrote:

I am confused here. Let $a\le b\le c$. Setting the quadratic \[ c^2-(ab)c+a^2+b^2-1=0, \]indeed if $c'$ is the other solution (keeping $a,b$ fixed), then $c+c'=ab$. However, how can you assume $c\le ab/2$? If $c=\max\{c,c'\}$ then actually $c\ge ab/2$, whereas otherwise how do you know if $a\le b\le c$ then $ab-c\ge a,b$ too? Rearrange $a,b,ab-c$ if $b>ab-c$.

The only solutions are $(0,0,1),(0,1,0),(1,0,0)$. Assume that $0 < a \leq b \leq c$. Notice that if $(a,b,c)$ is a solution then so is $(a,b,ab-c$), $(a,ac-b,c)$ and $(bc-a,b,c)$. This means that if there exists a solution then we generate an $\infty$ amount of solutions. Assume that there exists a solution whose all components are greater than or equal to $4$. Then we can assume that $c < \frac{1}{2}ab$, since we must have that $a^2+b^2-1=c(ab-c)$. Now let's take a look at the following assumption, if $a,b,c$ satisfy the equation, so they must satisfy the following $\frac{a^2+b^2+c^2}{abc}\geq 1$. Set $b=a+x$ and $c=a+x+y$, this translates into: $$a^2(a-3)+ax(a-4)+x^2(a-2)+y((a+x)(a-2)-y) \leq 0$$notice that $a+x+y < \frac{1}{2}a(a+x)$, or in other terms we must have that $y < (a+x)(\frac{1}{2}a-1)$, which implies that $(a+x)(a-2)-y > 0$, and since all terms of the inequality are positive since $a \geq 4$, we get that there isn't a solution if all of it's components are greater than $3$. Now we do a quick case bash, when one component is less than $4$, then when two components are less than $4$, from this we get no solutions. Thus we go to the case when we have that $a=0$, we get that $b=0$ and $c=1$, permutating we get the other solutions.

See that $(1,0,0)$ and permutations are solutions. We'll prove that those are the only solutions. First, see that if $b=c$ we have: $$a^2+2b^2=ab^2+1\implies(a-1)(a+1)=b^2(a-2)\implies a-2\mid a+1\implies a\in\{1,3,5\}$$where the only possible case is when $a=1$, which we have already considered. Now, suppose we have a solution $(a_0,b_0,c_0)$ with $a_0>b_0>c_0\geq1$ and $a_0+b_0+c_0$ minimal. See that: $$3a_0^2>a_0^2+b_0^2+c_0^2=a_0b_0c_0+1>a_0c_0^2\implies3a_0>c_0^2.$$By Vieta we have that the other root of: $$a_0^2-a_0\cdot b_0c_0+b_0^2+c_0^2-1=0$$$a_1$, is an integer and: $$a_1=\frac{b_0^2+c_0^2-1}{a_0}>0$$and thus $(a_1,b_0,c_0)$ is solution. By the minimality of $a_0$ we must have $a_1\geq a_0$ and therefore $b_0^2\geq a_0^2-c_0^2+1$: $$\implies a_0^2>b_0^2\geq a_0^2-c_0^2+1>a_0^2-3a_0+1\geq(a_0-2)^2$$since $a_0\geq3$, and thus we conclude $b_0=a_0-1$. We have: $$a_0^2+(a_0-1)^2+c_0^2=a_0(a_0-1)c_0+1\implies2a_0^2-2a_0+c_0^2=a_0^2c_0-a_0c_0$$$$\implies c_0^2=a_0(a_0-1)(c_0-2)>c_0^2(c_0-2)\implies c_0\in\{1,2\}$$which we can test and find no new solutions. $\blacksquare$

Solution at contest: Set $a\geq b \geq c$ Notice that $3a^2 \geq abc+1 > ac^2 \Rightarrow 3a>c^2$. Now assume that $(a,b,c)$ is the solution for the equation with all numbers $>0$ and with minimum sum. Since the equation: $x^2- xbc + b^2+c^2-1$ has two positive solutions $(a, \frac{b^2+c^2-1}{a}),$ then: $$\frac{b^2+c^2-1}{a}\geq a.$$$$\Rightarrow a+3>\frac {a^2 + 3a -1}{a}> \frac{a^2 + c^2 -1}{a} \geq \frac{b^2 + c^2 -1}{a} \geq a.$$Therefore, $\frac{b^2+c^2-1}{a}=a,a+1 \text{ or } a+2$ Meaning that the delta of the equation $x^2- xbc + b^2+c^2-1$ is $0,1 \text{ or } 4$. Then: $(bc)^2- 4(b^2+c^2)+4 = 0, 1 \text{ or } 4$ $\Rightarrow (b^2-4)(c^2-4) =12, 13 \text{ or } 16 $ but none of them have solution with $b,c>0$. Contradiction. Then one of the guys is $0$, meaning the only solution is $(1,0,0)$ and permutations.

Very very nice problem ekan Lekin yecholmadim

Assume $a, b, c > 2$. Looking at the equation as a quadratic on $a$, we get that the discriminant $$b^2(c^2-4) - 4(c^2 - 1)$$must be a perfect square. Then, in particular, it must be a quadratic residue modulo $c^2 - 4$ and modulo $c^2 - 1$, hence $$b^2(c^2-4) - 4(c^2 - 1) \equiv -4(4 - 1) \equiv 2^2 \cdot (-3) \mod{c^2 - 4}\text{, and}$$$$b^2(c^2-4) - 4(c^2-1)\equiv b^2(1 - 4) \equiv b^2\cdot (-3) \mod{c^2 - 1}$$must be a quadratic residues. Since $2^2$ and $b^2$ are certainly a quadratic residues, it must be the case that $-3$ is a quadratic residue. Now, assume $c\not\equiv -1\,\mathrm{mod}\, 3$. Then at least one of $c-2$ or $c+2$ must be of the form $3k - 1$, likewise for $c-1$ and $c+1$. As such, at least one of those 4 numbers is odd and of the form $3k - 1$, and thus divisible by an odd prime $p\equiv -1\,\mathrm{mod}\, 3$. Since we have either $p\, |\, c^2 - 4$ or $p\, |\, c^2 - 1$, $-3$ must be a quadratic residue modulo $p$. But then, by quadratic reciprocity: $$1 = \left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right) \left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{3}{p}\right) =(-1)^{\frac{p-1}{2}\cdot \frac{3-1}{2}}\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right)\left(\frac{3}{p}\right)^2 = \left(\frac{p}{3}\right) = -1$$which is absurd. Hence, we need $c\equiv -1\,\mathrm{mod}\, 3$. As such $c$ is congruent to $2$, $5$ or $8$ modulo $9$. Doing analogous work, we find that $a$ and $b$ must also be $2$, $5$ or $8$ modulo $9$. But:

again a contradiction. Hence $a, b, c \leq 2$ and testing each case we see the only solutions are $(1, 0, 0)$ and permutations. p.s.: I unfortunately did not finish this solution correctly in the contest (I did not exclude the case $c\equiv -1\,\mathrm{mod}\, 3$ correctly (edit 2: and also did not make sure $p$ was odd)), but I later found that it was still possible to complete it and was pretty glad. Though I'm pretty happy to have found a solution that goes a different path from what seems to be the "intended" solution (Vieta jumping), I'm kind of worrying that going against the grain will mean that I'm not gonna get a good score on this problem because of my mistake, even though I did write correctly the parts (edit 2: i did not, in fact, do those fully correctly, but the issue was small and easily fixable, and the main insight was not particularly affected) which I understand to be the hardest bits of this solution =/ edit 2: I fixed an issue there was with this solution: I had not made sure that the prime $p$ was odd. But now I have.

Let $a\geq b\geq c>0$. Consider the quadratic: $x^2-xbc+(b^2+c^2-1)=0$, it has roots $a$ and $a'$, where $a'=bc-a$. Lemma 1: $a'>0$ Proof: Assume $a'\leq 0\rightarrow a\geq bc\rightarrow a^2\geq abc\rightarrow a^2+b^2+c^2>abc+1$, Contradiction! Lemma 2: $a'<a$

$\rightarrow$ Contradiction! Let $(a_0, b_0, c_0)$ be the nonzero solution with the least $a$. By the Lemmas we can find a solution $(a_0', b_0, c_0)$, with $a_0'<a_0$, Contradiction! Thus there can only be solutions that contain zero. We can easily get the answer $(1,0,0); (0,1,0); (0,0,1)$.

$\therefore a \leq 3$ testing we don't have solution $\implies S = \varnothing$. So, at least one of them is $0$ and we get $\boxed{(a, b, c) = (0, 0, 1), (0, 1, 0), (1, 0, 0)}$