# 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.\)