Problem $1.(10$ points$)$ Recall the following LCS Theorem.

Theorem. Let $Z=($:$z_1,z_2,$dots,$z_k$:$)$ be an $LCS$ of $(x,Y).$

If $x_m=y_n,$ then $z_k=x_m=y_n$ and $Z_{k-1}$ is an $LCS$ of $(x_{m-1},Y_{n-1})$

If $x_m{y}_n$ and $z_k{x}_m,$ then $Z$ is an $LCS$ of $(x_{m-1},Y)$

If $x_m{y}_n$ and $z_k{y}_n,$ then $Z$ is an $LCS$ of $(x,Y_{n-1}).$

a$)(5$ points$)$ Prove Case $3.$

b$)(5$ points$)$ The proof of Case $2$ tells us that if $z_k{x}_m,$ this implies $Z$ is a subsequence

of $x_{m-1}.$ Prove whether or not the converse is true. In other words, is the following

true or false: if $Z$ is a subsequence of $x_{m-1},$ then we know $\frac{z_k}{x_m}.$