AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
be reals such that 
. Prove that
and 
satisfies the following recursion formulas: 
, 
and 
. Find 
and 
, an arbitrary point 
is chosen on the side 
. In triangles 
and 
, the angle bisectors 
and 
are drawn, respectively. The point 
is the circumcenter of 
. Prove that the second intersection point of the circumcircles of triangles 
and 
lies on the line 
.
+1 w
such that ![\[f(f(x)f(y))=f(xf(y))+f(y)\]](http://latex.artofproblemsolving.com/4/f/4/4f40c133524db64428861c756773ee25659d048a.png)
for all integers 
and 
.
satisfying 
Prove that 
When does equality hold?
be a prime number and 
an integer polynomial of degree 
such that 
and 
is congruent to 
or 
modulo for every integer 
. Prove that 
.
such that 
is an integer for all 
, where 
are all the positive divisors of 
.
be three positive reals such that 
. Prove that![\[ \frac { x^5-x^2 }{x^5+y^2+z^2} + \frac {y^5-y^2}{x^2+y^5+z^2} + \frac {z^5-z^2}{x^2+y^2+z^5} \geq 0 . \]](http://latex.artofproblemsolving.com/a/1/4/a14adf0f1e35df57c734c7df701d5a67da22dc3c.png)
real numbers 
, we can select a real number 
and transform the sequence into 
. This transformation can be performed multiple times, with each chosen real number potentially being different
where 
are lengths of parallel sides and 
are other two sides.
be a cyclic quadrilateral. Let 
, 
, 
be the feet of the perpendiculars from 
to the lines 
, 
, 
, respectively. Show that 
if and only if the bisectors of 
and 
are concurrent with 
.
compute the smallest possible value of ![\[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\]](http://latex.artofproblemsolving.com/5/6/2/562c27c7779285b6439c4087f52933a41f29ee2e.png)
over all permutations 
of 
. Suppose 
where 
. Then we may assume 
-- otherwise by swapping and 
the sum will not increase, as 
imply 
and 
. Analogously we may assume 
, 
and so on up to 
. Now if 
, then 
are a permutation of 
, so overall we have ![$f(n) = \min_{1\leq k \leq n} \left[f(k-1) + \left\lfloor \frac{n}{k} \right\rfloor\right]$](http://latex.artofproblemsolving.com/d/4/6/d46ae731968b53499dd01e3e73effe695a002349.png)
(conventionally treating 
). To deal with this painful recurrence, calculate up to e.g. 
(or 
if you have time and nerves) in order to suspect 
which we shall prove by induction!
is immediate. For the induction step we have to show 
for all 
and that equality is attained (we omitted 
since then the recurrence yields 
). Write 
and 
where 
, 
and observe that 
since 
and 
would imply 
, contradiction! The inequality becomes 
. The left hand side is minimal for 
minimal and 
maximal, so we reduce to 
, which is true since and 
holds for all 
by a trivial induction (and clearly for 
as well). Equality holds e.g. for 
and 
(note that this value for is indeed in ![$[1,2^{s-1}]$](http://latex.artofproblemsolving.com/d/4/2/d42e72b84bec1347787ab75cebde783a2116d102.png)
).
. We first bound, then give a construction.
minimal, such that 
for all 
. Suppose otherwise 
, then there exists 
such that 
. Swap 
then the change in the sum is
. Suppose 
and 
, then we pick 
such that
exists because there are 
values of such that 
. The largest of them is at least 
as 
.
. The difference is
and may or may not have added a smaller term 
.
, then the answer is merely 
.
. It's clear that 
for all .
, then 
.
. Letting denote the answer, we prove this by induction on 
. and 
are easy. For 
, consider a permutation 
with minimal sum and let 
denote the position of , meaning we have an expression ![\[ f(n) = \dots + \left\lfloor \frac{\bullet}{t-1} \right\rfloor + \left\lfloor \frac nt \right\rfloor + \left\lfloor \frac{\bullet}{t+1} \right\rfloor + \dots + \left\lfloor \frac{\bullet}{n-1} \right\rfloor + \left\lfloor \frac{\bullet}{n} \right\rfloor. \]](http://latex.artofproblemsolving.com/e/8/a/e8ac9a5fd51bf60df521714ab3066d4addf51606.png)
Then we can make the following 
transformations without increasing the value of the right-hand side:
into the th floor (i.e.\ the last term)
into the 
st floor (i.e.\ the second-to-last term) into the 
st floor (i.e.\ the term after 
).
So we just need the value of that minimizes the right-hand side. This is split into two cases:
, we have ![\[ f(n) \ge \left\lfloor \log_2 \left( \left\lceil \frac{n+1}{2} \right\rceil - 1 \right) \right\rfloor + 2 = \left\lfloor \log_2 n \right\rfloor + 1 \]](http://latex.artofproblemsolving.com/5/c/f/5cfce5b6a2b8bb70ca0d063a9b12fda89414c3cf.png)
with equality if 
.
, then we do an extremely annoying calculation to prove ![\[ \left\lfloor \log_2(t-1) \right\rfloor + \left\lfloor \frac nt \right\rfloor \ge \left\lfloor \log_2 n \right\rfloor \qquad (\diamondsuit). \]](http://latex.artofproblemsolving.com/5/1/a/51ae532db2a43ee6d5253e1d6dd05ac5915a94e7.png)
We will twice use the fact that 
for all 
, which we denote 
. If is not a power of 
, then 
and 
If we are unlucky and 
, then instead let 
, with 
and 
. The main insight is that 
, so ![\[ (\diamondsuit) \iff (e-1) + q \ge \left\lfloor \log_2(2^eq + r) \right\rfloor = \left\lfloor \log_2(2^e q) \right\rfloor = e + \left\lfloor \log_2 q \right\rfloor. \]](http://latex.artofproblemsolving.com/2/b/1/2b1ddd6121baa10538319f477c3a9a453aa8b84c.png)
Thus it suffices to show 
which is .
. Let be such that 
. We want to prove that the given sum is 
.
, which easily rearranges to what we wanted to prove 
, since both sides are integers.
and in general
.
and
groups in total and in each group, the sum of the floors is equal to 
, so in total the sum is equal to , as we wanted.
, find the smallest value of 
over all permutations 
of 
.![\[\{\vec a=(a_1, \dots, a_n)\}=S_n\subseteq\mathbb R^n\]](http://latex.artofproblemsolving.com/1/2/b/12bd7efbdc6d4f150715f6e450dc8aa751dceb97.png)
be the set of all permutations of . (Technically, the set of all images of all permutations.) Let ![\[f_n(\vec a)=\sum\limits_{i=1}^n\left\lfloor\frac{a_i}i\right\rfloor\]](http://latex.artofproblemsolving.com/0/c/a/0cace9383285fee77126aad038bedd51eadbea3c.png)
and ![\[g(n)=\min\limits_{\vec a\in S_n}f_n(\vec a).\]](http://latex.artofproblemsolving.com/1/2/3/123d321925d1246a23bc34aa9a786ccf2761b06d.png)
We claim that ![\[g(n)=\lfloor\log_2(n)\rfloor+1.\]](http://latex.artofproblemsolving.com/3/4/8/3482de9d9acd338213466998cafab376b06726a5.png)
by induction on 
. For the base case 
, obviously 
. Assume that 
for all such that 
. Now consider those such that 
. Indeed, we can assign 
Then 
where 
is the projection of 
, the map ![\[\mathbb R^n\supseteq S_n\stackrel{\phi}{\twoheadrightarrow}\left\{\vec{a'}=\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}\right)\right\}\subseteq\mathbb R^{\left\lfloor\frac n2\right\rfloor}\]](http://latex.artofproblemsolving.com/a/5/9/a5979440bf67d3295ecf273c568e1376d07e92b8.png)
is defined by ![\[\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}, a_{\left\lfloor\frac n2\right\rfloor+1}, \dots, a_n\right)\stackrel{\phi}{\twoheadrightarrow}\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}\right).\]](http://latex.artofproblemsolving.com/b/f/9/bf90e026e7d866f3806cd04491680a19c085e0cc.png)
Hence 
By induction hypothesis, there exists ![\[\vec{a'}\in \left\{\vec{a'}=\left(a_1, \dots, a_{\left\lfloor\frac n2\right\rfloor}\right)\right\}\]](http://latex.artofproblemsolving.com/9/e/1/9e15bc6ced206dce48293130a6baba376d627724.png)
such that ![\[f_{\left\lfloor\frac n2\right\rfloor}\left(\vec{a'}\right)=\left\lfloor\log_2\left\lfloor\frac n2\right\rfloor\right\rfloor+1=k+1,\]](http://latex.artofproblemsolving.com/d/2/6/d26e385d26b8636717ef8f5297a0d2cd01dff651.png)
so ![\[g(n)\le k+2.\]](http://latex.artofproblemsolving.com/c/0/8/c081252d15f7ef9e1468e462116da3444502732b.png)
![\[f_n(\vec a)\ge\lfloor\log_2n\rfloor+1\forall\vec a\in S_n\forall n.\]](http://latex.artofproblemsolving.com/d/5/d/d5d82c2eecc00adb5a97d3df7de9a19cad9d1597.png)
achieves its minimum when 
.
and 
. Then we can compute 
But the value must be integral, hence ![\[f_n\left(\left(a_1, \dots, a_{i_1-2}, a_{i_1-1}, a_{i_2}, a_{i_1+1}, a_{i_1+2}, \dots, a_{i_2-2}, a_{i_2-1}, a_{i_1}, a_{i_2+1}, a_{i_2+2}, \dots, a_n\right)\right)-f_n\left((a_1, \dots, a_n)\right)\ge 0.\]](http://latex.artofproblemsolving.com/0/5/7/05728f2cdd803d969996d3fb09f5021e00197259.png)
where the base case is vacuously true. Assume that 
for those such that 
. Then we now consider those such that 
. Indeed, by Claim 1, it suffices for us to consider the cases when , so, we have 
, which is what we wanted.
. If 
for 
, then let the permutation be 
The only for which 
is when is a power of , and 
, so 
. Therefore, the sum is equal to in this case. Now, we will show that 
by induction on .
.
. Then, we have
since 
is a permutation of 
. Therefore, if 
then we have proven the inductive step. If 
, then we have 
If 
then 
, as desired. Otherwise, 
Suppose that 
where 
and 
. Then, 
, so this expression is at least 
since 
. As 
is a permutation of 
, this means that this expression is at least 
, as desired.
over all permutations of 
is 
.
We inductively construct 
the base case is easy. For the inductive step,
terms a permutation of 
This gives a sum of 
th term be 
This adds 
for all 
This adds nothing to the sum.
so our induction is complete.
Induct on 
the base case is clear.
be such that 
By the inductive hypothesis, ![\[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\ge\sum_{k=1}^{m}\left\lfloor\frac{a_k}{k}\right\rfloor\ge(\lfloor\log_2(m-1)\rfloor+1)+\lfloor n/m\rfloor=\left\lfloor\log_2\left(\frac{n}{\lfloor n/m\rfloor+1}\right)\right\rfloor+(\lfloor n/m\rfloor+1).\]](http://latex.artofproblemsolving.com/0/0/e/00eceefea3c124962a9d0dc9d346965fdd308595.png)
If 
increases by 
then the first term increases by at most while the second term increases by 
Thus, it is always optimal for to be This gives the desired bound of ![\[\lfloor\log_2(n/2)\rfloor+2=\lfloor\log_2(n)\rfloor+1.\]](http://latex.artofproblemsolving.com/d/d/3/dd312daacba620cce033b4cc45071fe4ae1423ea.png)
.![$i\in[n]$](http://latex.artofproblemsolving.com/e/d/d/eddf7b37f39f32e513c09400509bc039e19a0e17.png)
, choose 
whenever 
or 
is a power of . Otherwise choose 
.. The base case is clear. Let be the minimal value of 
over all permutations of 
. It suffices to prove that 
whenever 
. be a positive integer. Let 
be pairwise distinct positive integers. Then 
and if 
then the inequality is strict.
such that 
. For each let 
. Hence 
and
Obviously 
. If then 
so we obtain a strict inequality. 
. Pick any permutation of . Let 
. Let ![$t\in[n]$](http://latex.artofproblemsolving.com/9/6/9/96957687fe06a70ab3b40070391ef17a9bc1204d.png)
be the element such that 
. We consider two cases.
. Then by the claim above we have
. Then 
. Therefore, by the claim above,
, as desired.
. We show that 
for all naturals . Note that 
. It suffices to show that for all naturals , we have 
and 
. We show the former.
achieves 
. Extend 
to 
as![\[\pi(k) = \begin{cases} \sigma(k) & 1 \le k \le n \\ 2n & k = n+1 \\ k-1 & n+2 \le k \le 2n \end{cases}\]](http://latex.artofproblemsolving.com/1/f/1/1f1ec6fb5f8e36fdda2c1387de484c54e379ba2f.png)
Then ![\[\sum_{k=1}^{n}\left\lfloor\frac{\pi(k)}{k}\right\rfloor = F(n) +\left \lfloor \frac{2n}{n+1} \right \rfloor + \sum_{k=n+2}^{2n}\left\lfloor\frac{k-1}{k}\right\rfloor = F(n)+1,\]](http://latex.artofproblemsolving.com/9/f/e/9feb9ec9d2f4fdfb8edbdcfdf32f27a08188589e.png)
so 
. Consider a permutation such that 
. Consider the first elements 
. The -th smallest number among these is at least , for each 
. Define as 
if is the -th smallest among . Then,![\[F(n) \ge F(2n) = \sum_{k=1}^{2n}\left\lfloor\frac{\pi(k)}{k}\right\rfloor \ge \sum_{k=1}^{n}\left\lfloor\frac{\pi(k)}{k}\right\rfloor \ge \sum_{k=1}^{n}\left\lfloor\frac{\sigma(k)}{k}\right\rfloor \ge F(n)\]](http://latex.artofproblemsolving.com/0/3/2/032eee5d6eb2d33271976b2e7acc14eb941e305e.png)
for 
and 
for 
. But where does the number 
go?
for any , and if 
for some , then 
, because the difference 
. This is a contradiction.. The proof of 
is similar.
.
be the -tuple 
that we are constructing that will give 
. Take 
. Say 
. Then, for 
, if is not a power of , set to be the -tuple with entries 
for 
, entry for 
, entry for 
, and entry 
for 
, and if is a power of , just append to the end of 
, i.e. 
.
is easy to see -- 
. Now, assume 
works for some 
. We will show 
works. is a power of , then 
since is a power of (so 
). is not a power of , then let 
and let 
. Then, 
by the recursive defenition and the fact that 
, as is not a power of . This is equivalent to ![$$\left[\sum_{i=1}^{2^{\lfloor \log_2k\rfloor} - 1}\left \lfloor \frac{c_i}{i}\right \rfloor\right] + \left \lfloor \frac{k+1}{2^{\lfloor \log_2k\rfloor}} \right \rfloor + \left[\sum_{i=2^{\lfloor \log_2k\rfloor} + 1}^{k}\left \lfloor \frac{c_i}{i}\right \rfloor \right] + \left \lfloor \frac{c_{2^{\lfloor \log_2k\rfloor}}}{k+1}\right \rfloor.$$](http://latex.artofproblemsolving.com/7/8/5/7859917908f373ff81c0c9d4878e2b61ae07f7e4.png)
Since 
(since as is not a power of and 
), 
. Since 
was used in 
, it is less than or equal to , so it is less than , thus 
Therefore, the expression is equivalent to ![$$1 + \left[\sum_{i=1}^{2^{\lfloor \log_2k\rfloor} - 1}\left \lfloor \frac{c_i}{i}\right \rfloor \right] + \left[\sum_{i=2^{\lfloor \log_2k\rfloor} + 1}^{k}\left \lfloor \frac{c_i}{i}\right \rfloor \right] = 1 - \left \lfloor \frac{c_{2^{\lfloor \log_2k\rfloor}}}{2^{\lfloor \log_2k\rfloor}}\right \rfloor + \sum_{i=1}^{k}\left \lfloor \frac{c_i}{i}\right \rfloor = 1 - \left \lfloor \frac{c_{2^{\lfloor \log_2k\rfloor}}}{2^{\lfloor \log_2k\rfloor}}\right \rfloor + 1 + \lfloor \log_2k\rfloor$$](http://latex.artofproblemsolving.com/d/b/f/dbff5d4963436876a1c841b1b1ce08ed6335cc0f.png)
by the inductive hypothesis. Since 
, the floor is either 
or . If is not a power of , then by the recursive construction (constructing from 
), 
. Else, by our recursive contruction again, so either way, which is 
, so the floor is at least , so it must be equal to . Thus, the expression is 
( is not a power of ), so we have completed our inductive hypothesis and our proof of the construction is done and so the minimal value is at most 
., which will immediately imply the conclusion since by the construction, equality can hold. To show this, we will start with a lemma.
be the minimum possible value of 
over all permutations 
of 
. Then, 
.
be a minimal such permutation. Then, if 
, we have 
by the minimality of . So in this case 
. Else, 
for some 
, and 
for some 
. Then, 
since . Letting 
, we have that 
since 
is a permuatation of 
, 
, and by the minimality of . Thus, either way, 
if 
(since by Lemma 1, 
). Thus, in order to show 
, it suffices to show 
, i.e. it suffices to prove the statement for powers of only, so we will show 
for all 
. Before we do that, we will prove another lemma which will help us in our induction.
be pairwise distinct positive integers. Prove that there exists a permutation 
of 
such that 
and furthermore that 
for all 
. had an ordering 
, where 
is a permutation of 
. Then, since the are positive, 
, so 
, and so on, so 
for all 
. Thus, taking the permutation such that 
for all 
gives 
and so 
as desired.
, the only choice is 
, whence 
, so the base case is established. Now, assume the statement is true for . We will prove that it is true for . Let 
be a minimal 
-tuple, i.e. so that 
. Let be the unique index between and inclusive such that 
. If was greater than 
, then 
By Lemma , since 
are all pairwise distinct, there exists a permutation 
with 
where the last inequality is by the minimality of 
. Thus, 
, and since by the inductive hypothesis 
, we have 
, so we are done in the case that 
. Else, is less than or equal to , so 
By Lemma , there exists a permutation 
of 
with 
for all 
. By the minimality of , 
so we have 
Since for all , all of these terms are nonnegative, so this is greater than or equal to 
I claim that this is greater than or equal to . It suffices to show that 
is 
, since if they differ by at least , they cannot reside in the same interval 
for some integer 
, hence they have different floors (and if the difference of the floors is not greater than or equal to , it must be less than , but the difference is nonnegative since 
, so the difference must be ). Indeed, 
Thus, 
. By the inductive hypothesis, , so it follows that 
, so in both cases our inductive step is complete and so we are finally done.
or given by the recurrence 
with 
we use the arrangement from 
for 
then we set 
Then we clearly have as the only additional contributing term is 
we do something similar. We first use the arrangement from 
for the first 
terms, then we set 
This again gives us 
can be decomposed into cycles based on the permutation 
Suppose 
is such a cycle, contributing 
to the total sum. Then I claim that in any optimal configuration, the cycle contains at most one inversion, ie. 
such that 
To show this, suppose there were two or more inversions in the cycle. WLOG, let 
be the largest element in the cycle. Let 
be the rightmost inversion in the permutation, 
We will split the cycle into two cycles, removing the inversion 
Then we can iteratively do this to remove inversions until there is at most one remaining in each cycle. We can write the cycle in the form 
There are two cases. Suppose 
But then we could split the cycle into two cycles: 
If we compare the sum of contributions from these two cycles with the sum for the original cycle, after cancelling like terms we see that the remaining terms are 
for the two cycles compared to 
for the original cycle, as these are the only terms not in common. However, 
as 
and 
as 
In the special case where 
the second cycle is a degenerate fixed point 
Thus, the total sum does not increase after the split.
so 
Then there exists 
such that 
and 
Now we split the cycle into
If we compare the sum of contributions from these two cycles with sum for the original cycle, after cancelling like terms, we see that the remaining terms are 
for the two cycles after the split compared with 
for the original cycle. However, by assumption, 
and 
so 
and furthermore 
as 
Thus the total sum again does not increase after the split.
each cycle 
's terms must be arranged in the order 
ie. each cycle contributes exactly one term 
to the total sum. Now it easily follows that optimally, each cycle must contain a set of consecutive integers, because if there were some missing number between 
and 
in some cycle, we could add that number in without affecting that contribution from that cycle, while weakly decreasing the contribution from the other cycle that we removed the number from.
for each cycle. Suppose some cycle contained the numbers 
where 
and 
so the contribution is 
Then by splitting up into 
cycles of the form 
we get cycles that each contribute so the sum does not change. (We can clearly do better but this reasoning suffices.) is monotonic, suppose the group containing is 
then we know that 
so clearly we have 
and we indeed have as desired. 
. We show this in the proof. to be the minimal value of the floor sum for a fixed . There are three things to prove.
is nondecreasing.
.
.
and 
and induct. Suppose that we have 
. Then to show that we want to show that 
is impossible. If this were true, then we would have to have 
for all 
which implies that 
for some 
. But now the floor sum of the first half of the permutation for 
is greater than which implies that 
. A construction for is simple: take the optimal construction for 
and set 
and 
for all 
.. It is enough to give a construction, which is trivial: just take the optimal permutation for 
and then set 
, and for all 
. We are done. 
Let 
and note that 
For 
and 
let 
and 
Let 
Note that 
is one if and only if is a power of two, and zero otherwise, so the sum is 
as desired.
Otherwise, in a minimum construction, suppose is the value such that 
then ![\[a_1+\left\lfloor\frac{1}{m}\right\rfloor=a_1\ge 1+\left\lfloor\frac{a_1}{m}\right\rfloor\]](http://latex.artofproblemsolving.com/0/d/1/0d17ece7029270a3000b03e4d03d8630d5370f05.png)
so there is another minimum construction for which 
for all 
and suppose there is a minimum construction where 
Then, let 
Now, in order to decrease the value of 
we find a value such that 
but we also need 
such that is disjoint from the set of such that 
There are 
in the first set, and at least 
in the second set. Note that summing the two with 
will result in a number at least so that's a contradiction. Thus, there exists a described 
and 
then decreases by at least and 
increases by at most Thus, we have constructed another minimal construction. Following this pattern, there exists a minimum construction where 
for all 
for which 
Group the terms by 
and we are done.
be the answer. It is clearly that . We claim that 
. This will implay that 
. Firstly, we will show that 
., there exists 
which is a permutation of 
such that 
. Now, let 
for all 
and 
. We see that 
is a permutation of 
. Hence,
; that is to show that 
for all permutation .
for all . Let be an integer such that 
.
be a permutation of such that 
if 
. It is clear that this permutation exists. Thus, 
for all 
for all 
, and 
.
.
. Hence, 
as desried.
be the smalelst possible value of our expression. We will show that 
.
otherwise swapping values doesn't change our expression. Similiarly, WLOG 
. For some 
. Then we have
With help of , calculate smaller cases of .
, hence one may guess our answer is
.. We will show is also true .Combining 
with our induction hypothesis gives
Let 
where 
and 
( The reason 
is for avoiding to divide into cases). Rewriting 
gives
We can further simplify using our inequalities on our new variables. Since by floor function, we will have:
Which is true since 
Equality happens when 
i.e when 
and 
since we want 
is indeed minimum value and achieveable, hence we are done.
be the minimum value of the expression; we claim that 
.
and 
.
choose with 
as a permutation of 
such that ![\[\sum_{i=1}^n\left\lfloor\frac{a_i}{i}\right\rfloor=t_n\]](http://latex.artofproblemsolving.com/b/7/a/b7a7ed36878ec467220f226f5d8782def06bdf9b.png)
Then, let 
and for 
let . Notice our sum for becomes 
, so . Proceed similarly for the odd case, letting 
, and we have the desired result. 
. FTSOC, suppose not.
with . Notice we can find a permutation of called 
such that 
for 
and 
since all the less than or equal to are distinct. Hence, ![\[t_n\ge \left\lfloor\frac{2n}{j}\right\rfloor+\sum_{i\neq j}\left\lfloor\frac{a_i}{i}\right\rfloor\ge 1+\left\lfloor\frac{b_j}{j}\right\rfloor+\sum_{i\neq j}\left\lfloor\frac{b_i}{i}\right\rfloor\]](http://latex.artofproblemsolving.com/8/1/2/812969f861c3f84fb96adce5f5f53fb3e96b20d0.png)
which contradicts the minimality of . with 
. Then, 
and the sum of the first terms is at least so we have a contradiction. 
, we can prove by induction that the first term of is one, the next two terms are two, the next four terms are three, and so on, with the next 
th terms being . Thus, 
to 
are equal to so we find . 
. Strong induct on ; the base case is trivial. Assume the assertion holds for 
, specifically for 
so that![\[\sum_{k=1}^{\lfloor(n+1)/2\rfloor}\left\lfloor\frac{a_k}{k}\right\rfloor\le\left\lfloor\log_2\left\lfloor\frac{n+1}{2}\right\rfloor\right\rfloor+1=\lfloor\log_2(n+1)\rfloor\]](http://latex.artofproblemsolving.com/8/f/e/8feabc7d066bd6d8f908ff71771f12a0a8dbf0e5.png)
where 
is a permutation of ![$[\lfloor\tfrac{n+1}{2}\rfloor]$](http://latex.artofproblemsolving.com/6/8/9/689f2b279a09e55c6187d2e3806851d1bae5b6b0.png)
. It remains to show that is the minimum of the remaining![\[\sum_{k=\lfloor(n+1)/2\rfloor+1}^{n+1}\left\lfloor\frac{a_k}{k}\right\rfloor.\]](http://latex.artofproblemsolving.com/2/8/6/28633342c86748718612e96d270d8dfa82b1b866.png)
Indeed, said minimum is attainable at 
, and it is optimal because clearly 
for some . 
.
. Then 
holds for 
. Else, suppose that 
.
, then by swapping 
with it decreases the sum as ![\[ \left\lfloor \frac{n-1}{f(n-1)} \right\rfloor + \left\lfloor \frac{a_n}{n} \right\rfloor > \left\lfloor \frac{a_n}{f(n-1)} \right\rfloor. \]](http://latex.artofproblemsolving.com/6/5/9/659ea0a63d01087428fba830862154bb3bf2e6c2.png)
By repeating this, we can get that for 
.![\[ \sum_{k=1}^n \left\lfloor \frac{a_k}{k} \right\rfloor = M_{f(n)-1} + \left\lfloor \frac{n}{f(n)} \right\rfloor \]](http://latex.artofproblemsolving.com/6/0/2/602a0d444e87af391f36598d6c29fcf5bd8fe87d.png)
be 
.
.
holds.
.
is the minimal possible value of 
as ranges from to inclusive. is one more than a power of , so let 
. The expression is then ![\[ b + \left\lfloor \frac{n+1}{2^b} \right\rfloor \]](http://latex.artofproblemsolving.com/b/0/0/b009ca9453371fe1d21a71d623b3e8197c6cb9c3.png)
Since 
it follows that this occurs when 
is maximized at 
, at which point 
so the expression is simply the desired 
. 
., we have 
.
of 
. Let 
and 
. It's easy to see 
so there exists a bijection that swaps each element in 
with an element from 
within the permutation, forming a new permutation 
where the first terms are a permutation of 
and the last terms are a permutation of 
. Now, suppose 
.
, then assume and 
swap via the bijection. Because 
, 
where the penultimate inequality is true because the bijection always swaps in smaller values for the first terms.
, then 
using similar reasoning from the previous case. Thus, 
. An analogous process shows the same bound for 
, as we can just replace with 
.
be a permutation of that achieves 
. Then, setting 
yields 
An analogous construction can be used for to achieve 
. 
is trivial. Suppose the hypothesis is true for all such that 
. Observe that 
implies 
for integer 
, so 
which completes the induction step. 
implies 
during my induction step, as the main claim is equivalent to 
.
we trivially conclude 
for arbitrary 
Hence 
for 
(the last tuple may be incomplete); in each tuple consider permutation 
Then the sum of floors in each tuple equals to giving the exact desired total sum.
. We prove this by strong induction on .
the value of the given function, and to be the minimum value for variables. Suppose that . By swapping to and so on until we can no longer do so, we have 
The rest is just a very long calculation: it suffices to show that 
Unless is a power of , the result follows by the identity 
. If is a power of , then we can set 
and 
, and the result follows again by a direct calculation.
and finish the problem , and the result for every follows easily. and all of the form 
and the last fraction gives the only to a sum
.
. Then, 
. Partition the set into sets 
. There are exactly parts. Label the sets 
such that 
. Then, for any 
, if 
and 
then , while if 
then 
. Using this construction, we see that if 
is not a power of two then 
. So, the sum is just![\[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor=\sum_{i=0}^{k}\left\lfloor\frac{\max(S_i)}{2^i}\right\rfloor=\sum_{i=0}^{k}1=k+1\]](http://latex.artofproblemsolving.com/0/1/5/01542c167430042090443e2135ab6873552ce249.png)
Note that this is because 
.
are trivial.. If for some 
, then we are done because 
contributes at least 1, and we get the rest from 
. Now suppose that for some 
. Let 
be the smallest number not in 
. If we replace 
with , the answer for first terms' sum will be at least . Changing back to , we see that 
, and hence the answer increases by 1, which gives . 
. The construction is similar to above posts.
so that 
. Say that 
is bad if 
is positive (i.e. 
), and good otherwise. Label all the bad integers 
. Then order all the 
as 
.
and 
for 
.
, then at most 
elements in 
are of the form 
for bad, and so there remains at least 
elements that are of the form 
for 
good. But since here 
we must have 
, so there are at most 
possible values of , contradiction. 
, one sees that we must have 
for 
. Hence it suffices to minimize![\[ S = \left\lfloor \frac{b_1}{b_0+1} \right\rfloor + \left\lfloor \frac{b_2}{b_1+1} \right\rfloor + \left\lfloor \frac{b_3}{b_2+1} \right\rfloor + \dots + \left\lfloor \frac{b_k}{b_{k-1}+1} \right\rfloor \]](http://latex.artofproblemsolving.com/8/0/0/8005d22e0ca080ec1a971e9bae32513e82a05caa.png)
for a sequence 
. By telescoping the inequality![\[ \frac{b_{i} + 1}{b_{i-1} + 1} \leq \left\lfloor \frac{b_i}{b_{i-1}+1} \right\rfloor + 1 \]](http://latex.artofproblemsolving.com/1/8/4/184cba430176c9bcd57627c350aa80c46395d144.png)
we obtain![\[ n + 1 \leq (s_1 + 1)(s_2 + 1) \dots (s_k + 1) \]](http://latex.artofproblemsolving.com/3/e/b/3eb5216e185c4fe9a2fc1bd2120bbd9454025e66.png)
where 
, and we want to minimize 
. Noting that if 
then replacing it into two smaller numbers summing to 
(and correspondingly increase by ) must increase the RHS, so we may assume all 
. this produces 
and so 
, as desired.
denote the smallest possible value over all permutations of 
.
for some natural number 
, such that is minimized, where is a natural number. We will also assume 
for convenience. Moreover, I just realized that this claim was used in Evan's solution, just that I express it in a more convoluted way.
, then we will show that the permutation with the smallest value is indeed in the form 
. Let the smallest value among all the sequences with be 
with 
. Then suppose is the largest index that doesn't satisfy this. Note that for indices larger than , 
. Consider swapping and 
, where 
. Note again that 
and 
. Then the relevant fractions become:
=
which is our original two fractions, implying the existence of a permutation resulting in a smaller value, contradiction.. Now it suffices to consider permutations of such form. Note that 
is actually a permutation of the first natural numbers. Thus for each , the permutation yielding the smallest value is 
, where 
yields 
. Thus the permutation yielding must be in that form, and , since all the fractions before yield the value , while the fractions after have numerator one less than the denominator, so all the terms yield . It is then clear that we choose the that yields the smallest value.
, and will prove by induction. We will use without proof that 
for nonnegative integers 
.
, and 
with 
and being nonnegative (i.e. i\geq 2), then 
.
, it is clear that the resulting sum will be .
, which yields 
.
is trivial.
.
then we can put 
for all 
. then the later brackets go to zero and we are left with \begin{center}
. then we have \begin{center}
. Here we have 
and this follows due to case two.
, the maximum value. Then if 
, since![\[\left\lfloor\frac{n-1}{m}\right\rfloor + \left\lfloor\frac{a_n}{n}\right\rfloor \ge \left\lfloor\frac{a_n}{m}\right\rfloor + \left\lfloor\frac{n-1}{n}\right\rfloor \impliedby n-1 \ge a_n\]](http://latex.artofproblemsolving.com/6/1/9/619317ce05c109897691490a1394670b6dba9c06.png)
and to make 
. Similarily, we continue this process to make![\[a_{n-1} = n-2, \ldots, a_{k+1} = k.\]](http://latex.artofproblemsolving.com/c/2/4/c249b69bfadc1a1f1652bcea1ebe62f0b2421ae3.png)
as the least possible value of the desired. Then![\[f(n) = \min_{1 \leq k \leq n} \left(f(k-1) + \left\lfloor\frac nk\right\rfloor\right).\]](http://latex.artofproblemsolving.com/9/6/b/96bc7aa523c53cb2d5b38bfa7f42ba6992fd789b.png)
, which we can prove through induction. Suppose 
such that![\[\left\lfloor\frac{n}{a+1}\right\rfloor+1 \leq k \leq \left\lfloor\frac{n}{a}\right\rfloor\]](http://latex.artofproblemsolving.com/c/3/9/c390959e93d9f2972f2c0f9578bf661e74f0ee2a.png)
![\[\implies f(n) = \min_{1 \leq a \leq n} \left(\left\lfloor\log_2 \left\lfloor\frac{n}{a+1}\right\rfloor\right\rfloor+a+1\right).\]](http://latex.artofproblemsolving.com/c/b/b/cbb109666ad787d9bd97a34beabc27a5183d21f4.png)
, and thus the maximum occurs at 
. Comparing 
and 
, it suffices to have![\[\left\lfloor\frac{n}{x+1}\right\rfloor \leq 2 \left\lfloor\frac{n}{x+2}\right\rfloor,\]](http://latex.artofproblemsolving.com/a/1/3/a137770856e48ca11fc850fb3c27abc9272cac89.png)
. Hence![\[f(n) = \left\lfloor \log_2 \left\lfloor\frac{n}{2}\right\rfloor\right\rfloor + 2 = \left\lfloor\log_2 n\right\rfloor+1\]](http://latex.artofproblemsolving.com/6/4/4/644925659a02d6a7f43aa3aa080742a7d7b0c216.png)
, completing our induction. 
. I claim that 
where 
is such that 
.
and 
. Taking for 
and for every 
that isn't a power of , we find that 
. This is the construction for our answer.
(since is monotonic). We will induct. Suppose that for some we have 
. Note that for 
this implies that 
for every 
. This implies that there is some 
such that 
and so 
. But then swapping some terms we'll be able to get a smaller value of 
, contradiction.
. The key is to consider where we place . Suppose that is put into spot . Then if we put in spot , in spot all the way to in spot this minimizes the sum because everything to the right of contributes zero to the sum, and the numbers to the left are minimized. This allows us to proceed with our induction., we have:
denote the total of minimal sum for 
. Suppose that for 
, 
Then we have:
Now suppose 
so we wish to minimize:
If 
then increasing by can only decrease or keep the sum the same. So we can take 
to minimize it. Therefore 
and we are done.
in other words the number of digits has when written in binary. is clear. Now there are two cases:
for some 
then we use the construction for for 
and then let 
and for 
This gives a value of 
for some then we use the construction for for and then let 
and for 
This again gives a value of is clear. Once again, there are two cases. for some then consider the first terms of the sum. Since the floor function is nonstrictly increasing, we can shift down 
down to a permutation of 
while only decreasing the sum. By the inductive hypothesis, the first terms of the sum thus contribute at least 
to the sum., then by our logic above this means that the last terms contribute to the sum. This implies that 
cannot be among the last terms, so it must be among the first terms. Suppose that 
for 
Then we have 
so we can subtract from , contributing extra to the sum, and still shift down the to a permutation of 
by the inductive hypothesis this gives a bound of 
contradiction. Thus the sum is at least 
for some Thus we are done.
. Let 
, so that 
is the smallest integer with 
. Call the sum in the problem the value of a permutation., where 
, and 
for 
. The section of this permutation will contribute exactly to the value. We can now induct downwards on the section of 
until we reach 
. This construction will allow the value to take on .
:![\[(1, \quad 3, 2, \quad 7, 4, 5, 6, \quad 14, 8, 9, 10, 11, 12, 13).\]](http://latex.artofproblemsolving.com/5/8/a/58a6d57a5068fc63bab5b1ea39eb5e089ef53106.png)
, which we can prove exhaustively. Now assume that this is true for each 
. I will show that this is the minimum value for as well.. I will perform a series of operations that does not increase the value of this supposedly minimal permutation, and at the end of this series of operations, the new value will be at least . This would mean that the minimum is as claimed. from above, swap with 
in the permutation (if they're not the same already). Letting 
and 
for some 
means that we need to verify![\[ \left\lfloor \frac{n}{c} \right\rfloor + \left\lfloor \frac{x}{a} \right\rfloor \leq \left\lfloor \frac{x}{c} \right\rfloor + \left\lfloor \frac{n}{a} \right\rfloor .\]](http://latex.artofproblemsolving.com/7/d/2/7d2c9569ba9099ac1622ec22769ee23ae0ce8be9.png)
Since 
, the above holds if 
. If 
, then the above would also hold, due to 
.
, beginning with 
and going down, swap 
with 
in the permutation (if needed). Now redefine 
, 
. Here, 
and 
, since we are doing this algorithm from down. Here's a useful visual:![\[ \frac{k-1}{a}, \cdots \frac{x}{k}, \frac{k}{k+1}, \frac{k+1}{k+2}, \cdots \frac{n-1}{n} \]](http://latex.artofproblemsolving.com/1/3/5/135b91fe9eb892d08d04d496babcd57bff09e4f8.png)
Now we just need to verify that this swapping does not increase the value of the permutation with the following:![\[ \left\lfloor \frac{k-1}{k} \right\rfloor + \left\lfloor \frac{x}{a} \right\rfloor \leq \left\lfloor \frac{k-1}{a} \right\rfloor + \left\lfloor \frac{x}{k} \right\rfloor .\]](http://latex.artofproblemsolving.com/8/e/5/8e5eb36701871055a11e902e465e0c24ed1b4ae5.png)
This is just true, because 
and 
.![\[ \sigma(c),\sigma(c+1),\dots,\sigma(n) = n,c,c+1,\dots,n-1 ,\]](http://latex.artofproblemsolving.com/a/2/3/a23fbe77d92a334fad39f6a7f14d707c69e69c30.png)
This entire section will contribute exactly to the total value of the new permutation.
is a permutation of 
. By the inductive hypothesis, the minimum that this can contribute to the sum is![\[ \left\lfloor \log_2 \left\lfloor \frac{n}{2} \right\rfloor \right\rfloor + 1 = \lfloor \log_2n \rfloor .\]](http://latex.artofproblemsolving.com/6/5/7/657f1026296a6427c342a619374904a2f04094e4.png)
Thus, the value of the new permutation is at least , as desired.
?
.
then we do blocks of 
for 
and the final one is 
.
of the entries are nonzero, and they are all 1.
.
terms will be at least 
(because 
dominates some permutation of 
)
for some 
.
.
with the smallest positive integer 
not among 
.
so this term must have increased by at least 1 when floor functions are introduced.
.
and right after it add 
and it's easy to see that indeed the value of the sum is as desired (it is incremented exactly by 
.
- just consider the position of 
are all on positions 
.
,
.
.![$[n]$](http://latex.artofproblemsolving.com/0/d/e/0deff9086fd7840ef23860f5bc924f1d4d2d2310.png)
into groups 
,
,
,
(each group ranges from 
,
,
with 
for which the block 
is not 
,
;
currently has value 
(since we assumed all previous blocks match our construction). We will show that swapping ![\[\left\lfloor{\frac{a}{2^k}}\right\rfloor + \left\lfloor{\frac{2^{k + 1} - 1}{b}}\right\rfloor \geq 1 + \left\lfloor{\frac{a}{b}}\right\rfloor.\]](http://latex.artofproblemsolving.com/5/b/7/5b7381614bb44f817bf7eb682036ad92f892522e.png)
)![\[\left\lfloor{\frac{a}{2^k}}\right\rfloor \geq 1 \text{ and } \left\lfloor{\frac{2^{k + 1} - 1}{b}}\right\rfloor \geq \left\lfloor{\frac{a}{b}}\right\rfloor.\]](http://latex.artofproblemsolving.com/a/c/9/ac9b45f2b529192e2f6dec0d93f663a94d872f8a.png)
)![\[\left\lfloor{\frac{a}{2^k}}\right\rfloor \geq \left\lfloor{\frac{a}{b}}\right\rfloor \text{ and } \left\lfloor{\frac{2^{k + 1} - 1}{b}}\right\rfloor \geq 1\]](http://latex.artofproblemsolving.com/f/e/3/fe3abddbe7fe4215f3ca9e7353b87b5a5cb632b8.png)
(the first inequality follows from the fact that 
)
)
.![\[\left\lfloor{\frac{a}{b}}\right\rfloor + 1 \leq \left\lfloor{\frac{a}{2^{k + 1}}}\right\rfloor + 1 \leq \frac{x}{2} + 1 \leq x,\]](http://latex.artofproblemsolving.com/b/2/6/b260654cf228fcd5c660153edb02c78eb3c4cfde.png)
as desired.
be the first index (with 
)
,
is currently 
is currently at index 
and 
(since all previous slots have been filled correctly). Now swap ![\[\left\lfloor{\frac{a}{2^k + \ell}}\right\rfloor \geq \left\lfloor{\frac{a}{b}}\right\rfloor \text{ and } \left\lfloor{\frac{2^k + \ell - 1}{b}}\right\rfloor = \left\lfloor{\frac{2^k + \ell - 1}{2^k + \ell}}\right\rfloor = 0.\]](http://latex.artofproblemsolving.com/c/5/a/c5ae24a8390d77da8650e57c42ec716e9a34781d.png)
the smallest value of 
.
where 
,
for 
.
If 
denotes the smallest such value, then 
is equal to the minimum over all 
We will first prove through strong induction that for 
minimizes. First, for the base case, 
)
and 
instead, we have that, since 
but 
so switching 
would not increase our sum, proving the base case. For the inductive step, the reasoning is analogous, after noting that 
for all 
so 
so we have a minimum of 
for that part. Now, for the first 
so the sum becomes 
and thus we have proved the claim.
The base cases (try 
because these "small" values seem kinda sus in our inductive step) Firstly, we will show that 
Plugging in 
gives us that
so this is proven. Now, notice that 
trivially for all 
so we are done.
