candy pieces and places them in a row on a table. Then, she chooses one of the following operations (if available) and executes it:
She eats a candy of type 
followed by one candy type 
(we consider type 
to be type 1, and type 0 to be type 
She chooses two consecutive candies which are the same type, and eats them.
and any configuration of candies on the table.
of 
with 
elements. Prove that there exist three elements 
from 
.
be a convex hexagon with 
and 
.
which is equidistant from sides 
and 
.
and 
are the centers of mass of 
and 
,
.
Y by mssmath, kk108, tenplusten, rashah76, v4913, megarnie, HamstPan38825, GorgonMathDota, Adventure10, Mango247, MS_asdfgzxcvb
Suppose that 
and 
are positive integers such that ![\[ 1 = \underbrace{\varphi( \varphi( \dots \varphi(}_{k\ \text{times}} n) \dots )). \]](//latex.artofproblemsolving.com/b/6/4/b64fa5fbf6613768c78beb3ab2b712599bd7ea80.png)
Prove that 
.
Here
denotes Euler's totient function, i.e. denotes the number of elements of 
which are relatively prime to . In particular, 
.
Proposed by Linus Hamilton
and 
are positive integers such that ![\[ 1 = \underbrace{\varphi( \varphi( \dots \varphi(}_{k\ \text{times}} n) \dots )). \]](http://latex.artofproblemsolving.com/b/6/4/b64fa5fbf6613768c78beb3ab2b712599bd7ea80.png)
Prove that 
.Here
denotes Euler's totient function, i.e. denotes the number of elements of 
which are relatively prime to . In particular, 
.Proposed by Linus Hamilton
decreases by at most 
with each application of 
.
on positive integers as follows: it satisfies 
,
,
for any prime 
.
counts the powers of 
.
for every 
.![\[ w(p) = w(2) + w\left( \frac{p-1}{2} \right) \ge 1 + \log_3(p-1) - \log_3 2 \ge \log_3 p \]](http://latex.artofproblemsolving.com/7/6/f/76f32b24dfb893e560e0cb9a3501c898b01f68de.png)
for any 
.
to be multiplicative satisfying 
for 
and 
for 
.
.
for 
,
.
,
.
,
solves the equation.
< 
. 
,
.
so that 
is the number of iterations of the Euler function required to obtain 
is even and 
for 
)
.
.
,
.
,
if at least one of 
and 
is odd and 
otherwise.
and 
,
,
.
so 
.
.
as 
for any prime 
.
.
.
.
,
.
,
.
.
,
.
implies 
.
and if 
.
.
,
,
.
,
.
if 
is composite. And, if 
.
,
,
to avoid edge cases. Abbreviate given equation as 
,
,
If we look carefully, 
by noting that the contributions of odd parts get added up ,ie, get doubled (in this case) in the exponents. This can be extended to 
.
for primes 
.
.
by Induction on 
Now coming back, we let 
,
.
otherwise we can't have 
Now suppose 
,
.
). Now it is easy to observe that 
is odd, we find that 
as desired.
, then 
then 
, 
and then I reached to make a perfect claim...
.
.
where 
.
,![\[ f(n)=\begin{cases}1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i &\text{ if } 2\nmid n\\ e_1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i &\text{ if $2\mid n$, i.e. $p_1=2$}. \end{cases} \]](http://latex.artofproblemsolving.com/5/5/d/55d2905222b9552fd2818a92b780934720134fcf.png)
In particular, 
'
,
,
,
and 
.
.
with 
,![\[f(ab)=\begin{cases}f(a) + f(b) &\text{ if } 2\mid a \text{ and } 2\mid b, \\ -1+f(a)+f(b) &\text{ if } 2\nmid a \text{ or } 2\nmid b. \end{cases} \qquad (\spadesuit)\]](http://latex.artofproblemsolving.com/7/3/d/73d9fab0a4aaf1c8ffd75f3ccea853c7c620a7fa.png)
We have 
by definition. Also, in particular, 
,
for primes 
.
:![\begin{align*} f(n) &= 1+f(\varphi(n)) \\ &= 1+f\big( (p_1-1)\cdots (p_k-1) p_1^{e_1-1}\cdots p_k^{e_k-1} \big) \\ &= 1+\left[ -1+ f(p_1-1) + \cdots + f(p_k-1) + f\big(p_1^{e_1-1}\cdots p_k^{e_k-1} \big)\right] \\ &= [f(p_1)-1] +\cdots + [f(p_k)-1] + \left[ 1 + \sum_{i=1}^k \big( f(p_i)-1\big)(e_i-1) \right] \\ &= 1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i. \end{align*}](http://latex.artofproblemsolving.com/d/f/1/df15f0b85220a6591df1cf26eb14af3831891fbd.png)
We can also confirm that even if 
,
.![\begin{align*} f(n) &= 1+f(\varphi(n)) \\ &= 1+f\big( (p_1-1)\cdots (p_k-1) p_1^{e_1-1}\cdots p_k^{e_k-1} \big) \\ &= 1+\left[ f(p_1-1) + \cdots + f(p_k-1) + f\big(p_1^{e_1-1}\cdots p_k^{e_k-1} \big)\right] \\ &= 1+ [f(p_1)-1] +\cdots + [f(p_k)-1] + \left[ (e_1-1) + \sum_{i=1}^k \big( f(p_i)-1\big)(e_i-1) \right] \\ &= e_1 + \sum_{i=1}^k \big(f(p_i)-1\big)e_i. \end{align*}](http://latex.artofproblemsolving.com/2/5/1/251f13c9d1798da225d39ce24228d9148aeabb71.png)
.
.
for primes 
are all less than ![\begin{align*} f(p) &= f(p-1) + 1 \\ &= \left[-1+f(2^{\nu_2(p-1)}) + f\left(\frac{p-1}{2^{\nu_2(p-1)}}\right)\right]+1 \\ &\le \log_3(2^{\nu_2(p-1)}) + \log_3\left(\frac{p-1}{2^{\nu_2(p-1)}}\right) \\ &= \log_3(p-1) \\ &<\log_3(p), \end{align*}](http://latex.artofproblemsolving.com/2/0/d/20d5020508069008bc999d0367c5f92fc50a954b.png)
and we are done. Note that we had to use 
inequality.
,![\[ 3^a13^b \to 2^3\cdot 3^a\cdot 13^{b-1} \to \cdots \]](http://latex.artofproblemsolving.com/7/b/0/7b0f2b0b58db035e96224e0bfdde02989ff33c6e.png)
where new prime factors are introduced, but somehow the number of steps is still a linear combination. Finding out a rigid description of 
cleared all this up since after that, induction takes care of the process, which is very hard to analyze step-by-step as stated.
or 
and so on that 
for 
became too difficult after being compounded by many steps. The main observation was to notice that the coefficients are basically 
,
.
.
,
,
for prime 
.
for 
.
.
as desired.
function decreases 
by at most 
to be the maximal possible 
value upon repeatedly applying 
to 
,
.
and 
are trivial, and for the inductive step, if the result holds for all 
divide it, then for any ![\[f(n) = f(p^m) + f(n/p^m) \geq mf(p-1) + \log_3(n/p^m) \geq \log_3(n)\]](http://latex.artofproblemsolving.com/1/d/5/1d54c96e52f0bb6f9a7d1a93730be98248687cfb.png)
where 
,
.
.
.
where 
and all exponents are positive.
So 
The last is true since 
.
.
.
when 
and all exponents are positive.
with 
a power of two. On the other hand, because 
when 
is at least 
.
,
for odd primes 
for all 
times to reach 1.
"type 2" berries, 
"type 3" berries, 
"type 5" berries, and so on, she has 
type 
type 2 berries, 
type 3 berries, and so on (in particular, eating a type 2 berry has no gain). On each turn, Alice will eat one berry of every type that she has. The problem statement is thus equivalent to the assertion that Alice will be able to eat for at least 
We will show this by induction. Let 
be the value of berry 
as shown earlier. Now, note that after eating a type 
Let these berries be 
(not necessarily distinct). Note that for all 
,
.
However, note that 
is never an integer other than 
,
which shows the claim inductively.
berries of type 2 eventually. Let Alice's original berries be 
.
so at least 
to be 
be the number of distinct odd prime divisors of 
The key observation is that at each application of 
,
which comes from 
where 
except for 
by 
so 
.
are the odd prime factors counted in 
in any order,
as desired.
.![\[ \nu_2(\varphi(n)) = \nu_2(n)+\sum_{\text{prime} \ p|n} (\nu_2(p-1)-\nu_2(p)) \ge \nu_2(n)+g(n),\]](http://latex.artofproblemsolving.com/a/b/e/abef0571912392cc0a077e9f07fdb77066a9098f.png)
if 
if 
.
is easy. By the logarithmic nature of 
for prime ![\[ f(p) = f\left(\frac{p-1}{2}\right)+f(2)= f\left(\frac{p-1}{2}\right)+1 \ge \log_3(p-1)-\log_3(2)+1 = \log_3(p-1) + \log\left(\frac{3}{2}\right) \ge \log_3(p-1)+\log\left(\frac{p}{p-1}\right)=\log_3(p), \]](http://latex.artofproblemsolving.com/b/9/f/b9f6fee0505c264464207c39377ade6b3d6c89dc.png)
completing the proof. 
,
,
,
)
as desired. 
,
.
,
then nothing was destroyed), and 
has built 
twos. Now here comes the key claim:
twos will be built, including 
is obvious.
,
.
two will be built. We have 
will be built.
.
.
twos will be produced. Now 
.
,
twos will be produced. Now 
- prime. Then 
.
we can manually check that everything works. Otherwise, 
(cause none of this two can be a power of three), hence we are done.
![\[
\forall n \in \mathbb{N} , \frac{n}{\varphi(n)} \leq 3 \cdot \left( \frac{3}{2}\right)^{v_2(\varphi(n))-v_2(n)}
\]](http://latex.artofproblemsolving.com/8/e/c/8ec926c8f8907fa6850a782addb215f49ae326e8.png)
then this result holds trivially. Now let's assume that some odd prime divides 
denote the set of all primes dividing 
denotes set of all odd primes dividing 
as each odd prime will add at least one power of 
![\[
\frac{n}{\varphi(n)} = \prod_{p \in S}\left(1 + \frac{1}{p-1} \right) \leq 2\cdot \prod_{p \in G}\left(1 + \frac{1}{p-1} \right) \leq 2 \cdot \left(\frac{3}{2} \right)^{|G|} \leq 2 \cdot \left(\frac{3}{2} \right)^{v_2(\varphi(n))-v_2(n) +1 }
\]](http://latex.artofproblemsolving.com/2/1/b/21b1e9fdc480c88ec18c2b1e449867d37c2706d4.png)
which proves our original claim.
where 
and 
is the function 
applied to 
times (if 
then 
)![\[
\prod_{i=1}^{i=k} f_t(n) \leq \prod_{i=1}^{i=k} 3 \cdot \left( \frac{3}{2}\right)^{v_2(\varphi^{t}(n))-v_2(\varphi^{t-1}(n))}
\]](http://latex.artofproblemsolving.com/2/8/c/28cac03676edad9d78674530ffd1c04b599ae6bc.png)
Hence![\[
n \leq 3^k \cdot \left( \frac{3}{2}\right)^{-v_2(n)} \leq 3^k
\]](http://latex.artofproblemsolving.com/4/9/9/499485b4dc9cec04ba597825e8bc4baa19d73b5b.png)
QED
by considering the parity of 
. If 
and therefore get 
.
,
