,
,
,
,
or even expressions of those terms combined as if that would make them defined. I have made this post to answer these questions once and for all, and I politely ask everyone to link this post to threads that are talking about this issue.
,
isn't even rigorously defined in this expression. What exactly do we mean by 
.
,
does not exist in the first place, although you will see why in a calculus course. So the point is that 
?
indeterminate? In analysis (the theory behind calculus and beyond), limits involving an algebraic combination of functions in an independent variable may often be evaluated by replacing these functions by their limits. However, if the expression obtained after this substitution does not provide sufficient information to determine the original limit, then the expression is called an indeterminate form. For example, we could say that 
,
or ![\[0/0, \infty/\infty, \infty-\infty, \infty \times 0\]](http://latex.artofproblemsolving.com/2/6/0/260f97a1cf1ea8722ff97a29b83bac7bfe83e577.png)
etc etc. So what makes something undefined? In the broader scope, something being undefined refers to an expression which is not assigned an interpretation or a value. A function is said to be undefined for points outside its domain. For example, the function 
given by the mapping 
is undefined for 
.
is undefined because dividing by ![\[\overline{\mathbb{R}}=\mathbb{R}\cup \{-\infty,+\infty\}.\]](http://latex.artofproblemsolving.com/9/9/3/993c78b62ec2c84b5d77daa8e9a8cd6f70fcf904.png)
So instead of treating infinity as an idea, we define infinity (positively and negatively, mind you) as actual numbers in the reals. The advantage of doing this is for two reasons. The first is because we can turn this thing into a totally ordered set. Specifically, we can let 
for each 
which means that via this order topology each subset has an infimum and supremum and 
is therefore compact. While this is nice from an analytic standpoint, extending the reals in this way can allow for interesting arithmetic! In ![\begin{align*}
a + \infty = \infty + a & = \infty, & a & \neq -\infty \\
a - \infty = -\infty + a & = -\infty, & a & \neq \infty \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \pm\infty, & a & \in (0, +\infty] \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \mp\infty, & a & \in [-\infty, 0) \\
\frac{a}{\pm\infty} & = 0, & a & \in \mathbb{R} \\
\frac{\pm\infty}{a} & = \pm\infty, & a & \in (0, +\infty) \\
\frac{\pm\infty}{a} & = \mp\infty, & a & \in (-\infty, 0).
\end{align*}](http://latex.artofproblemsolving.com/6/d/8/6d8fc1eca5c791d430a7168cd3b37a02104fa318.png)
So addition, multiplication, and division are all defined nicely. However, notice that we have some indeterminate forms here which are also undefined,![\[\infty-\infty,\frac{\pm\infty}{\pm\infty},\frac{\pm\infty}{0},0\cdot \pm\infty.\]](http://latex.artofproblemsolving.com/a/0/b/a0b67076efcc014c78b2023be1151c84b57c1503.png)
So while we define certain things, we also left others undefined/indeterminate in the process! However, in the context of measure theory it is common to define 
as greenturtle3141 noted below. I encourage to reread what he wrote, it's great stuff! As you may notice, though, dividing by ![\[\mathbb{C}^*=\mathbb{C}\cup\{\tilde{\infty}\}\]](http://latex.artofproblemsolving.com/8/4/e/84ed3d6ab237df970333b87beaef5311caa46185.png)
which we call the Riemann Sphere (it actually forms a sphere, pretty cool right?). As a note, 
means complex infinity, since we are in the complex plane now. Here's the catch: division by ![\[\frac{z}{0}=\tilde{\infty},\frac{z}{\tilde{\infty}}=0.\]](http://latex.artofproblemsolving.com/1/6/0/160cb939707708ff4e0930724df2928af11d7fd1.png)
where 
and 
Furthermore, we actually have some nice properties with multiplication that we didn't have before. In 
it holds that![\[\tilde{\infty}\times \tilde{\infty}=\tilde{\infty}\]](http://latex.artofproblemsolving.com/8/e/0/8e035b4841d20c5ad671c46355cc667ca01e533b.png)
but 
and 
are left as undefined (unless there is an explicit need to change that somehow). One could define the projectively extended reals as we did with ![\[{\widehat {\mathbb {R} }}=\mathbb {R} \cup \{\infty \}.\]](http://latex.artofproblemsolving.com/c/0/4/c044ff37849acad3b8b280b9753539225a1276ca.png)
They behave in a similar way to the Riemann Sphere, with division by 
let 
and 
denote the feet of the altitudes from 
and 
intersect circumcircle 
.
intersect circumcircle 
.
and 
passes through the orthocenter of triangle 
,
,![\[
a_{2k+1} = 2 + 2a_k, \quad a_{2k+2} = 2 + a_k + a_{k+1},
\]](http://latex.artofproblemsolving.com/4/e/c/4ec892df19b4ec97af9bb1e5d1954e6c26be3172.png)
for all integers 
.
such that![\[
\frac{a_n}{n}
\]](http://latex.artofproblemsolving.com/3/d/1/3d1d012e7c41e1e09abd14626a79b1fb1cbab34d.png)
is an integer.
,
to the equation![\[
\frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n} + \frac{1}{x_1 x_2 \cdots x_n} = 1
\]](http://latex.artofproblemsolving.com/5/c/4/5c40a3f0eaa58e438c8dcaad395d7ab9e8f4f439.png)
be the incenter of triangle 
.
,
,
be the orthocenters of triangles 
,
,
,
,
,
,
.
.
units of effort to gain 
points on the 
,
units of effort to gain 
points on the 
,
.
points on 
and 
points on 
to make 
and 
intersect at the point 
.
?
,
.
are chosen from 0 to 1. What is the probability that their positive difference is more than 
?
?
families, there are 
children respectively. If a random child from any of the families is chosen, what is the probability that the child has 
siblings? Express your answer as a common fraction.[/quote]
,
such that 
.
,
lies on diagonal 
such that 
.
.
has 
,
,
.
.
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 
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 
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 
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 
.
