$a_1, a_2, a_3, a_4, a_5$

a)
$a_1 < a_2$

$a_1 < a_3$

$a_1 < a_2 < a_3$ - NA

$a_3 < a_1 < a_2$

# Problem 2

# Problem 3

 1 2 3
|x|x|x|x|
| | | |x|
| | | |x|
| | | |x|
 
| |x|
|x| |

{1,1}
{2,2}
{3,3}

{1,3}

{1,1}

{3,3}
{4,4}

# Problem 4

$n+1 = 1$

$a^{n+1} = {a^0 * a^0}/{a^{0-1}}$

# Problem 7

ZB => Z, B
ZZ => 3Z
BB => Z, 2B

---

1st
200Z 800B
x(Z B) + yB

2nd
(Z B) +

x(Z B) + (yB + y/2 Z)

(x+y/2)Z, (x+y/2)B + y/2 B
(x+y)Z, (x+y)B + yB
which means,
()
---

z_gen(n) = ZB gen(min(n_b,_n_z)) + ZZ gen()3 + BB gen(n-1)

b_gen(n) = ZB gen(n-1) + BB gen(n-1)2

Base case:

$$
\begin{align}
z_0 = 200 \\
b_0 = 800 \\
b_0 - z_0 ≥ 0 \\
\end{align}
$$

Hyp:

$$
b_n - z_n ≥ 0
$$

Induction step:

Let $m_n = min(z_n, b_n)$. Since $b_n ≥ z_n$ by hypothesis, $m_n = z_n$.

Then we have

$$
\begin{align}
z_{n+1} = m_n + \lfloor(z_n - m_n) / 2)\rfloor \cdot 3 + \lfloor(b_n - m_n) / 2 \rfloor \\
= m_n + \lfloor(b_n - m_n) / 2 \rfloor \\\text{(since z_n = m_n, the second floor evaluates to 0)}
\end{align}
$$

And,

$$
b_{n+1} = m_n + \lfloor(b_n - m_n) / 2 \rfloor * 2
$$

Therefore,

$$
\begin{align}
b_{n+1} - z_{n+1} \\
= \lfloor(b_n - m_n) / 2 \rfloor \cdot 2 - \lfloor(b_n - m_n) / 2 \rfloor \\
= \lfloor(b_n - m_n) / 2 \rfloor \\
≥ 0 \\ \text{ (since m_n = z_n and b_n - m_n ≥ 0)} \\
\end{align}
$$