![\[x^4-(2\cdot10^{10}+1)x^2-x+10^{20}+10^{10}-1=0\]](http://latex.artofproblemsolving.com/b/9/d/b9d355433e896e8b97f28c2e4235140fd2348e77.png)
correct to four decimal places.
be a triangle with circumcircle 
.
and 
intersect at 
.
intersects the line 
at 
and 
is the midpoint of 
.
and 
intersect on 
be an integer, 
a real number, and 
be positive real numbers such that 
.![\[
\frac{1 + x_1^k}{1 + x_2} + \frac{1 + x_2^k}{1 + x_3} + \cdots + \frac{1 + x_n^k}{1 + x_1} \geq n.
\]](http://latex.artofproblemsolving.com/0/8/d/08de0c74a4e36b50a64d17875d3fd93eeb5b52de.png)
Y by tree_3, InvertedDiabloNemesisXD, centslordm, jhu08, megarnie, ImSh95, son7, sohere, Kingsbane2139, Supercali, Marshall_Huang, kiyoras_2001
Let 
be a positive integer. Find the number of permutations 
, 
, 
of the
sequence
, 
, 
, satisfying
.
Proposed by United Kingdom
be a positive integer. Find the number of permutations 
, 
, 
of thesequence
, 
, 
, satisfying
.Proposed by United Kingdom
This post has been edited 1 time. Last edited by Twoisntawholenumber, Jul 20, 2021, 9:36 PM
Reason: Added the country that proposed the problem
Reason: Added the country that proposed the problem
be the number of such permutations. If 
then the last inequality can't affect the rest 
)
.
with 
.
we must have 
and so 
must be a permutation of 
.![$[i+1,n]$](http://latex.artofproblemsolving.com/7/d/0/7d0029e63704229c38dee0be17cf7634aeb02fbc.png)
such that 
.
but this implies 
.
but this is a contradiction, and so we must have 
.
ways (there are no problems since 
)
.
and 
it follows that 
,
-
be the number of permutations which satisfy the property. We claim that 
,
is the 
Fibonacci number; defined as 
.
or 
.
for some integer 
.
must be given an index of less than 
;
for some index 
,
,
,
integers are in the permutation 
and the integer 
,
for some index 
,
.
,
,
for all non-negative integers 
.
which is less than or 
.
,
,
are divisible by this prime. However as 
and 
.
.
and 
,
.
and 
for some 
.
or 
.
,
.
and hence we can arrange the remaining terms in 
,
where 
is the 
,
,
.
,
,
,
permutations of the first 
,
.![\[a_{n-1}\cdot n\leq (n-1)\cdot a_{n-1}\leq n\cdot a_n\]](http://latex.artofproblemsolving.com/b/f/5/bf589dc96345cca212071f06f2b780b315babe2c.png)
thus, 
,
:
will satisfy 
,
.
for 
.
,![\[j\cdot n = j\cdot a_j \leq k\cdot a_k \Longrightarrow a_k\geq \frac{j\cdot n}{k}\geq j\]](http://latex.artofproblemsolving.com/2/d/2/2d29dae8415159c0b09a411763ed4e613a519479.png)
Thus,![\[a_j,a_{j+1},\ldots, a_n\geq j\]](http://latex.artofproblemsolving.com/5/d/1/5d164169298549aa5256bd06ddf06aae90ec6ff8.png)
Since these 
are distinct, 
must be some permutation of 
.
such that 
.![\[jn=j\cdot a_j\leq x\cdot a_x=xj\]](http://latex.artofproblemsolving.com/d/a/2/da21ccb53caba8caaac78b4d2f0b968f5fc3a64d.png)
Thus, 
so 
and 
.
for some 
.![\[n\cdot j=n\cdot a_n\geq y\cdot a_y = y\cdot (n-1)\geq (j+1)(n-1)=nj+n-j-1\geq nj+n-(n-2)-1=nj+1\]](http://latex.artofproblemsolving.com/c/1/8/c1882eb31c211dd4dd188015551779e3b2c00313.png)
Thus, 
,
,
,
and 
for 
are the Fibonacci numbers. We prove this by induction on 
being trivially true.
.
.
are elements of 
as that would contradict the given inequality. Therefore, 
is a permutation of 
.
to satisfy the inequality for 
,![\[ka_k=(k+1)a_{k+1}=\dots=na_n,\]](http://latex.artofproblemsolving.com/3/8/0/3806ac886fbd2c7d18769ac3477c0c4514fd9a25.png)
a clear contradiction when 
.
.
.
and 
.
,![\[ xn = xa_x \le ya_y \le na_y \implies a_y \ge x. \]](http://latex.artofproblemsolving.com/2/7/f/27f036a64f5fd954c2cf22d7e17b7a7d888ef758.png)
Therefore,![\[ \{a_{x+1},a_{x+2},\ldots, a_{n-1}\} = \{x,x+1,\ldots,n-1\}. \]](http://latex.artofproblemsolving.com/a/7/c/a7c59944a89b8556ae0008c8134dbcbfac3d201c.png)
In particular, 
for some 
.![\[ xn = xa_x \le za_z=zx \implies n \le z \implies z=n. \]](http://latex.artofproblemsolving.com/5/e/f/5ef6ebf916868cd02ed47a9291006232036cbdf9.png)
So 
.![\[ xn = xa_x \le \cdots \le na_n = nx, \]](http://latex.artofproblemsolving.com/7/f/5/7f5e3541414a0ea6f13146e344ec10d8192825f6.png)
so actually 
for all 
.
,
,
.
,
ways for the first 
ways for the first 
,
,
.
Fibonacci number.
be such a permutation.
,
for all 
.
,
hence 
,
.
hence 
,
as desired. But this is obviously impossible since 
.
,
,
,
.
,
,
and fixed points, and conversely every such permutation satisfies the condition.
then there are 
,
there are 
.
combine with the obvious fact that 
;![\[\{a_1, \ldots, a_{k - 1}\} = \{1, 2, \ldots, k - 1\}\]](http://latex.artofproblemsolving.com/4/b/0/4b094548a1f6fdee9a452cd3a9d18857a76771f2.png)
(this is true at the start 
)
for some 
.
,
,
or 
.
then we must have 
(or else 
)
and 
,
(corresponding to the cases where we place 
)
are the Fibonacci numbers.
then 
because 
because 
.
are 
numbers which are all greater than 
such values.
denote the total no of permutations satisfying the condition for n numbers.
first keep 
such permutations
which is 
which is indeed the 
Fibonacci number.
(the 
t
,
.
.
.
.
or 
.
for size reasons. Now note that 
.
,
for size reasons, so we have 
,
,
denote the total number of permutation of ![$[n]$](http://latex.artofproblemsolving.com/0/d/e/0deff9086fd7840ef23860f5bc924f1d4d2d2310.png)
with the given property.Let 
denote the number of permutation of 
denote the number of permutation of 
.
Now we will try to find out recursion for 
then 
.
.
so the above relation implies 
for 
.
[becoz size of both set are equal].
So indeed 
.
so 
.
.
because 
for size reason.
.
and 
implies 
.
and 
,
where 
,
,
,
to 
.
.
,
and so 
,
case. This contributes 
.
where 
.
is. Observe that this minimum element is at most 
elements from 
are forced to be some permutation of 
with 
,
for some integer 
.
,
,
,
.
be the number of ways to do so. The base cases are easy since
We do casework on the index of 
ways. If 
ways. I now prove that 
.
Hence 
But 
,
Meaning that there are at least 
,
denote the number of permutations of the set 
such that 
.
for all 
.
,
such permutations. Let 
.
.
,
.
.
and 
such permutations. Thus we have proved the claim.
and 
for all 
.
and 
.
.
.
.
where 
term of the recursion
Now, we first show via induction that 
for all 
.
.
for some 
.
we have
which violates the given condition. If 
then,
which is also impossible.
denote the number of permutations of 
and 
are easy to verify.
so that we have 
Observe that the maximum value in the inequality chain that can be attained by 
are 
which are all less than 
t
are forced to be after the 
at index 
Thus 
The minimum possible value it can attain is at the index 
in which we have 
Observe that 
for all integers 
Thus there exist no valid sequences when the index of 
otherwise the inequality immediately fails. For the remaining 
there are 
ways to arrange them in the inequality 
If 
ways to arrange the remaining 
to satisfy the inequality 
is a valid permutation iff 
. FTSoC suppose 
for some 
with 
so that 
.
,
Suppose 
,
as otherwise 
even if 
is strict as otherwise 
This is contradictive if 
so 
implying 
,
for any 
.
then there are 
,
and we have 
.
and 
,
,
through recursion, starting by noting trivial base cases 
and 
.
multiplication table such that each cell is in a distinct column and the entries are in weakly increasing order. We consider the number selected in the last column:
:
:
-
for 
:
to row 
rectangle of potential cells. Attempting to select 
,
,
be the number of permutations of 
such that ![\[a_1\le 2a_2\leq 3a_3\le\dots na_n\]](http://latex.artofproblemsolving.com/d/3/1/d31a7b95434f2455d3ff2c5ef48aeb960b95b23b.png)
,
,
and 
.
.
,
,
for 
.
possible permutations.
,
,
.
.
and 
.
for 
,
possible permutations.
.
,
.
.
)
.
.
.
,
.
.
,
,
.
and 
,
,
Fibonacci number (this can be checked by going upto 
)
for 
.
,
or 
.
,![\[ a_{k-1} (k-1) < (k-1)^2 \implies a_{k-1} < k-1 \implies a_{k-1} \le k-2.\]](http://latex.artofproblemsolving.com/f/1/4/f14c95fb7313d7d3032d684cc9ed18186db343fb.png)
If 
,
,
.![\[ a_{k-1} (k-1) \le k(k-3) < (k-1)(k-2) \implies a_{k-1} < k-2 \implies a_{k-1} \le k-3.\]](http://latex.artofproblemsolving.com/b/5/7/b5735673416a43ca1642ec686d51f19f0795a275.png)
This is a contradiction, so the only remaining cases to be checked are 
where 
and 
so 
.
where 
or 
such that we have a good permutation and 
else there is a value 
such that 
which does not happen in a good permutation.
value to be less than 
is 
by the rearrangement inequality. This sum equals 
which exceeds 
These cases are true, verified on paper (too lazy to type)
there are 
good permutations. Now consider 
the earlier terms are permuted in 
total ways to permute, completing the induction. Q.E.D.
,
.
spot, then the number of permutations is simply 
,
.
spot, then 
is forced to be in the 
spot, since 
.
,
.
.
spot, where 
,
,
,
is forced to be in the 
,
,
is the kth Fibonacci number.
be the set of valid permutations and let 
be the inversion map. We claim that for every 
,
has entries at most 1.
,
Then, for 
this implies that 
which is absurd given that
Clearly, the maximum number of swaps that can be made is 
.
be the number of permutations in 
One can easily prove using induction that this number is just 
are trivial.
valid sequences. If it is second to the end, we must have 
,
,
elements, giving another 
valid sequences. We now claim that 
,
,
,
,
.
,
,
,
,
since the elements located after 
,
be the number of permutations satisfying the statement. The answer is 
.
.
.
.
for 
,
.
and 
,
but 
for 
.
,
permutations for the other numbers and if 
permutations. Hence by the additive principle, 
as we wanted to show 
.
for all 
we must have that 
for all 
(easily derivable manually) so 
where 
is the 
and the rest is trivial.
where 
are trivial, so if the proposition holds for 
where 
then for 
suppose that 
with 
Then 
so all 
must have occured somewhere in 
with 
Therefore for the inequalities to hold 
so 
Hence equality holds so 
But 
Therefore 
and by the inductive hypothesis there are 
ways. But if 
by the inductive hypothesis there are 
ways. QED
