[/quote]
,
be reals such that 
and 
Find tha minimum value of 
be a triangle with the incenter 
,
of 
at points 
respectively. Let 
intersect 
.
and 
parallel to 
intersect 
respectively. Prove that 
and the circumcircle of 
.
.
be reals such that 
Prove that
be a point in the plane, and 
a line not passing through 
Find tha maximum value of 
Show that 
.![$$ \frac{ a}{b}+\frac{b}{c}+\frac{c}{a}\geq \sqrt[3]{49}$$](http://latex.artofproblemsolving.com/4/1/7/41747f09ab60b8e1a07de01f23d11985133c0d17.png)
.
be a triangle with 
and with its incircle touching the sides 
and 
at 
and 
respectively. A point 
lies on the extension of 
such that 
.
be the midpoint of 
.
.
,such that 
P
Y by RAMUGAUSS, Mr.Chagol, Vlados021, Carpemath, rmtf1111, Vietjung, samuel, juckter, djmathman, Toinfinity, anantmudgal09, Ultroid999OCPN, Polynom_Efendi, csunllc, Grizzy, mathleticguyyy, Combi1234, magicarrow, fjm30, Inconsistent, fidgetboss_4000, Purple_Planet, scrabbler94, MintTea, Nymoldin, brendan_cape, RedFlame2112, megarnie, Lamboreghini, rayfish, metricpaper, Mattthebat2569, sabkx, Infinityfun, ImSh95, centslordm, Adventure10, buddyram, Blue_banana4, Sedro, EpicBird08, NicoN9, Yiyj1
The Bank of Bath issues coins with an 
on one side and a 
on the other. Harry has 
of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly 
coins showing , then he turns over the 
th coin from the left; otherwise, all coins show and he stops. For example, if 
the process starting with the configuration 
would be 
, which stops after three operations.
(a) Show that, for each initial configuration, Harry stops after a finite number of operations.
(b) For each initial configuration
, let 
be the number of operations before Harry stops. For example, 
and 
. Determine the average value of over all 
possible initial configurations .
Proposed by David Altizio, USA
on one side and a 
on the other. Harry has 
of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly 
coins showing , then he turns over the 
th coin from the left; otherwise, all coins show and he stops. For example, if 
the process starting with the configuration 
would be 
, which stops after three operations.(a) Show that, for each initial configuration, Harry stops after a finite number of operations.
(b) For each initial configuration
, let 
be the number of operations before Harry stops. For example, 
and 
. Determine the average value of over all 
possible initial configurations .Proposed by David Altizio, USA
This post has been edited 2 times. Last edited by djmathman, Jul 17, 2019, 12:26 PM
which is finite.
on vertices 
(each string points to its successor) with 
corresponding to heads and 
corresponding to tails. For 
we let 
,
:
and 
of 
and just append a 
.
.
.
is given below.![[asy] unitsize(0.8cm);
label("$0000$", (0, 0), red); label("$1000$", (0, 1), red); label("$1100$", (0, 2), red); label("$1110$", (0, 3), red); label("$0100$", (2, 2), red); label("$1010$", (2, 3), red); label("$0010$", (4, 3), red); label("$0110$", (6, 3), red);
label("$1111$", (0, 4), blue); label("$1101$", (0, 5), blue); label("$1001$", (0, 6), blue); label("$0001$", (0, 7), blue); label("$1011$", (2, 6), blue); label("$0101$", (2, 7), blue); label("$0111$", (4, 7), blue); label("$0011$", (6, 7), blue);
label(scale(1.5)*"$\downarrow$", (0, 0.5), red); label(scale(1.5)*"$\downarrow$", (0, 1.5), red); label(scale(1.5)*"$\downarrow$", (0, 2.5), red); label(scale(1.2)*"$\leftarrow$", (1, 2), red); label(scale(1.2)*"$\leftarrow$", (1, 3), red); label(scale(1.2)*"$\leftarrow$", (3, 3), red); label(scale(1.2)*"$\leftarrow$", (5, 3), red);
label(scale(1.5)*"$\downarrow$", (0, 4.5), blue); label(scale(1.5)*"$\downarrow$", (0, 5.5), blue); label(scale(1.5)*"$\downarrow$", (0, 6.5), blue); label(scale(1.2)*"$\leftarrow$", (1, 6), blue); label(scale(1.2)*"$\leftarrow$", (1, 7), blue); label(scale(1.2)*"$\leftarrow$", (3, 7), blue); label(scale(1.2)*"$\leftarrow$", (5, 7), blue);
label(scale(1.7)*"$\Downarrow$", (0, 3.5), deepgreen); [/asy]](http://latex.artofproblemsolving.com/a/1/d/a1d7058aab11a1bac20f8cda77e609ca4262adbe.png)
had 
ones, ergo 
which is what we wanted. Finally, the one edge from 
denote the desired expected value. Since 
takes ![\[ E_n = \frac{1}{2} \left[ E_{n-1} + (E_{n-1}+n) \right] \]](http://latex.artofproblemsolving.com/8/9/b/89ba0a553e2be834a596842ed7fc752e940ba8ad.png)
based on cases on whether the chosen string is in 
be our configuration after 
(which will clearly lead to 
)
has strictly more heads than 
.
.![\[ \cdots THH\cdots H\cdots \mapsto \cdots TTT\cdots T\cdots \mapsto \cdots HTT\cdots H\cdots \mapsto \cdots HHH\cdots H\cdots,\]](http://latex.artofproblemsolving.com/3/3/e/33e49266cf2738fb24f284a8ef79df02da803342.png)
which has more heads than 
didn't stop then there exists a cycle 
,
denote the the set of 
and 
be the sets of configurations that end with 
,
we refer to the configuration obtained after a single operation is performed on 
denote the complement of a configuration 
be the reverse of 
denote the configuration achieved by adding the line of coins 
to the right of 
.
be the average we are looking for.
.
,![\[ L_n = L_{n-1} + \frac{n}{2} \]](http://latex.artofproblemsolving.com/c/b/d/cbd68e990fcb302e3883e9f92b63a67f73a8fce8.png)
for all 
.![\[ L(C + T) = L(C) \]](http://latex.artofproblemsolving.com/c/3/a/c3a37dff89f4bbd370c430b821437db5dd2106d6.png)
for al ![\[ f(C) = R(C(C)) + H . \]](http://latex.artofproblemsolving.com/a/2/9/a29b983810d6d1f29ae86d64d4656fdc2ab1728e.png)
The crucial claim is that![\[ L(f(C)) = L(C) + n \]](http://latex.artofproblemsolving.com/c/a/8/ca8be8643994800cb184169edfa9e154c8726891.png)
whenever 
.
.
to reach 
,
.
is a bijection. Moreover since 
are all bijections, it follows that 
is also a bijection. Now proving the recursion is just a direct computation:
as desired.
,
we have the configurations 
,
if 
is the result of applying the operation to 
,
since the final 
.
to be 
considered as the root at level 
from all levels). Clearly if 
then 
where 
denotes the level number of 
are isomorphic as leveled directed trees, which will almost finish the problem.
,
to be as follows. If 
,
,
,
.![\[ f(C) + f(\overline{C}) = n.\]](http://latex.artofproblemsolving.com/6/5/d/65d5c9b2bbb4331faf7cd0cbcf862b9bb1135424.png)
Now, say 
.
.
means flipping the 
-
.
.
,
is trivial and the average is clearly 
.
gives a sum of 
which is easy to compute by hand. Now, assume 
and 
.
.
.![\[ S_n = (2^{n-3}(n-1)n \times 2) + n2^{n-1} = 2^{n-2}(n^2-n+2n) = 2^{n-2}n(n+1),\]](http://latex.artofproblemsolving.com/4/e/8/4e8e8ec951c2d5c4c9a45099543bcbc1160bb937.png)
as desired.
,
is the location of the rightmost 
at all times. But every time the flip location turns rightward to leftward, 
strictly decreases.
which means we get a configuration that's 
so it's leftward until the end from here.
,
,
,
![$F(n) = \mathbb{E}[L_n(C)]$](http://latex.artofproblemsolving.com/2/e/a/2ea12e37d3237219ba63fdd9e467da80c2c99b7e.png)
.
(
)
,
steps we reach 
.
to reach the desired state.![$F(n) = \mathbb{E}[2\sum_{i=1}^k h_i - k^2] = \frac{\mathbb{E}[2 \sum_{i=1}^k h_i - k^2|h_k \neq n] + \mathbb{E}[2\sum_{i=1}^k h_i - k^2|h_k = n]}{2} = \frac{F(n-1) + \mathbb{E}[2 \sum_{i=1}^{k-1} h_i - (k-1)^2 + 2(n-k)+1| h_k= n]}{2} =F(n-1) + \mathbb{E}[n-k] + \frac{1}{2} = F(n-1) +\frac{1}{2}+\mathbb{E}[no.of T|n-1 tosses ] = F(n-1) + \frac{n}{2}$](http://latex.artofproblemsolving.com/3/f/f/3ff0dd76692abd4c1aff64e87feaf8ba39322129.png)
where 
and 
be defined as the sum of the number of the operations for all initial configuration with the following operation: if there are exactly 
,
from the 
until all coins show 
.
be the same as 
coin is turned over. Only 
,
,
,
,
,
,
,
make sense. Problem asks for 
initial configurations that end with a 
as the last 
operations, since the last 
when 
.
coin from right, where 
is the number of 
and 
.
.
by going through all possible cases. This leads us to the following claim:
We will show this by induction. We have already seen that this is satisfied for 
since it will take on average 
moves to make everything after it T and 1 additional move to finish.
,
moves to convert the middle part into T's and one more move to finish.
,
,
moves.
By our inductive hypothesis, we plug in 
and 
we get 
so we are done by induction. Note that this also solves part (a) since if any case is infinite, then the expected value is infinite, contradiction.
,
.
.
.
(since we can ignore the first coin and the process is the same, plus 1 when you need to flip the first at the end).
as desired. 
and 
We use induction to prove that for any starting position, the sequence eventually becomes a string of 
this is obviously true. For inductive step, assume that for 
coins, consider cases depending on if the first coin is 
the rest of the coins represent a binary string of length 
which from inductive assumption we know terminates. In this situation, all the indices of the binary string of length 
Therefore, the procedure in this case will be identical to the procedure for the binary string of length 
insert a coin in front of the first coin with label 
be the average number of steps it takes for the process to terminate for a string of length 
We prove that 
Testing the first few cases, we find 
Proceed by strong induction. The base cases are evident as described. For inductive step, assume 
for a string of length 
Then we prove that this holds for 
Consider the following cases:
where the 
accounts for the deletion of the initial 
operations to get to a string of 
operations to complete the process. Thus in this case we have 
This completes the induction.
the 
will denoted by 
while 
will be denoted by 
For example, 
would be denoted by 
has an arrow towards 
if and only if the string which 
we see that the “bottom” of the graph (i.e. the vertices closest to 
)
we see that the lower half of the graph for 
is exactly the same as the whole graph of 
then 
To prove this, notice that, in both of the strings 
and 
there are the same number of 
so when we apply the operation, we change the same number in the string. Similarly, we see that, if 
is not all zeroes, then 
implies that 
which can be proved in an analogous way. Now, to conclude part 
we proceed by induction. Notice that, if there is 
we assume this is true for 
Then, for any string of length 
by the inductive hypothesis. Now, 
so we are done.
denote the average number of moves for a string of length 
Then, 
Also, for 
moves. If the string ends in 
and then we require 
so overall,
Thus, 
which can be seen by Gaussian sums, or, more rigorously, a simple induction on 
,
through recursion. Note the ending state contains all tails.
and 
.
,
moves in this case.
.
.![\[a_n = \tfrac 14 (a_{n-2} + 2n-1) + \tfrac 12 (a_{n-1}+1) + \tfrac 12 (a_{n-1}) - \tfrac 14 (a_{n-2}+1) = a_{n-1} + \tfrac n2,\]](http://latex.artofproblemsolving.com/c/f/7/cf70dd677f58d7fb8df095c3689039a0424bc210.png)
be the wanted expected value, we claim that 
which is indeed finite and thus all configurations terminate. To prove this we induct, the 
case is obvious. Now assume this is true for some 
of 
coins.
is 
.
be the sequence of the first 
be the inverse of 
instances of 
as flipping coin 
as flipping coin 
.
is the inverse of 
for all positive integers 
,
has coin 
flipped. On the other hand, 
instances of 
is 
.
and the induction is finished. It is done.
This will prove part (a), since this value is finite, and finish part (b).
be the answer for 
and let 
be the expected value for a sequence of length 
Observe that 
Clearly, from 
if the sequence starts at 
operations for the middle 
Substituting this into the second recurrence yields 
Therefore, 
From here, we have that 
QED
![\[HH\dots H \longrightarrow HH \longrightarrow \dots
\longrightarrow HT \dots H TT\dots T \longrightarrow TT\dots TT\]](http://latex.artofproblemsolving.com/c/7/c/c7cc06ef858ce8065b5c84a31adec69c3a77737c.png)
which takes exactly 
be the total sum of steps taken over all ![\[[a_1 a_2 \dots a_{n-1}] H - [b_1 b_2 \dots b_{n-1}] T
\]](http://latex.artofproblemsolving.com/1/f/4/1f463217528dbda796462ebe03e0991f4e834094.png)
be \textit{paired} if for the first 
and 
is tails and the other is head.![$[a_1 a_2 \dots a_{n-1}] H$](http://latex.artofproblemsolving.com/1/8/5/1857530dbc4343fe2f3eed8dfbf90706643542a8.png)
,
Heads in ![$[b_1 b_2 \dots b_{n-1}]T$](http://latex.artofproblemsolving.com/2/8/e/28e49b8af4fa6dfd559988de719e1db36d538daa.png)
since the places which have Heads in the configuration paired to this has exactly 
Heads in places besides the final 
respectively of these two configurations. Thus, before the move one of Position 
.![\[M_{n} = 2M_{n-1} + 2^{n-1}n\]](http://latex.artofproblemsolving.com/c/1/0/c10170debe0611c26b5532fc07d6b004802bd1b7.png)
Now, it is easy to show that this recursion gives,![\[M_n = 2^{n-2}n(n+1)\]](http://latex.artofproblemsolving.com/9/6/9/9690c3b386423acd78f75c84e7584a16302f93f8.png)
which makes the average number of steps taken to reach termination state over all ![\[\frac{2^{n-2}n(n+1)}{2^n} = \boxed{\frac{n^2+n}{4}}\]](http://latex.artofproblemsolving.com/0/4/1/041f2d9df7b655f31a4fe0b75d77ffc14acb5e8b.png)
.
,![\begin{tabular}{|c c c c c c c c|}
\hline
HHH & HTH & THH & TTH & HHT & HTT & THT & TTT \\ [0.5ex]
\hline \hline
HHT & HHH & TTH & HTH & HTT & TTT & HHT & . \\
\hline
HTT & HHT & HTH & HHH & TTT & . & HTT & .\\
\hline
TTT & HTT & HHH & HHT & . & . & TTT & .\\
\hline
. & TTT & HHT & HTT & . & . & . & . \\
\hline
. & . & HTT & TTT & . & . & . & . \\
\hline
. & . & TTT & . & . & . &. & . \\
\hline
\end{tabular}](http://latex.artofproblemsolving.com/2/7/c/27c461c9c0806a3c95a0053b6147edfb9547243f.png)
Above is the table for 
for example, the sequence up to 
is identical to that of 
up to 
are related to 
in that the 
gets to 
in the same amount of flips as 
gets to 
.
which when inverted becomes 
t
heads. Thus, we flip the 
Therefore, the sequences will always be analogous under our reflection and inversion and thus will take the same amount of flips to get to either all 
is an identity so we are done (the 
comes from the 
,
be 
,
.
steps.
,
,
.
,
,
such that ![\[ s_i \text{ heads } \iff t_{n-1-i} \text{ for all } i = 1, 2, \dots, n-1 \]](http://latex.artofproblemsolving.com/b/b/2/bb2ce54d57cbb8af38f269b1665a894840c9bd7a.png)
(in the natural binary string interpretation, 
is the reverse of the inverse of 
)
holds. Suppose initially, 
are heads. Then 
of the 
and 
,![\[ a_n = \frac{2^{n-1}}{2^n}\cdot a_{n-1} + \frac{2^{n-1}}{2^n}\cdot (a_{n-1} + n) = a_{n-1} + \frac n2 = \frac{n(n+1)}{4} \]](http://latex.artofproblemsolving.com/0/1/6/0164cb327aa015ece63b0881de94682d3580d875.png)
as desired. 
coins, we can obtain a reduction.
coin from the left. Assume that the coins with 
,![\[a_1 < a_2 < \dots < a_k\]](http://latex.artofproblemsolving.com/b/9/b/b9bd2d04645c1f95d202aa47e412f1d7cf365bee.png)
Obviously, 
.
be the index of the first coin with 
(there exists such a 
since 
,![\[\underset{k}TT\dots T \underset{a_j}{H} \rightarrow \underset{k}HT\dots T \underset{a_j}{H}\]](http://latex.artofproblemsolving.com/c/4/0/c40713576ea7de3abaf306aa01e617fe3695749c.png)
Now, there are 
coins, so we move from![\[\underset{k}HT\dots T \underset{a_j}{H} \rightarrow \underset{k}{H}H\dots T \underset{a_j}H\]](http://latex.artofproblemsolving.com/3/c/8/3c86803d1b62f033773baf4500831a84b367d8c1.png)
We see that we keep doing the moves until we reach![\[\underset{k}HH\dots H \underset{a_j}{H}\]](http://latex.artofproblemsolving.com/a/1/1/a11e12f388e7038a135d40602c29b4e66f519f93.png)
this takes 
)
coins with ![\[\underset{k}HH\dots H \underset{a_j}{H} \rightarrow \underset{k}HH\dots H\underset{a_j}T\]](http://latex.artofproblemsolving.com/9/0/3/9032ebe6b1568ec72ee4047404434ff0cd3c0db9.png)
Once again, we can keep doing moves until we eventually reach![\[\underset{k}TT\dots T \underset{a_j}{T}\]](http://latex.artofproblemsolving.com/3/9/8/398a0a011e6dbd57bd2eb5c45fdc18d26b77a90a.png)
which takes 
moves. Therefore, this sequence of moves is indeed a reduction, since the coin at index 
moves if there are ![\[2\sum_{i=1}^k a_ i - 2\sum_{i=1}^ki + k = 2\sum_{i=1}^k a_ i - k^2\]](http://latex.artofproblemsolving.com/a/7/1/a71221433f949cb993786e3e0d6fc2958cdc3a6d.png)
steps. Now, if we sum this over all possible arrangements of the ![\[-k^2 \cdot {n \choose k} + 2\sum_{i=1}^ni\cdot{n - 1 \choose k - 1} = n(n+1){n -1 \choose k-1} - nk{n-1 \choose k-1}\]](http://latex.artofproblemsolving.com/e/a/0/ea03100c981034fb8aacb138bc37becf759c884f.png)
Now, summing this over all possible values of ![\begin{align*}
S &= \sum_{k=0}^n\left[n(n+1){n -1 \choose k-1} - nk{n-1 \choose k-1}\right] \\
&= n(n+1)\sum_{k=0}{n-1 \choose k -1} - n \sum_{k=0}^n k {n-1 \choose k - 1} \\
&= n(n+1)\cdot 2^{n-1} - n \cdot (n+1)2^{n-2} \\
&= n(n+1) \cdot 2^{n-2} \\
\end{align*}](http://latex.artofproblemsolving.com/a/0/6/a06f585792f7cb44360f0ec880ee078362086f64.png)
Therefore, the average number of steps over all ![\[\frac{n(n+1) \cdot 2^{n-2}}{2^n} = \boxed{\frac{n(n+1)}{4}}\]](http://latex.artofproblemsolving.com/2/f/b/2fb977afd094d0d28e18376944a2b15d2c33ce97.png)
and we are done.
,
,
.
total letters and half are 
.
,
steps, where 
.
,
and consider a configuration of 
coins: if it finishes on an 
more than the previous 
configuration (which will have 
,
as a result. Then, we add that remaining 
.
steps, then it will go up 
steps, then it will go down 
and up 
,
.
,
and up 
,
,
,
,
.
via 
.
.
.
s
.
,
the 
s
gives 
and the new process is just the old process on the 
as the states tree of this process for 
we see that the 
are cycleless.
is cycleless. Then 
has two components. The states tree for all sequences ending in 0 is the same as the states tree 
just with a 0 tagged onto the end of each vertex. The states tree of the transformed sequences ending in 1 is the same as the states tree 
.![$E[X_n]$](http://latex.artofproblemsolving.com/6/7/7/677f93928c7cf2f08761c95b8de2fad53b983392.png)
be the expected number of steps taken for ![$$E[X_n]=\frac{2E[X_{n-1}]+n}{2}=E[X_{n-1}]+\frac{n}{2}$$](http://latex.artofproblemsolving.com/2/9/e/29e8a70da5b250885ed2d2f15c081ced7f17d1e7.png)
with ![$E[X_1]=\frac{1}{2}$](http://latex.artofproblemsolving.com/9/9/d/99d312a9ea65f0d2a5f600ab19dede909a31416c.png)
so substituting we see that ![$E[X_n]=\frac{n(n+1)}{4}$](http://latex.artofproblemsolving.com/9/e/9/9e9e6d2361140f8d2cbcad304790a1e5fbf488f6.png)
.
is equal to 
.
and 
is easy. Define 
as the sum over all of the 
is some arbitrary configuration of length 
.
cases, namely the case where 
is at the end of the configuration, the case where the first letter is 
and the last 
for the case where 
,
configurations of 
(since we can just ignore that final coin).
,
,
coins which have 
,
,
moves needed for it to become 
since all the coins have to become ![\[S(n) = 2S(n-1) + 2^{n-2} \cdot 2n \ \text{for all \(n \geq 3\)}, \quad S(1) = 1, \quad S(2) = 6\]](http://latex.artofproblemsolving.com/d/6/a/d6aa740a8dc87e38fb907472c62bee79a1997b18.png)
It is easy to see that this is fulfilled by 
.
