1. Professor Baltazar has a machine that is programmed in the following way:

$>$ a natural number $n$ is written into the machine (zero is not a natural number),

$>$ if the number $n$ is even, the machine divides it by 2 and prints the result, and

$>$ if the number $n$ is odd, the machine multiplies it by 3, adds 1 to the resulting number, and prints the result.

Professor Baltazar wrote a number into the machine, then wrote the printed result back into the machine, and repeated this process several times. After the sixth entry, the machine printed the number 4. Determine all possible initial values that Professor Baltazar could have written into the machine.
## Solution.

The way the machine works can be illustrated as follows:

| input | $n$ |  |
| :---: | :---: | :---: |
|  | $n$ is an even number | $n$ is an odd number |
| output | $n: 2$ | $3 \cdot n+1$ |

If the result is $m$, then the input could have been $2m$ or $(m-1) : 3$, depending on whether the entered number is even or odd.

The result 4 can appear if the input number was $8 = 2 \cdot 4$ or the number $1 = (4-1) : 3$.

The result 8 can only be obtained from the number 16, because the number $8-1=7$ cannot be divided by 3 without a remainder. The number 1 can only be obtained from the number 2, because the input cannot be 0.

The result 16 can be obtained in two ways, if the input is 32 or 5.

By similar reasoning, we get a "tree" of possible intermediate results all the way to the initial numbers.

The initial values that Professor Baltazar could have entered into the machine are: 4, 5, 6, 32, 40, 42, and 256.

![](https://cdn.mathpix.com/cropped/2024_05_30_9fa22177d42fb47260cfg-2.jpg?height=924&width=1567&top_left_y=110&top_left_x=276)