AoPS Academy
or 
. To avoid unfairly favoring specific company, the regulation ensures that if there have three cities 
and 
, with flight routes 
and 
operated by two different companies, then there must exist flight route 
operated by the third company different from and .
, 
and 
denote the number of flight routes operated by companies and , respectively. It is known that, starting from a city, we can arrive any other city through a series of flight routes (not necessary operated by the same company). Find the minimum possible value of 
.
is a positive integer. Determine all functions 
such that![\[f(x^{n+1}+y^{n+1})=x^nf(x)+y^nf(y),\forall x,y>1.\]](http://latex.artofproblemsolving.com/a/4/7/a47d53806f2148cc3339335fb990b33641085896.png)
be a fixed integer. Find the least constant such the inequality![\[\sum_{i<j} x_{i}x_{j} \left(x^{2}_{i}+x^{2}_{j} \right) \leq C
\left(\sum_{i}x_{i} \right)^4\]](http://latex.artofproblemsolving.com/d/d/e/dde2d1dd0c412d8ba640f1d4c044e2fa2dcccc82.png)
(the sum on the left consists of 
summands). For this constant , characterize the instances of equality.
, let 
be the least prime that does not divide 
, and define 
to be the product of all primes less than . In particular, 
For having 
, define 
. Consider the sequence 
defined by 
and ![\[ x_{n+1} = \frac{x_n p(x_n)}{q(x_n)} \]](http://latex.artofproblemsolving.com/8/2/5/825be3bbef6a29de69aead03392ca7215093f320.png)
for 
. Find all such that 
.
for which there exist infinitely many positive integers 
such that ![\[ \frac{a^m+a-1}{a^n+a^2-1} \]](http://latex.artofproblemsolving.com/2/8/a/28a68e409451bbdcaee7c1286341f6aeea9ffdad.png)
is itself an integer.
I have another finish to this problem which I feel is slightly cleaner:
, 
. Therefore, 
. Hence, 
, so 
. But it was have shown that 
, so we have that 
. Therefore, 
, so 
. The only way this can be is if 
, yielding 
and 
, as desired.
has no double root. But it is easy to see that 
(not hard, I can show this more explicitly). Now let 
be a root of 
. Then 
.
. Dividing these equations and rearranging gives 
. But this holds for all roots , so we get that 
, where 
. By a rather famous result, 
is irreducible for all , so if we reverse the coefficients, 
is also irreducible. Therefore, 
. is irreducible in the beginning and much more later.
. . We let 
and 
, we have since both polynomials are monics, we can use Euclidean theorem for monic integer polynomials, to conclude that there is ![$S,R\in \mathbb{Z}[x]$](http://latex.artofproblemsolving.com/d/3/b/d3b22aeb20f625ce47ce695ff2d953935f174eed.png)
where 
, such that 
, we have then ![\[ f(x) = \frac{x^m+x-1}{x^n+x^2-1} = \frac {P_m(x)}{Q_n(x)}= S(x) + \frac{R(x)}{Q_n(x)} \]](http://latex.artofproblemsolving.com/5/8/2/58258a385b32885efba4f16c76a775a8624dbe55.png)
If 
is non-zero, We get the 
, which imply that for all but finitely many integers 
, 
. And as that term never achieves zero for large numbers, we can't have integer for infinitely many 's. So we must have 
in ![$\mathbb{Z}[x]$](http://latex.artofproblemsolving.com/4/b/7/4b7d768fffbb7a1a6163af392ed348f2d49d8783.png)
. Easily one can see that we must have 
. iff 
. We do module arithmetic in the Euclidean domain ![$\mathbb{Q}[x]$](http://latex.artofproblemsolving.com/3/d/9/3d963b0224d7c8b822ad2df9d699fd043f0013e8.png)
to prove that. Note that 
and 
in , and hence ![\[ \begin{array}{lcl}
x^m+x-1 & \equiv & 0 \pmod{x^n+x^2-1} \\
\iff x^m+x-x^n-x^2 & \equiv & 0 \pmod{x^n+x^2-1} \\
\iff x^{m-1}+1-x^{n-1}-x & \equiv & 0\pmod{x^n+x^2-1} \\
\iff x^{n-1}(x^{m-n} - 1) + (1-x) & \equiv & 0 \pmod{x^n+x^2-1} \\
\iff x^{m-2} + \cdots + x^{n-1} -1 & \equiv &0 \pmod{x^n+x^2-1}
\end{array}\]](http://latex.artofproblemsolving.com/2/9/5/29555ec4b3caf00be5e4b410ccef452d342a7964.png)
we get
we get 
which cannot happen unless 
and 
and hence 
and so we have the solution 
. Now if 
, then ![\[ \begin{array}{lcl}
x^{n-1} + x - x^{i} - x^{i-1} & \equiv & 0 \pmod{x^n+x^2-1} \\
\iff - x^{n-1} - x + x^{n+j} + x^{n+j-1} & \equiv & 0 \pmod{x^n+x^2-1} \\
\iff x^{n+j-1} + x^{n+j-2} - x^{n-2} - 1 & \equiv & 0\pmod{x^n+x^2-1} \\
\iff x^{n-2}(x^{j+1}-1) + x^{n+j-2} - 1 & \equiv & 0 \pmod{x^n+x^2-1} \\
\iff x^{n+j-2} + 2x^{n+j-3} + \cdots + 2x^{n-2}+ x^{n} + \cdots + 1 & \equiv &0 \pmod{x^n+x^2-1}
\end{array}\]](http://latex.artofproblemsolving.com/8/c/c/8cc10c3be0a0b6cc79ad13462c0b2bc6b87b9999.png)
for 
, while 
for some 
since divisibility applies also in ![$\mathbb{R}[x]$](http://latex.artofproblemsolving.com/a/8/8/a88b9f4858016b1771635c611d44b56161a08009.png)
, we get 
, getting a contradiction.
since 
implies that if 
, then 
for relatively large. First we claim that 
must always be an integer. Indeed, since 
for polynomials 
, with 
, implying that for large , 
occurs, meaning that the quotient cannot yield an integer unless 
for infinitely many values, implying the above claim. Now we can bound. Since
, we get that 
.
.. Hence, , so . Plugging in 
, we immediately get 
with 
. Then 
. Since 
and 
is odd, 
. This rearranges to 
for 
. Since 
, 
, implying the only solution to be 
.
dividing 
as polynomials. The big step is the following analytic one.
.
and let 
be the unique real number with 
, hence 
. But now 
As 
and 
, this is a contradiction 
. 
The right-hand side has degree 
, and the leading coefficients are both 
. So the only possible situations are 
The former fails by just taking 
; the latter implies . As our work was reversible, this also implies works, done.
for which there exist infinitely many positive integers such that is itself an integer.
as polynomials, by the given condition. Now the former has different signs at 
and 
, so pick a root 
. Notice that 
and 
. Suppose 
. Then 
which is a contradiction!. Now 
by taking residues. Finally, the latter polynomial has degree 
so in fact, these two polynomials are equal, hence 
so 
. Clearly, this pair works, so we're done.
to divide 
.
.
Suppose otherwise, we have .
and 
. By the Intermediate Value Theorem, we have that the polynomial has a root 
which satisfy 
. Therefore,![\[ \alpha^m + \alpha = \alpha^n + \alpha^2 \Rightarrow \alpha (1 - \alpha) = \alpha^n (1 - \alpha^{m - n}) = (1 - \alpha^2)(1 - \alpha^{m - n}) \]](http://latex.artofproblemsolving.com/8/3/b/83b747f526ef4de754f19ad3e57cd471aaec5f29.png)
This gives us![\[ \alpha = (1 + \alpha)(1 - \alpha^{m - n}) \]](http://latex.artofproblemsolving.com/9/1/c/91c1f27dcaa10393e467b8a7d744ff322a3e6116.png)
which can be rewritten as 
. Since 
and . We have![\[1 = \alpha^{m - n} + \alpha^{m - n + 1} \le \alpha^n + \alpha^{n - 1} \le \alpha^n + \alpha^2= 1\]](http://latex.artofproblemsolving.com/6/a/4/6a42b64eac3eb47c5a345aeff4361ef5756ba4ae.png)
results to a clear contradiction.![\[ x^n + x^2 - 1 | x^{m - n + 2} - x^{m - n} - x + 1 \]](http://latex.artofproblemsolving.com/2/5/4/254b7f1d7bf8d36d5054b43bf3b7b0093b078b13.png)
Notice that we have the bound 
.
.
since they are both the polynomial in the same degree and both having leading coefficient 
, which is a clear contradiction as 
has constant and 
has constant 
..![\[ (x^n + x^2 - 1)(x - 1) = x^{n + 1} - x^{n - 1} - x + 1 \]](http://latex.artofproblemsolving.com/3/6/f/36fb0cc62f6d2b7dfe4df1e102c2c84a03b56f65.png)
But taking 
. We have 
since 
.
. This forces 
, and we could check that![\[ (x^3 + x^2 - 1)(x^2 - x + 1) = x^5 + x - 1 \]](http://latex.artofproblemsolving.com/a/6/9/a690317653a650a6adcd420a253f9c9ec43e8922.png)
Therefore, the pair 
clearly satisfies.
, we have![\[a^n+a^2-1\ |\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right)\]](http://latex.artofproblemsolving.com/c/3/d/c3dad3018beab9c04ebb5e6a5583fc5739cf5e11.png)
. For 
, it is true. So assume for some 
, it is true.![\begin{align*}
a^n+a^2-1\ &|\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right)\\[1em]
\implies a^n+a^2-1\ &|\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right) - (-1)^i(a^n+a^2-1)\\[.5em]
&=a^{m-i} + (-1)^i\left(-a^n+ a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^{i+1}(a^2-a)\\[1em]
\therefore a^n+a^2-1\ &|\ a^{m-i-1} + (-1)^{i+1}\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^{i+1}\left(a-1\right)\\
\end{align*}](http://latex.artofproblemsolving.com/3/7/f/37f21341a5229d3e78c208aa802149c21241ac34.png)
Which proves our lemma.
, we get,![\[a^n+a^2-1\ |\ a^{m-n} + (-1)^n \left(\frac{a^n+1}{a+1}\right) + (-1)^n(a-1)\]](http://latex.artofproblemsolving.com/2/a/f/2aff9295048db08e8da003e5c81b1515754badf0.png)
Clearly, 
. Let 
. If 
is even,![\begin{align*}
a^n+a^2-1\ &|\ a^{m-n}+a-1 + \left(\frac{a^n+1}{a+1}\right)\\[.5em]
\implies a^n+a^2-1\ &|\ a^q+a-1 + k\left(\frac{a^n+1}{a+1}\right)
\end{align*}](http://latex.artofproblemsolving.com/d/9/7/d973296d7d080dd48307dfacdc7ea85d5a3ec62d.png)
, and can't be 
for all 
. is odd. Then we have,![\begin{align*}
a^n+a^2-1\ &|\ a^{m-n} + a-1 - \left(\frac{a^n+1}{a+1}\right) - 2(a-1)\\[.5em]
\implies a^n+a^2-1\ &|\ a^q + a -1 - k\left(\frac{a^n+1}{a+1}\right) -2k(a-1) = P(a)
\end{align*}](http://latex.artofproblemsolving.com/b/1/d/b1d64365f9973539295f50051c44fb24d536407a.png)
has degree at most , 
for all .
. Which gives us the only solution 
.
, else the remainder (which is deg 
at most) will eventually be smaller than for large enough 
otherwise 
for 
and obviously one of the roots has this value. So then the remainder is 
so we want 
which must be equal to or 
as 
For size reasons 
or 
. The first case fails by comparison of coefficient, and the second case requires 
, which gives us 
fixing 
works.
which I can't find above, given that we already know 
has to divide 
.
, and one divides the other, so it is impossible for them to have different signs for some . Consider 
. 
since 
. On the other hand, 
. The first part of the product is 
and since 
, the second part of the product is 
. Thus this is 
, giving the desired contradiction.
and 
be polynomials in ![$\mathbb Z[x]$](http://latex.artofproblemsolving.com/b/d/c/bdc78abe277078318648d69381180248b72777be.png)
. We claim that works.
holds always.
we do polynomial division with quotient and residue in 
From here note that 
so set to be a extremely large positive integer such that 
meaning that for infinite values is 0 so 
holds always meaning that as desired.
are also roots of 
now 
if hence is strictly increasing in 
, now 
and 
meaning that there exists a root of satisfying 
. then by all said before and ineqs
Contradiction comes from assuming hence as desired.
From here as RHS has at most degree we see that both have to be equal and 
hence 
which means and this means 
. is the unique pair that works, thus we are done 
is the only solution. One can see that it works as![\[a^5+a-1=(a^2-a+1)(a^3+a^2-1).\]](http://latex.artofproblemsolving.com/9/3/3/93350360c093da87c8aa91cfc00beee9113f0cfc.png)
We will break the solution into two claims which will bound the values of 
. We define 
where 
are polynomials. We will now prove a well-known but extremely useful lemma which will take the problem from Number Theory to Algebra!![$f,g \in \mathbb{Z}[x]$](http://latex.artofproblemsolving.com/9/6/0/9604fca9608988d718f3dcf1e89eaaff86d5805a.png)
are such that 
for infinitely many integers , then 
.
. By the division algorithm over , write 
for ![$f,q \in \mathbb{Q}[x]$](http://latex.artofproblemsolving.com/9/8/c/98cf5266b2e715a5913e61997d44de7e6fa9b01d.png)
and 
. One can clear out the denominators by multiplying by suitable integer, so we assume that all the polynomials are in . Just pick huge 
such that 
. It would actually mean that 
. But since , we must have 
as desired. 
.
. The algebra for divisibility begins here 
Bringing this into divisibility condition, we get 
Due the bound on the degree, we get 
which on simplifying gives as desired.
.
. By the Intermediate Value Theorem, there exists a real root of 
which lies between 0 and 1. Let this root be . By the problem condition, is also a root of 
. Now 
and 
gives the following 
Now we compute 
and 
. 
By assumption, we must have 
. Plugging in the values, we get 
where 
is the golden ratio. We will now show that 
which would bring the desired contradiction. It is easy to see that is an increasing function in the interval ![$[0,1]$](http://latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
. Note that 
and we can conclude that and we are done with the claim.
. Putting this in 
we get![\[a^n+a^2-1 \mid a^{n-1}-a^2.\]](http://latex.artofproblemsolving.com/7/3/5/7355fb5b7bbe77b634c35a8c1b4edde692e016eb.png)
This forces and we are done. 
.
.
impossible.
, none of which work.
, and checking the possible n, only 
works.
, none of which work by looking at deg LHS<deg RHS except for a few n, and checking those don't work. Having exhausted all cases, we conclude the proof here.
only, which clearly works since 
in the polynomial sense. We now prove this is the only one.
, since is monic we can write
for some ![$p,q \in \mathbb{Z}[x]$](http://latex.artofproblemsolving.com/b/3/c/b3c5451e859f4bd79c10f4705ff7478c36e521a3.png)
and 
. Then by considering sufficiently large we require 
, so we should have 
in the polynomial sense. Note that both of these polynomials have exactly one positive real root, so they must be the same. Call this common root ; clearly 
..
On the other hand, since 
but 
, this is impossible, since 
increases as gets closer to 
. 
with 
(since clearly 
). We should have
Since 
(in the polynomial sense) it follows that 
. In general 
is a nonzero polynomial, so 
is impossible, hence 
and 
. The last polynomial has degree less than , hence it must be zero, i.e. . Thus we extract the claimed solution. felt "intuitive" but it's not super motivated in itself. I guess you start thinking about the roots after divisibility, and these are mostly hard to pin down except .
.. It's not hard to see that 
. Let be a real root of 
. Then is real root of 
. Thus 
, which is equivalent to 
., then 
, a contradiction. Thus .
, thus 
. Since 
, thus 
or 
. In the first case we have 
, which is impossible. In the second case we have 
, thus . Thus . Therefore is only answer. 
, then the polynomial divides the polynomial . Note that 
implies 
. In particular, 
.
, which implies 
. This becomes 
. Note that 
so 
. This implies 
. This also means 
.
for which 
. We must have 
. Setting them equal, we get![\[r=\frac{r^n(1-r^{m-n})}{1-r}=\frac{(1-r^2)(1-r^{m-n})}{1-r}=(1+r)(1-r^{m-n})\]](http://latex.artofproblemsolving.com/8/1/9/8193a0d906ff3cb41eb1dbcef2e69b92319300b1.png)
and this becomes 
which implies 
so 
. Note that equality is dependent on 
, so we need which works.
. be a root of 
, such that 
. Suppose for the sake of contradiction that . Then,
On the other hand, 
and 
, so this is a clear contradiction. 
In particular, as 
, we have 
If 
, then the RHS is clearly smaller and 
, which is clearly impossible.
, perform one more step to get 
As 
, the RHS is smaller than the LHS now, so it must uniquely equal zero. When 
, we get 
, giving the solution pair 
. When 
, we get 
, which does not work for any value of . Thus, is the only solution.
. Our condition, 
, can be rewritten as![\[D \mid a^{m-n}\left(a^n+a^2-1\right) - \left(a^m+a-1\right) \implies D \mid a^{m-n+1}+a^{m-n}-1.\]](http://latex.artofproblemsolving.com/3/6/d/36dec78be151ddd2026641de9b1c7b7d40a27007.png)
, and investigating 
gives the desired solution. Now assume FTSOC , and consider a root of 
. Then![\[\left(a^n+a^2\right)^2 - (a^m+a) = 0 \implies a\left(2a^{n+1}+a^3-1\right) = a^m-a^{2n}.\]](http://latex.artofproblemsolving.com/a/e/1/ae14e7109cd2ce6c3164a5912f1cd13a6676447c.png)
![\[a\left((a^{n+1})+a(a^n+a^2)\right)-(a^n+a^2) = a(1-a)(a-a^n) > 0. \quad \blacksquare\]](http://latex.artofproblemsolving.com/5/4/e/54ec5193edebaf6dbc22ffcabf73ef18ed34b78e.png)
be the enumerator and 
be the denominator. Divide on :
where 
and division is done in 
. Multiply this equation by the lcm of denominators so that all coeffiecients were integer. Now 
is divisible by and 
are divisible by in infinitely many points from the problem statement, thus 
is also divisible by in infinitely many points. But if 
, then eventually 
, so 
must be equal to zero. Hence is divisible by 
, but 
, thus 
. Denote 
deg 
. Note that 
and 
, thus there exists a number 
such that 
. Then 
. Note that if 
, then 
and 
, contradicting the statement. Thus 
. But 
, thus 
, and 
then there is a remainder term which is eventually always smaller than the denominator, giving non integers. Thus 
. Rearranging, 
so 
. Now let be a root of with which exists by IVT. Then 
which is between 
and . However 
as otherwise 
. Thus 
. Together we have , which implies 
, so 
is the only solution.
such that 
Let be a real root to 
. This exists by IVT. Hence, we must have that 
I claim that 
Rearranging, we have that 
Hence, 
Now, assume for the sake of contradiction, that 
It follows that 
Thus, we have that 
Hence, since 
we have that the degree of the LHS is 
Hence, it must be 
and so 
Hence, the only solution is 
only.
,
not identically zero. Then by the conditions, 
.
and 
,
has a root 
.
,
.
.
,
or else 
,
.
.
is not identically zero, and since 
is either 
or 
.
,
,
,
.
,
.
,
.
and 
,
has a root 
.
,
.
.
,
or else 
,
.
,![$Q,R\in\mathbb{Z}[x]$](http://latex.artofproblemsolving.com/f/1/a/f1aee26e7c59551a1732ef45478565b47537ed34.png)
and 
.
,
must be an integer for infinitely many positive integers 
,
,
.
is a polynomial identity.![$\mathbb{Z}[\sqrt2]$](http://latex.artofproblemsolving.com/3/8/b/38b7f00d6aa0eb368303c97dc7f11300d18ff7f3.png)
.
to get 
in 
is an integer, so it must divide 
,
or 
.
,
.
and 
for some integer 
.
.
.
.
is 
and the absolute value of the norm of 
is of the form 
.
,
,
,
and thus 
.
.
.
is of the form 
.
with equality iff 
,
for 
and 
with 
.
.
is irreducible and is not 
.
and
Now pick a root 
,
and
such that 
, hence we may safely conclude that 
,![$$X^n-X-1 \text { is irreducible in } \mathbb{Z}[X]$$](http://latex.artofproblemsolving.com/6/e/9/6e96d6f48c84bea74469b761df351c6d9414ebf0.png)
![$$\implies X^n+X^{n-1}-1 \text { is irreducible in } \mathbb{Z}[X]$$](http://latex.artofproblemsolving.com/e/f/8/ef8dff554ec3a585f2a7d99822b2335a82df4a79.png)
is irreducible, we conclude,
.
where the degree of 
is an integer, so 
.
and 
and 
are increasing, this means that 
.
.
Therefore, this means that 
,
.
Therefore, by the Intermediate Value Theorem, 
.
.
Therefore, we must have 
,
.
,
,
.
,
and 
.
.
,
,
,
,
.
,
,
,
.
.
gives 
,
,
,
.
,
.
,
,
,
and 
.
,
.
,
,
.
.
where 
,
suppose FTSOC 
then
which is cap thus 
.
Thus 
.
then 
then 
must be equal to 
by considering coefficients however 
so 
therefore 
so