Hallar los múltiplos de tres con unas sencillas reglas

Question

El otro día nos plantearon este problema y me parece que está un poco por encima de mis posibilidades, así que he pensado en compartirlo aquí para cualquier posible consejo o ayuda :). El problema es el siguiente:

Inicialmente, $x = 1$ . Para cada iteración, puede ejecutar uno de los siguientes comandos:

1. $x = x + 3$

2. $x = 2x$

Generar un conjunto de instrucciones que sea capaz de producir un $x$ estado que es un múltiplo de 3.

He hecho unas primeras pruebas y parece que no hay soluciones posibles, pero estoy atascado intentando "probarlo".

Gracias de antemano :)

Answer 1

No es posible hacerlo. Dado un número entero $x$ tal que $$x\equiv1 \mod 3,$$ entonces $$2x\equiv2 \mod 3\qquad \text{ and }\qquad x+3\equiv1 \mod 3.$$ Análogamente, dado un número entero $x$ tal que $$x\equiv2 \mod 3,$$ entonces $$2x\equiv1 \mod 3\qquad \text{ and }\qquad x+3\equiv2 \mod 3.$$

Así que a partir de $x=1$ no se puede obtener un múltiplo de 3 con tales operaciones.