I came up with this problem inspired by the limitations of an old non-scientific calculator I owned years ago (the two registers were the display, and an internal memory for an additional number).

We have a primitive calculator with only two registers $R_1$ and $R_2$, and the following four operations:

  • $R_1+R_2\to R_2$ (add the content of register $R_1$ to register $R_2$.)

  • $-R_1+R_2\to R_2$ (subtract the content of register $R_1$ from register $R_2$.)

  • $R_1+R_2\to R_1$ (add the content of register $R_2$ to register $R_1$.)

  • $R_1-R_2\to R_1$ (subtract the content of register $R_2$ from register $R_1$.)

For instance, if $R_1=x$ (register $R_1$ contains number $x$) and $R_2=y$ ($R_2$ contains $y$), after applying the operation $R_1+R_2\to R_2$ we end up with $R_1=x$ and $R_2=x+y$.

Assume that initially we have $R_1=x$ and $R_2=y$, where $x$ and $y$ are arbitrary numbers. For each of the following tasks describe a sequence of operations that would allow us to perform it, or prove that the task cannot be performed (task 1 is very easy, the real challenge is about task 2):

  • Task 1. Swap the contents of registers $R_1$ and $R_2$ changing the sign of $y$ in the process, so we would end up with $R_1=-y$, $R_2=x$.

  • Task 2. Swap the contents of registers $R_1$ and $R_2$, so that we would end up with $R_1=y$, $R_2=x$.


Task 1 was answered. Task 2:

Not possible. We always have $\begin{bmatrix}R_1 \\ R_2\end{bmatrix} = M\begin{bmatrix}x \\ y\end{bmatrix}$ for some matrix $M$ that depends only on the sequence of operations. Initially $M = \begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}$, and the given operations cause $M$ to be left-multiplied by $\begin{bmatrix}1 & 0 \\ 1 & 1\end{bmatrix}$, $\begin{bmatrix}1 & 0 \\ -1 & 1\end{bmatrix}$, $\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}$, and $\begin{bmatrix}1 & -1 \\ 0 & 1\end{bmatrix}$ respectively. All of these matrices have determinant $1$, so we will always have $\det M = 1$, which makes it impossible to reach the desired $\begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}$ with determinant $-1$.

| improve this answer | |
  • $\begingroup$ I had a feeling this was true. Very neat proof. $\endgroup$ – Dr Xorile Jan 3 '19 at 15:23

Task 1

1. $R_1 - R_2\to R_1$ (now $R_1 = x-y$, $R_2 = y$)
2. $R_1 + R_2\to R_2$ (now $R_1 = x-y$, $R_2 = x$)
3. $R_1 - R_2\to R_1$ (now $R_1 = -y$, $R_2 = x$)

| improve this answer | |
  • 2
    $\begingroup$ Task 2 the second operation isn't in the list of allowed operations $\endgroup$ – Dr Xorile Jan 3 '19 at 6:26
  • 2
    $\begingroup$ @DrXorile Oops, so it seems... $\endgroup$ – jafe Jan 3 '19 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.