Prove that an algorithm cannot reach a given goal

Question

We are given an algorithm that, in each step takes a set $\left\{a, b, c\right\}$ It takes any two variables $a, b$ at random and changes them to $0.6 + 0.8b$ and $0.8a - 0.6b$. The initial value of the algorithm is $\left\{3, 4, 12\right\}$. Prove that the algorithm cannot reach $\left\{x, y, z\right\}$ where $|x - 4|, |y - 6|, |z - 12| < \frac{1}{\sqrt3}$.

I realized straight away that this could be solved using invariance. The invariant was easy to find: It was the function $f_i(a, b, c) = a^2 + b^2 + c^2$. This function gives the same value for any step $i$ of the algorithm. $f(3, 4, 12) = 169$.

It remained to prove that $x^2 + y^2 + z^2 \neq 169$. Now, I started off by adding the inequalities given in the statement:

$(x - 4)^2 + (y - 6)^2 + (z-12)^2 < 3\left(\frac{1}{\sqrt3}\right)^2 = 1$

$\implies x^2 + 16 - 8x + y^2 + 36 - 12y + z^2 + 144 - 24z < 1$

$\implies x^2 + y^2 + z^2 < 8x + 12y + 24z - 195$

This is where I was stuck. How do I prove that $8x + 12y + 24z - 195 < 169$?

Answer 1

Good start. Now what are the minimum values that $x,y,z$ can take? Add their squares and you are home.

Answer 2

You are transforming via multiplication by the matrix: $$ \begin{bmatrix} .6 & .8 & 0\\ .8 & -.6 & 0\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix}. $$ So the third element always stays fixed at it's initial value. The motion of the first two is given by the matrix $$ A = \begin{bmatrix} .6 & .8\\ .8 & -.6 \end{bmatrix}, \text{ and } A^2 = I. $$ Therefore, the first two elements will oscillate between $(3,4)$ and $(5,0)$ while the third one stays the same at 12. Your conclusions follows immediately.

Answer 3

You should study the function $f(x,y,z)=x^2+y^2+z^2$ in the domain $[4-\frac{1}{\sqrt{3}}]\times [6-\frac{1}{\sqrt{3}}]\times [12-\frac{1}{\sqrt{3}}]$. It is "obvious" (but you can prove it using, for instance, lagrange multipliers) that the minimum of the function is $f(4-\frac{1}{\sqrt{3}},6-\frac{1}{\sqrt{3}},12-\frac{1}{\sqrt{3}})=197-\frac{44}{\sqrt{3}}\sim 171.59$, so that $169$ is not in the image.