Skip to content

Instantly share code, notes, and snippets.

@masak
Created February 2, 2011 11:07
Show Gist options
  • Save masak/807554 to your computer and use it in GitHub Desktop.
Save masak/807554 to your computer and use it in GitHub Desktop.
Solving daxim's problem
G(0) = 1
G(1) = mex(G(0)) = 0
G(2) = mex(G(0), G(1)) = 2
G(3) = mex(G(0), G(1), G(2)) = 3
G(4) = mex(G(0), G(1), G(2), G(3)) = 4
G(5) = mex(G(1), G(2), G(3), G(4)) = 1
G(6) = mex(G(2), G(3), G(4), G(5)) = 0
G(7) = mex(G(3), G(4), G(5), G(6)) = 2
= 3
= 4
So, G( $n ) := $m < 2 ?? 1 - $m !! $m
where $m = $n % 5
G(21) = 0 by this rule. Don't move first in that game.
The 5 there is simply $MAX + 1, where $MAX was 4 in this case.
Let's try and generalize for $MIN as well. Here's one case where
$MIN == 2 and $MAX == 5:
G(0) = 1
G(1) = 1
G(2) = 0
G(3) = mex(G(1)) = 0
G(4) = mex(G(1), G(2)) = 2
G(5) = mex(G(1), G(2), G(3)) = 2
G(6) = mex(G(1), G(2), G(3), G(4)) = 3
G(7) = mex(G(2), G(3), G(4), G(5)) = 1
G(8) = mex(G(3), G(4), G(5), G(6)) = 1
= 0
= 0
= 2
= 2
So, the period is 7, which is $MIN + $MAX. The G($n) numbers occur in pairs,
except the 3, which is cut off by the modulus. The parising is probably due to
$MIN being 2. So i postulate the following formula, which covers all the data so far:
G( $n ) := $d < 2 ?? 1 - $d !! $d
where $d = floor($m / $MIN)
and $m = $n % ($MIN + $MAX)
In other words, try to be the next on turn for all games except those where
floor(($n % ($MIN + $MAX)) / $MIN) == 1.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment