Show that $n!=a^{n-1}+b^{n-1}+c^{n-1}$ has only finitely many solutions in positive integers. Proposed by Dorlir Ahmeti, Albania
Problem
Source: 2021 ISL N5
Tags: number theory, AZE IMO TST
12.07.2022 15:46
A great challenge in applying various techniques! Let's begin by deriving simple explicit bounds between the variables. It is easy to guess that $n! \leq (\frac{n}{2})^n$ for $n\geq 3$, but this on its own would not prevent some troubles later and so it is better to strengthen it to e.g. $n! \leq (\frac{n-1}{2})^{n-1}$ for $n\geq 19$ (I will get back to motivate the need of this later). This follows by induction (for $n=19$ calculate directly; for the step it is enough to prove $2 + \frac{2}{n} \leq (1+\frac{1}{n-1})^{n-1}$, then multiply with the hypothesis $n!\leq (\frac{n}{2})^n$ and rearrange; for the latter note that $(1+\frac{1}{n})^{n-1} = \sum_{i=0}^{n-1} \binom{n-1}{i}\frac{1}{n^i} \geq \binom{n-1}{0}\frac{1}{n^0} + \binom{n-1}{1}\frac{1}{n} + \binom{n-1}{2}\frac{1}{n^2} = 1 + (1-\frac{1}{n}) + \frac{1}{2}-\frac{3}{2n} + \frac{1}{n^2} > 2+\frac{2}{n}$). We deduce $a,b,c < \frac{n-1}{2}$, i.e. $a,b,c \leq \frac{n-2}{2}$, when $n\geq 19$ and we shall get back to this later. One could hope that a similar inequality such as $n! \geq (\frac{n}{3})^n$ would give bounds for $a$, $b$, $c$ from which to finish quickly, but if this was possible, this problem would certainly have not been N$5$! So let us instead try obtaining bounds by other standard techniques such as considering the equation modulo something or powers of primes in it. A meaningful main tool remaining is the Lifting the Exponent Lemma. However, there is no formulation for $p=2$ and sums of powers, so we better work with an odd prime. However, we also need the condition of $n-1$ to be odd in order to use the lemma. So suppose, for contradiction, that $n\geq 4$ is odd. Then $n! \equiv 0 \pmod 4$ and as $(a^{\frac{n-1}{2}})^2,(b^{\frac{n-1}{2}})^2,(c^{\frac{n-1}{2}})^2 \equiv 0,1 \pmod 4$, it must be the case that $a$, $b$, $c$ are all even. However, in this case Legendre's formula for $\nu_p(n!)$ implies $$n-1 \leq \nu_2(a^{n-1}+b^{n-1}+c^{n-1}) = \nu_2(n!) = \nu_2((n-1)!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n-1}{2^i} \right\rfloor < \sum_{i=1}^{\infty} \frac{n-1}{2^i} = n-1$$which is impossible. Hence $n$ is even. What remains to assure in order to apply the lemma is that e.g. $a+b$ has an odd prime divisor $p$ such that $p\nmid a,b$. Suppose, for contradiction, that $a+b$, $b+c$ and $c+a$ are all powers of $2$. Then $a$, $b$ and $c$ all have the same parity and since they cannot be odd (otherwise $n!$ would be -- not possible), they are all even. If they are all multiples of $4$, then $2(n-1) \leq \nu_2(n!) < n$, which is false. So without loss of generality $a=2$ but then $2+b$, $2+c$ being powers of $2$ implies $b=2^k - 2$, $c=2^{\ell}-2$ and hence $b = 2^k + 2^{\ell} - 4$ which is not a power of $2$ for both $k,\ell \geq 3$ (not divisible by $2^3$). So without loss of generality $b=2$ and $n! = 2^n + (2^{\ell}-2)^{n-1}$. Recalling $c < n$ from the beginning, we must have $2^{\ell} - 2 = c \mid n!$, so $2^{\ell} - 2 \mid 2^n$, impossible for $\ell \geq 3$ (divisor not a multiple of $4$), so $\ell = 2$ and $n! = 3 \cdot 2^{n-1}$, impossible for $n\geq 5$ for divisibility-by-$5$ reasons. Contradiction. So we have reached the point where we may without loss of generality assume that $a+b$ has an odd prime divisor $p$. We still have to check that $p\nmid a,b$! If otherwise, then $p\mid a,b$ and $a<n$ from the beginning implies $p\mid a \mid n!$, so $p\mid c^{n-1}$ and hence $p\mid c$, as well. So overall $$ n-1 \leq \nu_p(a^{n-1}+b^{n-1}+c^{n-1}) = \nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor < \sum_{i=1}^{\infty} \frac{n}{p^i} = \frac{n}{p-1} \leq \frac{n}{2} $$which is false! Hence we are finally ready to apply the Lifting lemma. Note that $p \leq a+b \leq n-2$ since $a,b \leq \frac{n-2}{2}$ from the beginning and together with $p\mid a+b \mid a^{n-1} + b^{n-1}$ we get $p\mid n!$ and $p\mid c$ (one reason I needed the strengthened inequality in the beginning, to assure that $p\mid c$ and $p\mid n!$). Exactly as above we have $\nu_p(n!) > \nu_p(c^{n-1})$ and so $\nu_p(n!) = \nu_p(n! - c^{n-1})$. Therefore $$ \sum_{j=1}^{n} \nu_p(j) = \nu_p(n!) = \nu_p(n! - c^{n-1}) = \nu_p(a^{n-1} + b^{n-1}) = \nu_p(a+b) + \nu_p(n-1). $$Hence all numbers from $1$ to $n$, except possibly $a+b$ and $n-1$, are not divisible by $p$, in particular there are at most two multiples of $p$ among $1$, $2$, $\ldots$, $n$. But $p\mid c$ implies $p\leq c \leq \frac{n-2}{2}$ and so there must be at least two multiples of $p$. Hence equality holds and since $a+b<n-1$, these multiples are $a+b=p$ and $n-1=2p$. (It could have been the case that $a+b=n-1=p$ under a weaker bound on $a$ and $b$ and this would have been a problem! This is also why the stronger inequality in the beginning is used.) However, $n$ is even, so $n-1 = 2p$ is impossible! Therefore the only eventual remaining possibilities are $n=1,2,3$ and even $4\leq n \leq 18$. Since there are finitely many possible $a,b,c$ for each $n$, we are done. (For completeness, one can brute-force check all $a,b,c \leq \frac{n-2}{2} \leq 8$ or strengthen some of the above arguments in order to conclude that all solutions are the permutations of $(2,1,1)$ with $n=3$ and $(2,2,2)$ with $n=4$.)
12.07.2022 15:46
This problem is proposed by me. And the original version was to find all positive integers $a,b,c$ and $n$ that satisfy condition. Which is a slightly harder.
12.07.2022 16:06
Assume otherwise, hence $n$ can obtain arbitrarily large values. We begin with some Claims: Claim 1: $n!<(n/2)^{n-1}$ for all large enough $n$. Proof: From Stirling's approximation $n! \sim \sqrt{2\pi n}(n/e)^n$ for large enough $n$ and so it suffices to check that $\sqrt{2\pi n}(n/e)^n<(n/2)^{n-1}$ for all large $n$, which is clear since $e>2$ and exponentials grow faster than polynomials $\blacksquare$ From the Claim, we infer that $a,b,c<n/2$ for all large $n$. Claim 2: $n$ is even. Proof: Assume otherwise. Then, if $n$ is odd, working $\pmod 2$ we see that all of $a,b,c$ must be even, since otherwise we would have $1$ even and $2$ odds, hence summing to $0+1+1 \equiv 2 \pmod 4$ in the RHS, a contradiction. Hence, $v_2(n!) \geq (n-1)$, and so the sum of the digits of $n$ in binary must be $1$ (by $v_2(n!)=n-s_2(n)$), which can be the case only when $n$ is a power of $2$, which doesn't work out since $n$ is odd $\blacksquare$ Claim 3: Not all of $a+b,b+c,c+a$ are powers of $2$. Proof: Assume otherwise. Let $a+b=2^k,b+c=2^\ell,c+a=2^m$ with $k,\ell,m \geq 1$. Then, we infer that either all of $a,b,c$ are odd or all even. All odd is an obvious $\pmod 2$ contradiction, hence they are all even. However, if $a=2x,b=2y,c=2z$, then $n!=2^{n-1}(x^{n-1}+y^{n-1}+z^{n-1})$, and so $n$ is a power of $2$ and $x^{n-1}+y^{n-1}+z^{n-1}$ is odd. Hence we may WLOG assume that $x$ is odd, too. Then, we have $x+y=2^{k-1},y+z=2^{\ell-1},z+x=2^{m-1}$ and so we have two cases to consider: Case 1: $k,\ell,m \geq 2$. Then, all of $x,y,z$ must be odd. Thus, $2^{k-1}+2^{\ell-1}+2^{m-1}=2(x+y+z) \equiv 2 \pmod 4$, and so we may assume that $k=2$. This in turn implies that $a=b=2$, hence $2^n+c^{n-1}=n!$, and so if $p \mid c$ then $p$ divides $2$, so $c=2^r$. So, $2^n+2^{r(n-1)}=n!$. If $r \geq 2$, then the exponent of $2$ in the LHS is more than $n-1$, absurd. So $r=1$ and $n!=3 \cdot 2^{n-1}$, hence the product of all odd numbers from $1$ to $n$ is $3$, i.e. $n=3$, which does not satisfy. Case 2: Some of them equals $1$, WLOG$ k=1$. Then, $a+b=2$, which is absurd since $a,b$ are supposed to be even $\blacksquare$ By Claim 3, we may pick an odd prime $p$ such that $p \mid b+c$ (WLOG). Since $n$ is even, $p \mid b^{n-1}+c^{n-1}$ and if $n$ is large enough, $p \leq b+c\leq (n/2-1)+(n/2-1)=n-2$, hence $p \mid n!$, which implies that $p \mid a$, too. Now, by LTE: $v_p(b^{n-1}+c^{n-1})=v_p(n-1)+v_p(b+c)$ and since $b+c \leq n-2<n-1$ we have $b+c \neq n-1$ hence $v_p(n!) \geq v_p(b+c)+v_p(n-1)$. If equality could hold, then there would be only two multiples of $p$ in $n!$, hence $2p<n<3n$, and so $b+c=p,n-1=2p$ which can't be the case since $n$ is even. So, $v_p(n!)> v_p(b+c)+v_p(n-1)$, which implies that $v_p(b+c)+v_p(n-1)=v_p(a^{n-1})=(n-1)v_p(a)$. Let $k$ be such that $p^t \leq n<p^{t+1}$. Then, $b+c<p^{t+1}$ and $n-1<p^{t+1}$ and so $v_p(b+c)+v_p(n-1)<2(t+1)=2t+2$. Thus, $2t+2>v_p(b+c)+v_p(n-1)=(n-1)v_p(a) \geq (n-1) \geq p^t-1,$ which in turn puts upper bounds on $p,t$, which is absurd since then $n<p^{t+1}$ would be upper-bounded too. We reached a contradiction, hence $n$ can obtain finitely many values, and subsequently the given equation has finitely many solutions.
12.07.2022 16:21
Quite approachable for a 2/5 in a TST, but some parts are a bit tricky. Otherwise, I am posting pretty much a similar solution: Firstly, a bit motivation: obviously we shall use LTE and the Legendre formula, but in order to do that for any prime $p|a+b$, we shall ensure $p<n$ (WLOG the pair is $(a,b)$), so we would need to have $a,b<\frac{n-1}{2}$. This motivates to prove that $n!<(\frac{n-1}{2})^{n-1}$, which is done with smart AM-GM (for $3.4...(n-4)$) and a few other bounds. Hence, we now assume $a,b,c<\frac{n-1}{2}$ If $n$ is odd, then the only possibility is $a,b,c$ to even , so comparing $v_2$ with Legendre finishes (we are using $v_p(n!)<\frac{n}{p-1}$). Suppose now $n$ is even. The motivation makes us consider two cases: Case 1. One of $a+b, b+c, c+a$ is not a power of $2$. Let $p | a+b$ and obviously $p$ doesn't divide $a,b$ (Legendre), $p|c$ and $v_p(c^{n-1})>v_p(n!)$. Hence $v_p(n!)=v_p(a+b)+v_p(n-1)$ due to LTE, so using $p<c<\frac{n-1}{2}, a+b<n$, the multiples of $p$ in $1,2,...,n$ shall be exactly $a+b$ and $n-1$ (the sum of the $v_p$'s of the others is $0$, hence $a+b=p,n-1=2p$, absurd. Case 2. All of $a+b, b+c, c+a$ are powers of $2$, then not all are divisible by $4$ (Legendre), so $a=b=2, c=2^s-2$ (some power of two can't be greater than $4$) and then $c=2^s-2|a^{n-1}+b^{n-1}=2^{n-1}+2^{n-1}=2^n$ so $c=2$ and now it's easy to finish.
12.07.2022 16:41
Solved with CT17 Assume $n$ is very large solution. $\textbf{Claim: }$ $n$ is even $\emph{Proof: }$ Suppose $n$ is odd. Then $n!\equiv 0\pmod{4},$ while $a^{n-1},b^{n-1},c^{n-1}$ are each $0$ or $1\pmod{4}.$ Therefore $a^{n-1}\equiv b^{n-1}\equiv c^{n-1}\equiv 0\pmod{4},$ so $a,b,c$ are all even. But then by Legendre's formula, \begin{align*} \nu_2(n!) &= \nu_2((n-1)!)\\ &= \lfloor (n-1)/2\rfloor+\lfloor (n-1)/4\rfloor+\lfloor (n-1)/8\rfloor+\dots\\ &< (n-1)/2+(n-1)/4+(n-1)/8+\dots\\ &= n-1\\ &\le\nu_2(a^{n-1}+b^{n-1}+c^{n-1}), \end{align*}contradicting the equation. $\blacksquare$ $\textbf{Claim: }$ WLOG $a+b$ is not a power of $2$ $\emph{Proof: }$ Suppose for the sake of contradiction that $a+b=2^x,a+c=2^y,b+c=2^z$ for $x\le y\le z.$ Then \[a=\frac{2^x+2^y-2^z}{2}.\]If $x,y<z,$ then $2^x+2^y\le 2^z,$ which is impossible as $a>0.$ Thus $y=z,$ giving \[a=2^{x-1},b=2^{x-1},c=2^{y-1}-2^{x-1}.\]If $x-1\ge 2,$ then $\nu_2(a^{n-1}+b^{n-1}+c^{n-1})\ge 2n-2,$ and we get a contradiction using Legendre as above. Otherwise, $a,b,c$ are bounded and we are done. $\blacksquare$ Fix an odd prime $p$ dividing $a+b.$ Note that $p\mid a^{n-1}+b^{n-1},$ so $p\mid c.$ Taking $\nu_p$ of both sides yields \[\nu_p(n)+\nu_p(n-1)+\dots+\nu_p(1)=\min(\nu_p(a+b)+\nu_p(n-1),(n-1)\nu_p(c)).\]Since $a,b<\tfrac{n}{2},$ we have $\nu_p(a+b)+\nu_p(n-1)\le 2\log_2(n)<n-1.$ Now we can get rid of the min: \[\nu_p(n)+\nu_p(n-1)+\dots+\nu_p(1)=\nu_p(a+b)+\nu_p(n-1).\]Since $p\le c<\tfrac{n}{2},$ there are at least two nonzero terms on the left. However, since $a+b<n-1<n,$ the nonzero terms on the left must be identical to the terms on the right. This forces $a+b=p$ and $n-1=2p,$ which is a contradiction as $n$ is even.
12.07.2022 19:24
We take $n$ to be large enough integer. Consider the case, when $n$ is even integer. Also suppose that none of the numbers $a+b, b+c, c+a$ are powers of $2$. WLOG, then there exists odd prime $p$ dividing $a+b$. Lemma: $ (\frac{n}{2})^{(n-1)}> n!$ Proof: We proceed by induction with base case $n=14$ being trivial by calculator. Suppose that for some positive integer $k$, we have $$ (\frac{k}{2})^{(k-1)} >k!$$. We need to prove that: $$ (\frac{k+1}{2})^{k} > (k+1)! $$Since $(k+1)(\frac{k}{2})^{(k-1)}>(k+1)!$, it is sufficient to prove that: $$ (\frac{k+1}{2})^{k}>(k+1)(\frac{k}{2})^{(k-1)} $$It can be rewritten as follows: $$(\frac{k+1}{2})^{(k-1)}>2(\frac{k}{2})^{(k-1)} \implies (1+\frac{1}{k})^{k-1}>2$$Using binomial expansion: $$ (1+\frac{1}{k})^{k-1} > 1+(k-1)\frac{1}{k}+ (k-1)(k-2)\frac{1}{2k^2} > 2,5 - \frac{1}{k}-\frac{3k-2}{2k^2}>2$$since the last $2$ terms are clearly neglectable for large enough $k$. From lemma follows that $a,b,c < \frac{n}{2}$, because otherwise: $$ n! = a^{n-1}+ b^{n-1}+ c^{n-1} >(\frac{n}{2})^{n-1}>n! $$which is obvious contradiction. Therefore $ a+b <n$, which leads to $p \mid n!$. Rewrite equation as follows: $$ n! -c^{n-1} = a^{n-1}+b^{n-1} $$Observe that since $n-1$ odd, we have $a^{n-1}+b^{n-1} =(a+b)(a^{n-2}-a^{n-1}n + ..+b^{n-2}) \equiv 0 \pmod p$. Moreover it is easy to see that $p \mid c^{n-1} \implies p \mid c$. By Legandre's formula we have that $\nu_p(n!) \le \frac{n}{p-1} <n-1$, whereas $\nu_p(c^{n-1}) \ge n-1$. Therefore by LTE lemma the following relation holds: $$ \nu_p(n!) = \nu_p(a+b) + \nu_p(n-1) $$This can be rewritten as: $$\nu_p(1)+\nu_p(2)+\ldots+ \nu_p(a+b-1) + \nu_p(a+b+1)+\ldots + \nu_p(n-2)+\nu_p(n) =0$$where we used the fact that $a+b<n$. Note that since $p \mid c$ and $c<\frac{n}{2}$, we must have $p < \frac{n}{2}$. This means that $a+b=p$ and $n-1=2p$. Last equation implies that $n$ is odd, whereas we assumed it is even. This means for large odd $n$ our initial equation has no solutions. We will return to what happens when $a+b; b+c; c+a$ is power of $2$ a bit later. For now, let's deal with the case when $n$ is an odd integer. Obviously, $n!$ is an even integer. This means that $a;b;c$ are all even integers or one of them is even, but the other two are odd. Suppose the latter is indeed the case. Since odd squares $\equiv 1 \pmod 4$, we have: $$0 \equiv n! = a^{n-1}+b^{n-1}+c^{n-1} \equiv 0+1+1 \equiv 2 \pmod 4$$. this is clearly a contradiction. Therefore $a;b;c$ are all even integers. Note that in that case $\nu_2(a^{n-1}+b^{n-1}+c^{n-1}) \ge n-1$. On the other hand using Lagrange formula once more: $$ \nu_2(n!) \le n-1$$with equality case if and onlf if $n$ is a power of $2$. Since we must have $\nu_2(a^{n-1}+b^{n-1}+c^{n-1})=\nu_2(n!)$, then we conclude that $n$ is a power of $2$. This is obviously impossible since it is assumed that $n$ is an odd integer. So finally we return to the case when $a+b;b+c; c+a$ are all power of $2$. It is easy to see that $a;b;c$ in that case are all even or all odd. If they are all odd; then $a+b+b+c-(c+a) = 2b$ is divisible by some power of $2$. Since $b$ is odd we immediately get that $b=1$ is the only possible value. Similarly we can deduce that $a=c=1$ too. Consider the case when all $a;b;c$ are even. We must have that $\nu_2(a)=\nu_2(b)=\nu_(c)$. Suppose not; then $a=2^xa_1; b=2^yb_1$; where $x>y$ and $a_1;b_1$ are odd integers. In that case: $2^(2^{x-y}a_1+b_1)$ is power of $2$. But this is impossible since $(2^{x-y}a_1+b_1)$ is some odd number greater than $1$. Contradiction. This means that $a=2^xa_1; b=2^xb_1; c=2^x_1c_1$. This means (after dividing both sides by $2^x$) that $a_1+b_1;b_1+c_1; c_1+a_1$ are powers of $2$ too. But in that case $a_1=b_1=c_1=1$. On the other hand: $$ n! = 3 \cdot 2^{x(n-1)}$$The left-hand side of the last equation is divisible by $9$ for large enough $n$, whereas the right-hand side is only by $3$. Contradiction. Thus all the cases are exhausted. This means that for large enough $n$ there is no solution to this equation. Therefore; there are only finitely many values of $n$ satisfying the equation; meaning only finitely many values of $a;b;c$ satisfying the equation. This concludes the proof.
12.07.2022 21:36
Stirling's Approximation is really useful.
Attachments:
IMO SHORTLIST 2021 N5 SOLUTION.docx (16kb)
14.07.2022 04:29
We claim that $n!<2\left(\frac{n+1}2\right)^{n-1}$ for all $n\geq4$. We have $$n!=2n(n-1)(3\cdot4\cdot\ldots\cdot(n-2))\leq2n(n-1)\left(\frac{n+1}2\right)^{n-4},$$so it suffices to show that $2n(n-1)<2\frac{(n+1)^3}8$, or $8n^2-8n<n^3+3n^2+3n+1$. This is equivalent to $n^3-5n^2+11n+1>0$, which is true as $n^3+11n\geq2n^2\sqrt{11}>5n^2$. Therefore, $n!<2\left(\frac{n+1}2\right)^{n-1}$ for all $n\geq4$. Now, if $n$ is odd, then $n!=x^2+y^2+z^2$ for some $x$, $y$, and $z$, so if $n\geq4$, then $8\mid x^2+y^2+z^2$, which implies $2\mid x,y,z$. Therefore, $2^{n-1}\mid n!$, which implies that $n$ is a power of $2$, which is a contradiction for $n\geq4$. Therefore, we must have $n=1$ or $n=3$, which gives $1=3$ and $6=a^2+b^2+c^2$, respectively, which gives the solutions $(a,b,c,n)=(2,1,1,3)$ and permutations. If $n$ is even, then $n-1$ is odd. Suppose $n\geq4$. Then, $n!=a^{n-1}+b^{n-1}+c^{n-1}>\frac1{2^{n-2}}(a+b)^{n-1}$. This means that $2\left(\frac{n+1}2\right)^{n-1}>\frac1{2^{n-2}}(a+b)^{n-1}$, which implies $n+1>a+b$, so $a+b\leq n$. Then, since $a+b\mid n!$ and $a+b\mid a^{n-1}+b^{n-1}$, we get $a+b\mid c^{n-1}$. If $p\mid a+b$, then $p\mid c$, which implies $\nu_p(n!)=\nu_p(a^{n-1}+b^{n-1}+c^{n-1})$. If $p\neq2$, then $\nu_p(n!)<n-1$ for $n\geq2$. This means that we must have $\nu_p(n!)=\nu_p(a^{n-1}+b^{n-1})=\nu_p(a+b)+\nu_p(n-1)$, so $\nu_p((n-2)!)+\nu_p(n)=\nu_p(a+b)$. Assume without loss of generality $a+b$ is even. Then, $\nu_p((n-2)!)+\nu_p(n)=\nu_p\left(\frac{a+b}2\right)$, which gives a contradiction as $\frac{a+b}2$ and $a+b$ both divide $(n-2)!n$. Therefore, $p\nmid a+b$, so $a+b$ is a power of $2$. If $a$ and $b$ are both odd, then $$\nu_2(n!)\leq\nu_2(n!-c^{n-1})=\nu_2(a^{n-1}+b^{n-1})=\nu_2(a+b).$$This is a contradiction for $n\geq4$. If $a$ and $b$ are both even, then $c$ is also even, which means that $a+b$, $b+c$, and $c+a$ are all powers of $2$. If all of these powers of $2$ are at least $8$, then $a=\frac{(a+b)+(a+c)-(b+c)}2$ is a multiple of $4$. Similarly, $4\mid b$ and $4\mid c$, which is a contradicion for $n\geq2$ as $\nu_2(n!)\leq n-1$. Therefore, assume without loss of generality $a+b\leq4$. We must have $a=b=2$, so $c^{n-1}=n!-2^n$, where $c+2$ is a power of $2$. Then, $c$ is even so $n$ is a power of $2$ as $\nu_2(n!)=n-1$. Since $c<n$, we have $c\mid n!-2^n$ and $c\mid n!$, so $c\mid2^n$, which implies $c$ and $c+2$ are both powers of $2$. This is only possible when $c=2$, which gives $n!=3\cdot2^{n-1}$, which implies $n\leq4$. For $n=2$, we get $2=a+b+c$, which is impossible. For $n=4$, we get $24=a^3+b^3+c^3$, which means $a=b=c=2$. Therefore, the only solutions for $(a,b,c,n)$ are $\boxed{(2,1,1,3)}$, $\boxed{(1,2,1,3)}$, $\boxed{(1,1,2,3)}$, and $\boxed{(2,2,2,4)}$.
14.07.2022 10:39
Very nice problem! I love the fact that they ask for finitely many solutions, making a problem more about thinking with conceptual ideas rather than griding through boring calculations. Assume $n$ is sufficiently large. We have two cases. Case 1: $n$ is odd. Notice that because $n$ is not a power of two, $\nu_2(n!) < n-1$. Therefore, $a,b,c$ cannot be all even, so we must have $a,b$ odd and $c$ even. However, this implies that $a^{n-1} + b^{n-1} = a^{\text{even}} + b^{\text{even}}$ is never divisible by $4$, a contradiction by modulo $4$. Case 2: $n$ is even. We first prove that $a+b$ must be a power of two. Assume not, then take an odd prime divisor $p\mid a+b$. Since $p\mid a^{n-1} + b^{n-1}$ and $p\mid n!$, we have $p\mid c$. By Stirling, $n! = \sqrt{2\pi n}\left(\tfrac ne\right)^n$, so we have $c < \tfrac{n}{2.5} = 0.4n$, so $p\leq c<0.4n$. However, by LTE, $$\nu_p(n!) = \nu_p(n! - c^{n-1}) = \nu_p(a+b) + \nu_p(n-1).$$However, notice that since $p<0.4n$ and $a+b<0.8n$, we must have $p(a+b)\mid (n-2)!$, a contradiction. Similarly, $a+b$, $b+c$, and $c+a$ must be a power of two. However, if $8$ divides all of $a+b,b+c,c+a$, then $a,b,c$ must all be divisible by $4$, implying a contradiction due to $\nu_2$ being too large. Therefore, we have two cases If $a+b=2$ or $a=b=1$, then $c^{n-1}+2=n!$, a parity contradiction since $c$ must be odd. If $a+b=4$, then $(a,b)=(1,3)$ or $a=b=2$. If the former happens, we use parity contradiction as above. Otherwise, we have $c^{n-1} + 2^n = n!$. However, this implies that any odd prime divisor of $c$ (which is $<n$) will not divide $n!$, a contradiction.
17.07.2022 02:27
It suffices to show that there are no solutions for $n > 5^7$, since for each $n \leq 5^6$, there can only be finitely many solutions since $a, b, c$ are integers greater than $0$ and less than $(n!)^{1/(n-1)}$ (assume $n > 1$ since $n = 1$ gives $3 = 1$, which clearly has no solutions), as $a^{n-1}, b^{n-1}, c^{n-1} < a^{n-1} + b^{n-1}+c^{n-1} = n!$. First, we will prove a few lemmas. Lemma 1: If $p > 2$ is a prime and $n > 2$ is a positive integer, then $\nu_p(n!) < n-1$. Consequently, if $a^{n-1} + b^{n-1} + c^{n-1} = n!$ for positive integers $a, b, c, n$ with $n > 2$, then there can be no prime greater than $2$ dividing all of $a, b, c$. Proof: By Legendre's Formula, $$\nu_p(n!) = \sum_{i=1}^{\infty}\left \lfloor \frac{n}{p^i}\right \rfloor \leq \sum_{i=1}^{\infty}\frac{n}{p^i} = \frac{n}{p-1} \leq \frac{n}{2} < n-1$$for all $k \geq 1$. The consequence follows since if there was such a prime $p$, then $p^{n-1}$ would divide the LHS, so it must divide the RHS, ergo $\nu_p(n!) \geq n-1$, a contradiction. Lemma 2: If $n$ is a positive integer that is not a power of $2$, then $\nu_2(n!) < n-1$. Consequently, if $a^{n-1} + b^{n-1} + c^{n-1} = n!$ for positive integers $a, b, c, n$ with $n$ not a power of $2$, then $a, b, c$ cannot all be even. Proof: Since $n$ is not a power of $2$, it must be between two consecutive powers of $2$. Thus, $2^k < n < 2^{k+1}$ for some positive integer $k$. Then, $$\nu_2(n!) = \sum_{i=1}^{\infty}\left \lfloor \frac{n}{2^i}\right \rfloor = \sum_{i=1}^{k}\left \lfloor \frac{n}{2^i}\right \rfloor \leq \sum_{i=1}^{k}\frac{n}{2^i} = n\left(1 - \frac{1}{2^k}\right) = n - \frac{n}{2^k} < n-1,$$since $n > 2^k$. The consequence follows in the same way the consequence for Lemma $1$ follows. Lemma 3: $n!^{1/(n-1)} < n$ for all integers $n > 2$. Consequently, if $a^{n-1} + b^{n-1} + c^{n-1} = n!$ for positive integers $a, b, c, n$ with $n > 2$, then all of $a, b, c$ are less than $n$. Proof: Note that $$\frac{n^{n-1}}{n!} = \frac{\underbrace{n\cdot n\cdot \cdots n}_{n\text{ of these}}}{n\cdot (n-1)\cdot \cdots 2} > 1\cdot 1 \cdots 1 = 1,$$which implies the conclusion. The consequence follows since $a^{n-1}, b^{n-1}, c^{n-1} < a^{n-1} + b^{n-1} + c^{n-1} = n! < n^{n-1}$, so $a, b, c < n$. Lemma 4: Let $x, y, z, k$ be positive integers with $k > 3$ and $$x^{2^k-1} + y^{2^k-1} + z^{2^k-1} = \frac{(2^k)!}{2^{2^k-1}}.$$Then, $x+y, y+z$, and $z+x$ cannot all be simultanouesly powers of $2$. Proof: Assume the contrary. If one of the powers of $2$ is $2$, then two of the variables (WLOG $x, y$) are $1$, so $$z^{2^k-1} = \frac{(2^k)!}{2^{2^k-1}} - 2.$$Since $$\nu_2\left(\frac{(2^k)!}{2^{2^k-1}}\right) = \nu_2((2^k)!) - (2^k-1) = (2^{k-1} + 2^{k-2} + \cdots + 1) - (2^k-1) = (2^k-1) - (2^k-1) = 0$$by Legendre's Formula, the RHS is odd. Thus, the LHS must be odd, so $z$ must be odd. If $z = 1$, then $$3 = \frac{(2^k)!}{2^{2^k-1}}.$$However, since $k > 3$, $5\mid (2^k)!$, so $5$ divides the RHS, and so it must divide the LHS, so $5\mid 3$, a contradiction. Thus, $z > 1$. By Lemma $3$, $2z = c < 2^k$, so $z < 2^k$ as well. Thus, $z \mid (2^k)!$ (as $z$ is odd, so the power of $2$ at the bottom does not prevent this from happening), so taking the equation modulo $z$ yields $$0 \equiv -2\pmod{z},$$so $z\mid 2$, implying $z\in \{1, 2\}$, a contradiction since $z$ is odd and greater than $1$. Thus, none of the powers of $2$ can be $2$, so $$x+y = 2^a,$$$$y+z = 2^b,$$$$z+x = 2^c,$$for positive integers $a, b, c\geq 2$ (as none of the powers of $2$ can be $1$ since $x+y, y+z, z+x \geq 1+1 = 2$), so $$x+y+z = 2^{a-1} + 2^{b-1} + 2^{c-1},$$implying $$z \equiv 2^{c-1} + 2^{b-1} - 2^{a-1} \equiv 0\pmod{2}$$$$x \equiv 2^{a-1} + 2^{c-1} - 2^{b-1} \equiv 0\pmod{2}$$$$y \equiv 2^{a-1} + 2^{b-1} - 2^{c-1} \equiv 0\pmod{2},$$so $2\mid x, y, z$, and so $2\mid \frac{(2^k)!}{2^{2^k-1}},$ but we saw earlier that $\frac{(2^k)!}{2^{2^k-1}}$ is odd, a contradiction. Now, we will break into cases. Case 1: $n$ is odd. Let $n > 5^7$ be an odd positive integer. Write $n = 2k+1$ for some integer $k > \frac{5^7-1}{2}$. Then, our goal is to show that $$a^{2k} + b^{2k} + c^{2k} = (2k+1)!$$has no solutions in positive integers for $k > \frac{5^7-1}{2}$. Assume for the sake of contradiction that there exists a positive integer solution $(a, b, c, k)$ to the equation with $k > \frac{5^7-1}{2}$. Note that since $5 \mid (2k+1)!$ as $2k+1\geq 5$, the RHS is divisible by $5$, so the LHS must also be divisible by $5$. If $k$ is even, then by FLT, $a^{2k}, b^{2k}, c^{2k}\in \{0, 1\}\pmod{5}$, so the only way for their sum to be $0\pmod{5}$ is if all of $a^{2k}, b^{2k}, c^{2k}$ are $0\pmod{5}$, ergo $5\mid a, b, c$, but by Lemma $1$, this cannot occur. Thus, $k$ is odd. Then, since $a^2\in \{0, 1, -1\}\pmod{5}$, and raising any of these to an odd power keeps it the same, it follows that $a^{2k} \equiv a^2\pmod{5}$, $b^{2k}\equiv b^2\pmod{5}$, $c^{2k}\equiv c^2\pmod{5}$. Furthermore, $a^{2k}, b^{2k}, c^{2k}\in \{0, 1, -1\}\pmod{5}$, so $(a^{2k}, b^{2k}, c^{2k})$ is either $(0, 0, 0)\pmod{5}$, or a permutation of $(0, -1, 1)\pmod{5}$. If it is $(0, 0, 0)\pmod{5}$, then as previously discussed this is a contradiction by Lemma $1$. Thus, $a^{2k}, b^{2k}, c^{2k}$ is a permutation of $(0, -1, 1)\pmod{5}$. WLOG, say that $a^{2k} \equiv 0\pmod{5}$, $b^{2k}\equiv -1\pmod{5}$, and $c^{2k}\equiv 1\pmod{5}$. Then, rewrite the equation as $$b^{2k} + c^{2k} = (2k+1)! - a^{2k}.$$As we showed in Lemma $1$, $\nu_p((2k+1)!) < 2k \leq \nu_p(a^{2k})$ (as $5\mid a$), so it follows that $\nu_p((2k+1)! - a^{2k}) = (2k+1)!$ by a well-known property of $\nu_p$'s. Since $b^2\equiv b^{2k}\equiv -1\pmod{5}$ and $c^2 \equiv c^{2k}\equiv 1\pmod{5}$, it follows that $5\mid b^2+c^2$ and $5\nmid b^2, c^2$, so by LTE, $$\nu_p(b^{2k} + c^{2k}) = \nu_p((b^2)^k + (c^2)^k) = \nu_p(b^2+c^2) + \nu_p(k).$$Thus, $$\nu_p(b^2+c^2) = \nu_p((2k+1)!) - \nu_p(k) = \nu_p((2k+1)(2k)\cdots (k+1)(k-1)\cdots 1).$$By Lemma $3$, $b, c < 2k+1$, so $b^2 + c^2 \leq 2(2k+1)^2$. Now, define $t := \lfloor \log_5(2k+1)\rfloor$. Then, $5^t \leq 2k+1 < 5^{t+1}$, so $$b^2 + c^2 \leq 2(2k+1)^2 < 2(5^{t+1})^2 < 5^{2t+3}.$$Therefore, the largest power of $5$ that can divide $b^2+c^2$ is $2t+2$, so $$\nu_p(b^2+c^2) \leq 2t+2.$$However, $(2k+1)(2k)\cdots (k+1)(k-1)\cdots 1$ has at least $t-1$ of $5^t, 5^{t-1},\cdots, 5^1$ contained in it (i.e. is one of the terms in the product), where the "at least $t-1$" is because there is no $k$ in the product. Therefore, $$\nu_p((2k+1)(2k)\cdots (k+1)(k-1)) \geq (t-1) + (t-2) + \cdots + 1 = \frac{t(t-1)}{2},$$so $$2t + 2 = \nu_p(b^2+c^2) = \nu_p((2k+1)(2k)\cdots (k+1)(k-1)) \geq \frac{t^2-t}{2},$$thus $$t^2 - t \leq 4t + 4 \iff t^2 - 5t - 4 = t(t-5) - 4 \leq 0,$$which is false for $t \geq 6$ since $t(t-5)-4$ is an increasing function of $t$ over $[5, \infty)$, and $t = 6$ gives $t(t-5) - 4 = 2 > 0$, so we must have $t < 6$, so $$5^6 > 5^{\lfloor \log_5(2k+1)\rfloor} > 5^{\log_5(2k+1) - 1} = \frac{2k+1}{5} > \frac{5^7}{5} = 5^6,$$absurd. Thus, there are no solutions when $n > 5^7$ is odd. Case 2: $n$ is even, but not a power of $2$. Let $n > 5^7$ be a even positive integer. Write $n = 2k$ for some integer $k > \frac{5^7}{2}$. Then, our goal is to show that $$a^{2k-1} + b^{2k-1} + c^{2k-1} = (2k)!$$has no solutions in positive integers for $k > \frac{5^7}{2}$. Assume for the sake of contradiction that there exists a positive integer solution $(a, b, c, k)$ with $k > \frac{5^7}{2}$. Then, since $2\mid (2k)!$, $2\mid a^{2k-1} + b^{2k-1} + c^{2k-1}$. Since $a, b, c\in \{0, 1\}\pmod{2}$, and $0$ and $1$ raised to any power gives $0$ and $1$ respectively, this means $2\mid a+b+c$. Thus, either $a\equiv b\equiv c\equiv 0\pmod{2}$ or $(a, b, c)$ is some permutation of $(1, 1, 0)\pmod{2}$. By Lemma $2$, we cannot have $a\equiv b\equiv c\equiv 0\pmod{2}$, so $(a, b, c)$ is some permutation of $(1, 1, 0)\pmod{2}$. WLOG say $a\equiv b\equiv 1\pmod{2}$ and $c\equiv 0\pmod{2}$, and rewrite the equation as $$a^{2k-1} + b^{2k-1} = (2k)! - c^{2k-1}.$$As we showed in Lemma $2$, $\nu_2(c^{2k-1}) \geq 2k-1 > \nu_2((2k)!)$, so by a well-known property of $\nu_p$'s, $\nu_2((2k)! - c^{2k-1}) = \nu_2((2k)!)$. On the other hand, we can write $$\nu_2(a^{2k-1} + b^{2k-1}) = \nu_2((a+b)(a^{2k-2} - a^{2k-3}b + a^{2k-4}b^2 - \cdots + b^{2k-2})) = \nu_2(a+b) + \nu_2(a^{2k-2} - a^{2k-3}b + a^{2k-4}b^2 - \cdots + b^{2k-2}).$$Since $a\equiv b\equiv 1\pmod{2}$, we have $$a^{2k-2} - a^{2k-3}b + a^{2k-4}b^2 - \cdots + b^{2k-2} \equiv \underbrace{1 + 1 + \cdots + 1}_{2k-1 \text{ ones}} \equiv 2k-1 \equiv 1\pmod{2},$$so $\nu_2(a^{2k-2} - a^{2k-3}b + a^{2k-4}b^2 - \cdots + b^{2k-2}) = 0$, and so the $\nu_2$ of the LHS is $\nu_2(a+b)$. Thus, we have $$\nu_2((2k)!) = \nu_2(a+b).$$Now, let $t := \lfloor \log_2(2k)\rfloor$. Then, $2^t \leq 2k < 2^{t+1}$. By Lemma $3$, $a, b < 2k$, so $a + b < 4k < 2^{t+2}$, so $\nu_2(a+b) < t+2$. On the other hand, $2^t$ and $2^2$ are contained in $(2k)!$ (i.e. are terms in the product, and they are distinct since $k > \frac{5^7}{2}$, so $t > 2$), so $\nu_2((2k)!) > t+2$, so $$t + 2 > \nu_2(a+b) = \nu_2((2k)!) > t+2,$$a contradiction. Case 3: $n$ is a power of $2$. Let $n > 5^7$ be a power of $2$. Write $n = 2^k$ for some integer $k > \log_2(5^7) > \log_2(4^7) = 14$. Then, our goal is to show that $$a^{2^k-1} + b^{2^k-1} + c^{2^k-1} = (2^k)!$$has no solutions in positive integers for $k > 14$. Assume for the sake of contradiction that there exists a positive integer solution $(a, b, c, k)$ with $k > 14$. Then, by the same logic as in case $2$, either $a\equiv b\equiv c\equiv 0\pmod{2}$ or $(a, b, c)$ is some permutation of $(1, 1, 0)\pmod{2}$. By the same logic as in case $2$ again, there the latter is impossible, so the former must occur, so set $a = 2x, b = 2y, c = 2z$ for positive integers $x, y, z$. Then, $$x^{2^k-1} + y^{2^k-1} + z^{2^k-1} = \frac{(2^k)!}{2^{2^k-1}}.$$ Thus, by Lemma $4$, there exists an odd prime $p$ dividing either $x+y, y+z$, or $z+x$. WLOG say $p\mid x+y$. Then, $p \mid x + y \mid x^{2^k-1} + y^{2^k-1}$, as $x + y \mid x^{2n+1} + y^{2n+1}$ for integers $n \geq 0$. By Lemma $3$, $a, b < 2^k$, so $x, y < 2^{k-1}$, implying $x + y < 2^k$. Thus, $p < 2^k$, so $p \mid (2^k)!$, so taking the equation modulo $p$ yields $$z^{2^k-1} \equiv 0\pmod{p},$$so $p \mid z$. Now, rewrite the equation as $$x^{2^k-1} + y^{2^k-1} = \frac{(2^k)!}{2^{2^k-1}} - z^{2^k-1}.$$Then, by Lemma $1$, $$\nu_p\left(\frac{(2^k)!}{2^{2^k-1}}\right) = \nu_p((2^k)!) < 2^k-1 \leq \nu_p(z^{2^k-1}),$$so by a well-known property of $\nu_p$'s, $$\nu_p\left(\frac{(2^k)!}{2^{2^k-1}} - z^{2^k-1}\right) = \nu_p\left(\frac{(2^k)!}{2^{2^k-1}}\right) = \nu_p((2^k)!).$$If $p \mid x$, then $p\mid (x+y) - x = y$ (and vice versa), so $$\nu_p(x^{2^k-1} + y^{2^k-1}) \geq 2^k-1$$in this case, giving $\nu_p((2^k)!) \geq 2^k-1$, which violates Lemma $1$. Thus, $p\nmid x, y$, so by LTE, $$\nu_p(x^{2^k-1} + y^{2^k-1}) = \nu_p(x+y) + \nu_p(2^k-1).$$Thus, $$\nu_p(x+y) = \nu_p(2^k(2^k-2)(2^k-3)\cdots 1).$$Write $x+y = pr$ for some integer $r$. If $x+y = 2^k-1$, then $pr = 2^k-1$, so if $r$ contains a prime divisor $q$ (greater than $2$ since $2^k-1$ is odd) other than $p$, then $\frac{2^k-1}{q}$ and $\frac{(2^k-1)2}{q}$ are terms both contained in the product and have the same $\nu_p$ as $2^k-1$, both not equal to $2^k-1$, then we have that the RHS is at least $2\nu_p(x+y)$, a contradiction. Thus, if $x+y = 2^k-1$, $r$ is a power of $p$ (possibly $1$), so $2^k - 1 = p^{\ell}$ for some $\ell$. If $\ell > 1$, then by Mihailescu we have no solutions. Else, $\ell = 1$, and so $r = 1$. Since $2^k - 1 = p\mid z$, this means $$\frac{(2^k)!}{2^{2^k-1}} = x^{2^k-1} + y^{2^k-1} + z^{2^k-1} > z^{2^k-1} \geq (2^k-1)^{2^k-1} > \left(\frac{2^k}{2}\right)^{2^k-1},$$so $$(2^k)! > (2^k)^{2^k-1}.$$By Lemma $1$, $(2^k)^{2^k-1} > (2^k)!$, so $(2^k)^{2^k-1}$ is greater than itself, a contradiction. Thus, we cannot have $x+y = 2^k-1$, so $x+y$ is contained in $2^k(2^k-2)(2^k-3)\cdots 1$. If $x+y\neq p$, then $p$ is also contained in this product, so $$\nu_p(x+y) = \nu_p(2^k(2^k-2)(2^k-3)\cdots 1) \geq \nu_p(x+y) + 1,$$a contradiction, so $x+y = p$. So $p$ must occur exactly once in $2^k(2^k-2)(2^k-3)\cdots 1$. If $p < 2^{k-1}$, then $2p$ is also contained in this, so $p$ occurs at least twice. Thus, $p \geq 2^{k-1}$, and since $p$ is odd, $p > 2^{k-1}$, and since $p\mid z$, $z > p > 2^{k-1}$, and so by the same bounding we did before, $(2^k)^{2^k-1}$ is greater than itself, a contradiction. Thus, we've exhausted all cases and we're done.
23.07.2022 23:23
20.05.2023 00:37
Deceptively simple problem statement, and many beautiful ideas. We prove that we cannot find solutions for arbitrarily large values of $n$. If there are only finitely many numbers $n$ can take, then the equation is bounded above and therefore has finitely many solutions. Let $n$ be very large. We claim that \[n! < \left(\frac{n-1}{2}\right)^{n-1}\]Indeed, by AM-GM, \begin{align*} n! &= 2\cdot (3\cdot 4\cdot \dots \cdot n) \\ &\le 2 \cdot \left(\frac{n+3}{2}\right)^{n-2} \end{align*}and since $\left(\frac{n-1}{n+3}\right)^{n-1}>c$ for some positive real constant $c$, for arbitrarily large $n$, we have \[\left(\frac{n-1}{n+3}\right)^{n-1}\cdot (n+3)\]being arbitrarily large, so certainly \[\left(\frac{n+3}{2}\right)^{n-2}\le \left(\frac{n-1}{2}\right)^{n-1}\]Therefore, our claim is proved. For this reason, $a,b,c<\tfrac{n-1}{2}$ and $a+b$, $b+c$, $c+a<n-1$. Note that \[\nu_p(n!)=\frac{n-s_p(n)}{p-1}\]where $s_p(n)$ is the sum of the digits of $n$ when written in base $p$. Suppose there is odd prime $p$, such that $p\mid a+b$, then $p\mid n!$. Thus, $p\mid c$. If $p\mid a$, then $p\mid b$ which implies that $\nu_p(n)\ge n-1$. But clearly, $\nu_p(n!)<n-1\le \nu_p(c^{n-1})$. Thus, \[\nu_p(n!)=\nu_p(n!-c^{n-1})\]On the other hand, \[\nu_p(n!)=\nu_p(n!-c^{n-1})=\nu_p(a^{n-1}+b^{n-1})=\nu_p(a+b)+\nu_p(n-1).\]Note that $a+b<n-1$ are both part of the product expansion of $n!$, so $a+b$ and $n-1$ are actually the only parts of it divisible by $p$. Thus, $a+b=p$ and $n-1=2p$. In particular, $n$ is odd. On the other hand, if $a+b$, $b+c$ and $c+a$ are all powers of two, then $a$, $b$, or $c$ being odd implies all the others being odd, so $n!$ is odd, absurd. Thus, $a$, $b$ and $c$ are all even. Note that \[n-1\ge \nu_2(n!)=\nu_2(a^{n-1}+b^{n-1}+c^{n-1})\ge (n-1)\text{min}(\nu_2(a),\nu_2(b),\nu_2(c))\]so one of $a$, $b$, and $c$ is not divisible by $4$. Then, one of $a+b$, $b+c$, $c+a$ is not divisible by $8$, so one of them is $4$. WLOG, $a+b=4\implies a=b=2$, and $c=2^k-2$ for some $k$. Thus, \[n!=2^{n-1}+2^{n-1}+\left(2^k-2\right)^{n-1}\]However, $2^k-2\mid n!$ and $2^k-2=n!-2^{n-1}-2^{n-1}$ so $2^k-2\mid 2^n$, which implies that $2^k-2$ itself is a power of $2$, and the only number that satisfies this is $k=2$, or $c=2$. Thus, $n!=3\cdot 2^{n-1}$, absurd. Therefore, the only large solutions that exist for $n$ are odd. This means that $a^{n-1}$, $b^{n-1}$, $c^{n-1}$ are squares, so $n!\pmod 4$ is the number of odd numbers in $a,b,c$. Clearly, this number must be zero, so $a$, $b$, $c$ are all even. However, \[\nu_2(n!)\le n-2\]so they can't all be even. Contradiction.
21.11.2023 21:38
It suffices to show that there only exist finitely many $n$ such that the equation has positive integer solutions $(a,b,c)$. Consider only $n$ sufficiently large. Lemma: Let $p \leq n$ be a prime. Then $p$ divides at most one of $a,b,c$, unless $p=2$ and $n$ is a power of $2$. Moreover, in this case $p^2$ cannot divide all three of $a,b,c$. Proof: Obviously $p$ cannot divide two of $a,b,c$. On the other hand, if it divides all three then $\nu_p(n!) \geq n-1$. By Legendre's formula this can only happen when $p=2$ and $n$ is a power of $2$, and in this case if $p^2$ divides all three then $\nu_p(n!) \geq 2(n-1)$ which is impossible. Claim: $n$ is even. Proof: Suppose otherwise, so $n$ is not a power of $2$. Then $2$ divides at most one of $a,b,c$ and thus $a^{n-1}+b^{n-1}+c^{n-1} \in \{1,2\} \pmod{4}$ since it's the sum of three squares, at most one of which is even. But this is absurd since $4 \mid n!$. Now, as a consequence of Stirling's approximation, we have $n! \leq (0.4n)^{n-1}$ for all large enough $n$, so $a,b,c, \leq 0.4n$. If we pick some some odd prime $p \mid b+c \mid b^{n-1}+c^{n-1}$, then $p \mid n!$ as well since $b+c \leq 0.8n$, so they divide $a^{n-1}$ and thus $a$ as well, and therefore don't divide $b+c$. Then $\nu_p(a^{n-1})=(n-1)\nu_p(a) \geq \nu_p(n!)$ by Legendre again, so we require $\nu_p(b^{n-1}+c^{n-1}) \geq \nu_p(n!)$. On the other hand, if $p$ is odd, then since $p \mid b+c$ and $n-1$ is odd, exponent lifting gives $\nu_p(b^{n-1}+c^{n-1})=\nu_p(b+c)+\nu_p(n-1)$. But both $b+c$ and $n-1$ are in $[1,n]$ and divisible by $p$, hence no other integers in $[1,n]$ are divisible by $p$ and we have $b+c=p$, $n-1=2p$. But $n-1$ is odd, so this is absurd. Thus $b+c$ is a power of $2$, and so are $a+b,a+c$ by similar reasoning. Pick the number among $a,b,c$ with minimal $\nu_2$, which by the claim has $\nu_2$ at most $1$; WLOG this number is $a$. On the other hand, if $a+b=2^x,a+c=2^y,b+c=2^z$ then $2a=2^x+2^y-2^z$. Thus $\min\{x,y,z\}\leq \nu_2(a)+1 \leq 2$. If $\min\{x,y,z\} \leq 1$, so two of the variables equal $1$. To have all three of $a+b,a+c,b+c$ be powers of two, the third must be odd, but then $n!$ is odd as well: absurd. If $\min\{x,y,z\}=2$, then $\nu_2(a)=1$. Furthermore, the two variables summing to $2^{\min\{x,y,z\}}$ must both be even, hence they both equal $2$. The third element then must be of the form $2^k-2$. So now suppose that $(a,b,c)=(2,2,2^k-2)$ works for infinitely many large $n$ (where $k$ is allowed to vary). Then $c \leq n \implies c \mid n! \implies c \mid a^{n-1}+b^{n-1}=2^n$, so $2^k-2 \mid 2^n$ and thus $k=2$. Obviously $(a,b,c)=(2,2,2)$ only yields finitely many $n$ (since the RHS is never divisible by $5$), so this finishes the problem. $\blacksquare$ Remark: Honestly the hardest part of the problem (aside from not forgetting the powers of $2$ case) is following the observation that $p \mid a \implies p \mid b^{n-1}+c^{n-1}$ for size reasons and proving that $p \mid b+c \implies p \mid a^{n-1}$, which is in the same vein.
04.04.2024 14:38
Awesome problem. Suppose for contradiction that there are infinitely many solutions $(a,b,c,n)$ to the given equation. Sterling approximation gives that for sufficiently large $n$, we have $n!<(0.4n)^{n-1}$. Hence, we have $a,b,c < 0.4n$. Claim: $n$ is even for $n>2$. Proof. Suppose $n$ was odd. Then, $n-1$ is even. Note, $4\mid n!$ and at least one of $a,b,c$ must be even. If only one of them were even, say $c$, then $a^{n-1}\equiv b^{n-1}\equiv 1\pmod{4}$, which would give $n!\equiv 2\pmod{3}$, impossible as $n>2$. Hence, $2\mid a, b, c$. But then $2^{n-1}\mid n!$. However, we also have \[n \geq \frac n2 +\frac n4 + \cdots \geq 1 + \left\lfloor \frac n 2 \right\rfloor + \left\lfloor \frac n4 \right\rfloor + \cdots = v_2(n!)+1 \Longrightarrow v_2(n!) \leq n-1,\]and equality holds only if $n$ is a power of $2$, which contradicts the fact that $n$ is odd. $\blacksquare$ Claim: Each of $a+b, b+c, c+a$ are a power of 2. Proof. Suppose there exists an odd prime $p\mid a+b$. Then, since $n-1$ is odd, $p\mid a^{n-1}+b^{n-1}$, while $p\leq a+b< 0.8n$, we have $p\mid n!$. So, $p\mid n!-a^{n-1}-b^{n-1}=c^{n-1}\Longrightarrow p\mid c$. Since $p$ is an odd prime, it is not possible that $v_p(n!)\geq n-1$, as \[v_p(n!)=\left\lfloor \frac np \right\rfloor + \left\lfloor \frac n{p^2} \right\rfloor + \cdots < \frac np + \frac n{p^2} + \cdots = \frac n{p-1} \leq \frac n2 < n-1\]Hence, by LTE Lemma, \[v_p(a+b) + v_p(n-1) = v_p(a^{n-1} + b^{n-1}) = v_p(n!)\]Finally, note that since $a+b<0.8n$, we have that $a+b\mid (n-2)!$ which means $v_p(a+b) < v_p(n!) - v_p(n-1) - v_p(n)$ but we also have $v_p(a+b) = v_p(n!) - v_p(n-1) \geq v_p((n-2)!)$. We have arrived at a contradiction. $\blacksquare$ Suppose that $2\mid a,b,c$. We have $x, y, z$ integers such that $a=2x, b=2y, c=2z$. Then, $2^{n-1}\mid n!$ which forces $n$ to be a power of $2$, and also forces $x^{n-1} + y^{n-1} + z^{n-1}$ to be odd. Note, $x+y, y+z, z+x$ are all powers of $2$, which means either all three are odd or all three are even. All can't be even, so all are odd. Then, $x+y+z$ is odd, and since $2(x+y+z)\equiv 2\pmod{4}$ is also the sum of three powers of 2, it follows that one of $x+y,y+z,z+x$ is 2. Suppose $x+y=2$ then $x=y=1$, which means $a=b=2$. Plugging this, we get $c^{n-1}+2^n=n!$ but that means $\gcd(c,n!)$ is a power of 2, which is impossible unless $z=1$, which actually gives $a=b=c=2$, but we know there are no solutions $n!=3\cdot 2^{n-1}$. Now assume that two of $a,b,c$ are odd, say $a,b$ and $c$ is even. This means $b+c$ is an odd power of 2, which forces $b+c=1$, which is impossible. The proof is complete. $\blacksquare$
03.07.2024 17:43
See that $a$, $b$, $c \leq n$ and hence WLOG assume $n \geq 20$ and $a \geq b \geq c$. It is easy to check that we have \[n! \leq {\left(\frac{n}2 \right)}^{n-1} \implies a,b,c \leq \frac{n}2\]Claim: All $a$, $b$, $c$ are even and $n=2^k$ for some positive integer $k$. Proof: Assume all $a$, $b$, $c$ are not even then WLOG assume $a$ even and $b$, $c$ odd (with $b \geq c$). Then see that \[\nu_2(n!) \leq n-1 \implies \nu_2(n!) \leq \nu_2(b^{n-1}+c^{n-1})\]If $n-1$ is even then $\nu_2(b^{n-1}+c^{n-1})=2$, contradiction. Hence $n-1$ is odd but then we get \[\frac{n}2 \leq \nu_2(n!) \leq \nu_2(b+c) \implies \frac{n}2 \geq b \geq 2^{\frac{n}2-1}\]which isn't true. And so $a$, $b$, $c$ must be even and we must have $\nu_2(n!)=\nu_2(a^{n-1}+b^{n-1}+c^{n-1}) \geq n-1$ which is only possible when $n$ is a power of $2$, say $2^k$. $\blacksquare$. And so the equation writes itself as \[\left(2^k \right)!=a^{2^k-1}+b^{2^k-1}+c^{2^k-1}\]and see that any odd prime $q$ or $4$ cannot divide $\gcd(a,b,c)$ as it will run into $\nu_q$ or $\nu_2$ issues; which means \[\gcd(a,b,c)=2\]So say $p \mid a+b$ where $p$ is an odd prime and so $p \leq n \iff p \mid n!$ which means $p \mid c$. And so by LTE we have that \[\nu_p(a+b)+\nu_p(2^k-1)=\nu_p \left(a^{2^k-1}+b^{2^k-1} \right)=\nu_p \left((2^k)! \right)\]\[\implies \nu_p(a+b)=\nu_p \left((2^k-2)! \right) \geq \frac{2^k-2}{p-1}-\log_p(2^k-2)\]\[\implies 2^k \geq a+b \geq \frac{p^{\frac{2^k-2}{p-1}}}{2^k-2} \implies n^2 \geq p^{\frac{n-2}{p-1}}\]Note the function $f(x)=x^{\frac1{x-1}}$ is decreasing. Now if $p^2 \mid a+b$ then $p^2 \leq a+b \leq n \iff p \leq \sqrt{n}$ and so \[n^2 \geq n^{\frac12\cdot \frac{n-2}{\sqrt{n}-1}} \geq n^{\frac12\cdot \sqrt{n}} \implies 4 \geq \sqrt{n} \implies n \leq 16\]which is a contradiction to our original assumption. And so $\nu_p(a+b)=1$ which means \[1=\nu_p\left((n-2)! \right) \implies p>\frac{n}2-1 \geq c-1 \implies p \geq c \implies p=c\]which is a contradiction as $c$ must be even. This means that $a+b$ is a power of $2$ and so is $b+c$ and $c+a$ but now by IMO $2015/2$, we get that this has finite solutions.
30.11.2024 00:06
This problem was featured on the Bolivian IMO TST 2022 where everyone got absolutely cooked (kinda expected lol), only me and I think 2 or 3 ppl got partials on this one, now I come back with the require tools and insights to nail this . Claim 1: For large enough $n$ we have that $n! < \left( \frac{n-3}{2} \right)^{n-1}$ Proof: By AM-GM and the use of the largeness of $n$ to bump the exponent we have: \[ n!=1 \cdot 2 \cdot (3 \cdot \cdots \cdot n) < \left(\frac{n+3}{2} \right)^{n-2}< \left(\frac{n-3}{2} \right)^{n-1} \]Now FTSOC that there is infinitely many quadriples, note that $a,b,c$ are bounded by $n$ which means that the infinitude of solutions depends on $n$, so suppose we could have solutions for abritrarily large $n$. Claim 2: All odd large enough $n$ fail. Proof: Notice that $4 \mid n!$ here so take $\pmod 4$ to get that all $a,b,c$ are even, now this means that: \[ n-1 \le \nu_2(a^{n-1}+b^{n-1}+c^{n-1})=\nu_2(n!)=n-s_2(n) \implies s_2(n)=1 \implies n=2^k \]Which is a contradiction as clearly $k \ne 0$ and $n$ is odd. Claim 3: At least one of $a+b,b+c,a+c$ must have an odd prime divisor. Proof: Suppose FTSOC this isn't true then let $a+b=2^k, b+c=2^l, a+c=2^m$ for $k,l,m \ge 1$, note that all $a,b,c$ have to be even in this case else all are odd but $2 \mid n!$, now if $4 \mid a,b,c$ then we get $2n-2 \le \nu_2(n!) \le n-1$ which is a clear contradiction so at least one is $2 \pmod 4$, now notice from a similar thing to Claim 2 we are forced to let $n=2^{\ell}$ and also that the sum after dividing $2^{n-1}$ has to ne odd, which means either the other two are $0 \pmod 4$ or all are $2 \pmod 4$, the first case is imposible as it implies the powers of $2$ are just $2$ and then you get size contradiction so $a,b,c \equiv 2 \pmod 4$. Note that $k,l,m \ge 2$ or else two of $a,b,c$ at least are $1$ but that would force $c$ even and odd at the same time, so now consider that $2^k+2^l+2^m=2(a+b+c)$ so taking $\nu_2$ in both sides gives that $\text{min}(k,l,m)=2$, so WLOG its $m=2$, but so we have $a=c=2$ and thus $k=l$ and $b=2^k-2$ so we get $(2^{\ell})!=(2^k-2 )^{2^{\ell}-1}+2^{2^{\ell}}$ but here just take an odd prime $p$ with $p \mid 2^{k-1}-1$ (if $k=2$ we get finitely many sols so assume $k \ge 3$), then first note from Claim 1 we had stablished that $2^k-2<2^{\ell-1}$ therefore $p \mid (2^{\ell})!$ which means $p \mid 2^{2^{\ell}}$, a clear contradiction!. Now WLOG $b+c$ is the one with an odd prime divisors (at least), let it be $p$ and now suppose $p \not \; \mid b,c$, then notice that from Claim 1 we have $b+c<n-3$ which means that $p<n-3$ as well, now we continue. Claim 4: Such $p$ causes $n$ to have only finitely many solutions Proof: Clearly $p \mid n!$ so $p \mid a$ as well, now from LTE observe: \[\sum_{i=1}^{n} \nu_p(i)=\nu_p(n!)=\text{min} \{(n-1)\nu_p(a), \nu_p(b+c)+\nu_p(n-1) \} \; \text{or} \; (n-1)\nu_p(a)=\nu_p(b+c)+\nu_p(n-1)\]If the first case was true then as $b+c<n-1<n$ then both get absorbed by the sum so you would be forced to have $b+c=p$ or $\frac{n}{p-1}>\nu_p(n!) \ge (n-1)$ which is clearly not possible so we must have $b+c=p$ but in this case remember that $p \mid a$ and $a<\frac{n-3}{2}$ which means that $p<\frac{n-3}{2}$ but then $2p<n-3$ so this term is not eaten in the sum of $\nu_p$'s, a contradiction of size. And in the other case just note that one ends up having $2 \cdot \text{log}_3(n-1) \ge 2 \cdot \text{log}_p(n-1)>\nu_p(b+c)+\nu_p(n-1) \ge n-1$ which can't happen for large $n$, so contradiction as well!. Finish: Now if for any such odd prime $p$ we had $p \mid b,c$ as a result then clearly $p \mid a$ as well but then once again we have $\nu_p(n!) \ge n-1$ which we've seen that this can't happen so it's a contradiction as well. Therefore only finitely many solutions exist, thus we are done .