There is a neat N-ary puzzle that has a solution that follows a 5-ary Gray code. https://www.schwandtner.info/publications/Kugellager.pdf
It's not the typical reflected Gray code but still seems to go through all the numbers 00..0 to 44..4, one transition at a time.
The rules are as follows (taken from the above pdf but starting at 0 index rather than 1 index)
| Transition | Lower numbers must be | Higher numbers must be |
|---|---|---|
| 0 -- 1 | 4 | 0 or 1 or 4 |
| 1 -- 2 | 0 | 0 or 1 or 2 |
| 2 -- 3 | 0 or 1 or 4 | any |
| 3 -- 4 | 0 or 1 or 2 | any |
I would like to prove that these rules do in fact produce a Gray code for any length n, but am having trouble since a transition depends on the lower and upper numbers. In the above paper, they confirm this is the case for n = 1,2,3,4.
One thing I've tried is to show that every number besides 00..0 and 44..4 has exactly two neighbors but that's not enough to prove they all lie on the same line (there could be a line and multiple cycles, and they'd still have the property of only 2 neighbors).
Thanks for your help!
I'll attempt to prove that |$0^n$ to $4^n$| = $5^n$
Notation:
I break up the sequence into parts:
[$2^j*0*0^k$, $2^{j+1}*0^k$) = [$2^j*0*0^k$, $4^j*0*4^k$] + [$4^j*1*4^k$, $2^j*1*0^k$],
e.g. [0000, 0444], [1444, 1000], [2000, 4044],[4144, 2100],[2200, 4404],[4414, 2210],[2220, 4440],[4441, 2221],[2222, 4444]
Since each transition is reversible, |A to B| = |B to A|, so we can look at the following
[$2^j*0*0^k$ to $4^j*0*4^k$]
[$2^j*1*0^k$ to $4^j*1*4^k$]
Since 0 and 1 are allowed as higher digits in all rules, and as lower digits in transitions from 2-3 and 3-4, the above two ranges will have the same size.
$Lemma$
|$2^j*x*0^k$ to $4^j*x*4^k$| = $5*|2^j*x*0^{k-1}$ to $4^j*x*4^{k-1}|$, where x = 0 or 1, $j>=1$, $k>=1$
(basically this says that if we have something like [2221000, 4441444], we can remove the trailing 0 and trailing 4, and count 5*|222100 to 444144|)
$Proof$
Key oberservation #1
Let's say you have a string [234]* x [01234]*, where x = 0 or 1 and everything to the left of x is 2 or higher, and the right can be anything. If we look at the moves where x remains the same, we can essentially ignore x since x will never cause a rule to get excluded. We can then count the transitions of x by recursively using the counts of the (n-1) string where we ignore x.
Key oberservation #2
The other key idea is that if there is a run of repeated high order digits, such as 222..2, then the digits below the run will behave the same as if it were a single 2. This will also help us to use recursion.
Let |$2^j*x*0^{k-1}$ to $4^j*x*4^{k-1}$| = c, where x = 0 or 1.
Then
|$2^j*0*0*0^{k-1}$ to $4^j*0*0*4^{k-1}$| = c (since we can ignore the left most 0 by key #1)
|$4^j*0*1*4^{k-1}$ to $2^j*0*1*0^{k-1}$| = c (this time counting down and ignoring the left most 0 by key #1)
|$2^j*0*2*0^{k-1}$ to $4^j*0*4*4^{k-1}$| = 3c (this time we don't ignore the leftmost 0. Instead, we ignore the digit to the right of it. To move the rightmost 2 in the 2^j, we need to make c moves of the lower digits to move the ignored term from 2-3, c more moves to move it 3-4, then c more moves to get the lower digits back to a position where we can move the rightmost 2 in the 2^j term from 2 to 3. Same applies to other transitions, so we always need to make 3c moves to move that position. This reasoning uses key observation #2.
So c+c+3c = 5c, which is what we set out to prove.
The same argument applies when the digit to the right of the leading 2s is a 1 rather than a 0.
Note that if $k = 0$ or $k=-1$, the above argument can't be used, but it's easy to see that |$2^{j-1}0$ to $4^{j-1}0$| = $3^{j-1}$ and |$4^{j-1}1$ to $2^{j-1}1$| = $3^{j-1}$, and also |$2^j$ to $4^j$| = $3^j$, because it is a reflected Gray code with alphabet {2,3,4}.
We also have the special case j=0, but in that case |$x*0^{k-1}$ to $x*4^{k-1}$| = |$0^{k-1}$ to $4^k{k-1}$|, which we assume to be $5^{k-1}$ by induction.
We now have counts of all the components and can add them together.
A recursive pattern emerges:
n = 1: $5^0 + 5^0 + 3^1 = 5 = 5^1$
n = 2: $5^1 + 5^1 + 2*3^1 + 3^2 = 25 = 5^2$
n = 3: $5^2 + 5^2 + 5*2*3^1 + 2*3^2 + 3^3 = 125 = 5^3$
n = 4: $5^3 + 5^3 + 5^2*2*3^1 + 5*2*3^2 + 2*3^3 +3^4 = 625 = 5^4$
The last two terms are for [$2^{n-1}0$, $2^{n-1}1$] and [$2^n$, $4^n$]. The other terms are 5 times the term above them as shown in the proof.
In general
$F(n) = 5*(F(n-1) - 3^{n-1}) + 2*3^{n-1} + 3^n$
$= 5*F(n-1) - 5*3^{n-1} + 2*3^{n-1} + 3^n$
$= 5*F(n-1) - 3*3^{n-1} + 3^n$
$= 5*F(n-1) = 5*5^{n-1} = 5^n$
The last step uses induction where we have base case $F(1) = 5$ and the inductive assumption $F(n-1) = 5^{n-1}$
These facts together should be sufficient to prove it's a gray code:
Therefore you can create a path starting at $0^n$ and ending at $4^n$ that is $5^n$ distinct numbers long where each number differs from the previous one by a 1 digit transition, which satisfies the characteristics of a Gray code.