Tic-Tac-Collatz

Question

Have you ever heard of the Collatz conjecture? Just in case you haven't, I'll summarize it for you! Take any positive integer $n$, if it is even then simply divide it by $2$; however, if it is odd, multiply it by $3$ and add $1$. With that out of the way, I recently had the delightful idea of implementing this conjecture in a $3$x$3$ grid and having it influence adjacent cells:

The rules of the grid a pretty simple:

1. Only the central cell is populated to start with.
2. Tapping a cell will apply the conjecture to the targeted cell.
3. Tapping a cell will apply the conjecture to all adjacent cells.
4. Tapping a cell will activate all inactive adjacent cells with half of the invoking cell's value.

Clarifications

1. The answer will define a strategy that ensures the minimum number of moves will be used for any starting $n$. _[1]
2. If you tap on a $1$, any inactive adjacent cells will remain inactive.

_{1: The minimum number of moves for any $n$ cannot be easily defined due to the nature of the conjecture. However, a strategy can be employed that finds the minimum number of moves for any $n$.}

---

What is the minimum number of moves, for any positive integer $n>1$, that will ensure every cell contains a $1$?

_{Note: An interactive version of this puzzle exists for your convenience.}

Answer 1

Let function 𝑓 output the number of "Collatz steps" needed for its input to reach 1, if possible (A006577). Let 𝑥 = 𝑓(𝑛) and 𝑦 = 1 + 𝑓(𝑛 / 2). Let 𝑧 be the remainder of 𝑥 - 𝑦 when divided by 3 (0, 1, or 2).

We use the following procedure:

1. Tap the center until its neighbors show 2^𝑧+2.
2. Tap each of the center's neighbors once.
3. Tap each corner 𝑧 times.
4. Tap the center until it shows 1.

This procedure ensures that

• the corners end up showing 1, and
• the parity (w.r.t. the 3-cycle 4, 2, 1) of the center matches that of its neighbors so that they line up and show 1 simultaneously.

Now we count the number of moves used.

Case 1: 𝑥 ≥ 𝑦 + 𝑧 + 3

We need at least 𝑥 moves on the center. Tapping each corner once costs 4 moves that don't act on the center.

Moves:

𝑥 + 4𝑧

Case 2: 𝑦 + 𝑧 ≥ 𝑥

We need at least 𝑦 moves on each center neighbor. Tapping the center acts on all four neighbors at once. Tapping each center neighbor once uses 4 moves but only acts on each center neighbor once, thereby costing 3 moves. Tapping each corner once uses 4 moves but only acts on each center neighbor twice, thereby costing 2 moves.

Case 2a: 𝑧 = 0 or 𝑧 = 1

We tap on each center neighbor once (+3) and each corner 𝑧 times (+2𝑧).

Moves:

𝑦 + 3 + 2𝑧

Case 2b: 𝑧 = 2

We tap on each center neighbor once (+3) and each corner twice (+4). Also, this is the only case where we overshoot the longest cycle, i.e., the center neighbors go through 1, 4, 2, 1, thereby wasting another 3 moves.

Moves:

𝑦 + 10

---

Addendum: For some small 𝑛 (2, 4, or 5), there is an extra cost of 3 moves because the center neighbors start off too small, requiring an extra 3-cycle.

Addendum 2: If 𝑛 = 9, then 𝑧 = 1 so we should make the center neighbors show 8 after Step 1, but they start off too small at 4. If we skip Step 1, then the corners are 1 farther ahead in the 3-cycle than they should be, so we need to repeat Step 2 to compensate (by hitting each corner twice). Fortunately, this doesn't affect the number of moves needed because 𝑓(9) is so large. A similar change is needed for 𝑛 = 17 (where 𝑧 = 2).

Answer 2

Starting with $n=2$

Seven moves.

- - -   - 1 -   - 4 -   2 2 2   2 2 2   1 2 2   1 2 1   1 1 1
- 2 -   1 1 1   4 4 4   4 2 4   4 1 4   2 4 4   2 2 2   1 1 1
- - -   - 1 -   - 4 -   - 4 -   2 2 2   1 2 2   1 2 1   1 1 1