0

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$?

Gerard
  • 4,264
  • The last equation is not necessarily true because we can take $x=4$, $y=6$ and $z=12$ and we get $197<169$ – Quimey Jul 18 '13 at 14:43
  • Yes, we have to essentially prove that $x^2 + y^2 + z^2 \neq 169$. But, I assumed that $x^2 + y^2 + z^2 < 169$ and set out to prove that. – Gerard Jul 18 '13 at 14:45

3 Answers3

1

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.

gt6989b
  • 54,422
1

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

Ross Millikan
  • 374,822
  • What do you mean by 'minimum values'? – Gerard Jul 18 '13 at 14:46
  • 1
    You must have $x \ge 4-\frac 1{\sqrt 3}$ and similar relations for $y,z$. If you square those and add them up, that is the minimum value $x^2+y^2+z^2$ can take, and is greater than $169$ – Ross Millikan Jul 18 '13 at 15:22
  • Yes, that's right. I was thrown off by the absolute value. Thanks. – Gerard Jul 18 '13 at 15:27
  • 1
    You have shown that all reachable values are on a sphere of radius 13. The problem asks if you can reach a value within a cube centered at $(4,6,12)$ of side $\frac 2{\sqrt 3}$ Essentially you are proving that there is no intersection between these. If there were an intersection, you wouldn't know if you could reach such a point or not (at least not this way). – Ross Millikan Jul 18 '13 at 15:37
1

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.

Quimey
  • 3,180