4
$\begingroup$

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:

Screenshot of a 3x3 grid where the cells read from left to right, top to bottom, are 4, 2, 1, 4, 1, 2, 4, 4, 4.

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.

$\endgroup$
6
  • $\begingroup$ I know a grid of $1$s is possible because, given a starting value of $9$, I've done it in 23 moves; however, this is likely not the optimal solution. $\endgroup$ Feb 27 at 23:08
  • 1
    $\begingroup$ @noedne added clarification for this. Due to integer division, the cell remains inactive since the result of $1 \div 2$ is $0$. $\endgroup$ Feb 28 at 0:23
  • 1
    $\begingroup$ @bob I'll gladly look into doing so, though I'm not sure it could be truly random. I think there will have to be some form of strategic randomization to ensure the grid is solvable, especially for it to be interesting lol the interactive version is linked at the bottom if you're interested though 😁 $\endgroup$ Feb 28 at 14:49
  • 1
    $\begingroup$ Initially I thought that this is a standard lights-out kind of puzzle, which means that the order the buttons are pressed don't matter and that you can solve it optimally with usual techniques. But after thinking about it for a long time I realised that this is not the case. Since you made inactive cells take half the value of the active neighbour, order DOES matter. So you can't solve it with usual techniques. Well to be more precise, usual techniques will give you a good solution, but it may not be optimal. $\endgroup$ Mar 2 at 6:22
  • 1
    $\begingroup$ Now if you replace cell.value = parseInt(tile.value / 2); with something like cell.value = 1; then it will become a standard lights-out puzzle, where order of button presses doesn't matter. $\endgroup$ Mar 2 at 6:27

2 Answers 2

6
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ These small edge cases are a tad annoying to shoehorn in. $\endgroup$
    – noedne
    Feb 28 at 3:08
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ A similar solution exists with $n=3$ $\endgroup$ Feb 28 at 0:15
  • $\begingroup$ While this is a great number of moves, it doesn’t answer the any $n$ question. $\endgroup$ Feb 28 at 0:15
  • 1
    $\begingroup$ @Taco Well, now you have changed the question. Tsk tsk., $\endgroup$ Feb 28 at 0:29
  • $\begingroup$ Well, not changed, just clarified. $\endgroup$ Feb 28 at 0:30

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.