Finding multiples of three given a few simple rules

Question

We were given this problem the other day and it seems a little over my head, so I thought I'd share it here for any possible advice or assistance :). The problem is as follows:

Initially, $x = 1$. For each iteration, you may execute one of the following commands:

1. $x = x + 3$

2. $x = 2x$

Generate a set of instructions that is able to yield a final $x$ state that is a multiple of 3.

I've done some initial testing and there appears to be no possible solutions, but I'm stuck trying to "prove" it.

Thanks in advance :)

Answer 1

It is not possible to do that. Given an integer $x$ such that $$x\equiv1 \mod 3,$$ then $$2x\equiv2 \mod 3\qquad \text{ and }\qquad x+3\equiv1 \mod 3.$$ Analogously, given an integer $x$ such that $$x\equiv2 \mod 3,$$ then $$2x\equiv1 \mod 3\qquad \text{ and }\qquad x+3\equiv2 \mod 3.$$

So starting at $x=1$ you cannot obtain a multiple of 3 with such operations.