# 50-50 chance

Discrete Mathematics Level pending

An infinite string $$a_1 a_2 a_3 \ldots$$ of $$x$$'s and $$y$$'s is constructed as follows:

Step 0. $$a_1 =x.$$

Step $$n, (n > 0).$$ If $$a_n = x,$$ append $$xy$$ to the end of the sequence. If $$a_n = y,$$ append $$yx$$ to the end of the sequence.

What is $$a_{1000}?$$

The next few steps are shown here for reference.

Step 1. Since $$a_1 = x,$$ the string $$xy$$ is appended to the end so the sequence becomes $$xxy.$$

Step 2. Since $$a_2 = x,$$ the string $$xy$$ is appended to the end, so the sequence becomes $$xxyxy.$$

Step 3. Since $$a_3 = y,$$ the string $$yx$$ is appended to the end, so the sequence becomes $$xxyxyyx.$$

×