5
$\begingroup$

Queen Shayra does not have the most impressive following, but she intends to expand her influence. If she could settle down at the center of an N Dimensional 3-Cube and build a palace there, she would attract all sorts of interesting folk to her realm. Of course, before she may build a palace, she needs to make sure that the N Dimensional 3-Cube is fit for colonization (no rats, etc).

For this purpose she will send her Brave Knight on a journey over all 1-Cubes of a realm, except for the center, which is easy enough to deal with during the building process as it is only one cube. Brave Knight moves from cube to cube in chess knight jumps (two over in one direction, one in another), and he may not pass through a cube that he has been to already because Shayra is an optimization enthusiast.

For which $N$ is there a $3\times\dots\times3$ cube with such a path? Whenever for some $N$ such a path exists, construct it.

$\endgroup$
  • $\begingroup$ Does the knight have to return to his starting point? $\endgroup$ – Tryth Apr 7 '15 at 12:02
  • $\begingroup$ @Tryth, He does not. $\endgroup$ – Ben Frankel Apr 7 '15 at 12:05
  • $\begingroup$ What is considered the "center" if $N$ is even? $\endgroup$ – mdc32 Apr 7 '15 at 12:14
  • 1
    $\begingroup$ @mdc32, The center. Consider $N=2$, ie a 3x3 square, it is easy to pinpoint the center. Or, if we create a coordinate system where one corner is $(0, \dots, 0)$, then the center is $(1, \dots, 1)$. $\endgroup$ – Ben Frankel Apr 7 '15 at 12:17
  • 1
    $\begingroup$ @IvoBeckers, Thing is, it isn't possible to reach the center anyways. If it's possible to jump from the frame into the center, then it's also possible to jump from the center to the frame. This is clearly impossible, if we consider the direction where we move 2 over: we break out of the region. $\endgroup$ – Ben Frankel Apr 7 '15 at 12:43
7
$\begingroup$

The knight cannot succeed when $N$ is odd. Color the squares in checkerboard fashion, with a corner black. When $N$ is odd, the removed square is white, so there will be two more black squares altogether. Since tours must alternate colors, none can exist.

We prove by induction that, for even $N$, an $N$-palace (i.e. an $N$-cube with its center removed) can be cycled (toured, with start and end joined). This clearly holds when $N=2$.

Given an $N$ palace, its cells can be described with coordinates $(x_1,\dots,x_n)$, where $x_i$ are all either $0,1$ or $2$. Take any cell where $x_1=x_2=1$, and color it red. The red cells themselves form an $(N-2)$-palace. Furthermore, surrounding each red cell are 8 cells with coordinates $$ (*,*,x_3,\dots,x_{n}) $$ where the $*$’s can be anything (except both $1$, since that would be the central red cell), while the $x_i$ are fixed. These $8$ cells form a $2$-palace: I’ll refer to these as the “ring” around the red cell $(1,1,x_3,\dots,x_n)$. Color such squares black. Almost every cell is now colored. The remaining cells, the ones whose last $N-2$ coordinates are $1$, form a ring around the removed central cell: color these blue.

Here is the current situation, illustrated when $N=4$. The coordinates $(x,y,w,z)$ mean the following: $w,z$ tell you which slanted square you are in, and $x,y$ tell you your location in that square. $w$ is horizontal, $z$ vertical. $x$ is back/front, $y$ is vertical.

enter image description here

We first show how to cycle each color: then we combined these 3 disjoint cycles into one big one.

The blue cells themselsves can be toured (this is just the $N=2$ case). By induction, the red cells can be cyclically toured. The black cells can be toured as well: do this, hop from ring to ring, following the tour of the red cells. When you arrive at each ring, perform a tour of it. There are two ways to cycle around a ring: alternate these each time. This will ensure when you return to the ring around your first red cell, you will be in the correct “phase” (since you switch phase each time, and there an even number of red cells).

Now, we have partitioned the $N$-palace into three disjoint cycles, and we must combine these into one cycle. Any two disjoint cycles can be combined as long as there are consecutive points on one which are joined to two consecutive points on the other. Here is, for example, how the black cycle can be joined to the red. The $\dots$'s mean the rest of the coordinates are all 1. $$ \begin{array}{ccc} (0,1,1,0,\dots) &\to \stackrel{\text{black tour}}{\cdots}\to &(0,1,0,2,\dots)\\ \uparrow && \downarrow\\ \color{red}{(1,1,1,2,\dots)}&\color{red}{\leftarrow \stackrel{\text{red tour}}{\cdots}\leftarrow} &\color{red}{(1,1,0,0,\dots)} \end{array} $$ The blue cycle can be joined to the now black/red cycle via $$ \begin{array}{ccc} (0,2,2,1,\dots) &\to \stackrel{\text{black tour}}{\cdots}\to &(1,0,2,1,\dots)\\ \uparrow && \downarrow\\ \color{blue}{(0,0,1,1,\dots)}&\color{blue}{\leftarrow \stackrel{\text{blue tour}}{\cdots}\leftarrow} &\color{blue}{(1,2,1,1,\dots)} \end{array} $$

$\endgroup$
  • $\begingroup$ I agree with your first two spoilers, but your third is a bit lacking (also, irrelevant, I meant for the center cube to be the location for Shayra's palace while the rest is land for the peasants). You have left to explain how you reach all of the inductively tourable cubes in the right sequence, and maybe you jump from one tourable cube to another at a place where you simply cannot tour the whole thing (tourable may mean from corner to corner or something). $\endgroup$ – Ben Frankel Apr 7 '15 at 17:22
  • $\begingroup$ @BenFrankel I'll get back to you...great puzzle! $\endgroup$ – Mike Earnest Apr 7 '15 at 17:55
  • 1
    $\begingroup$ For a 3x3 square, imagine numbering it 1-9 (with the center being 5). Then the knight can traverse 1,6,7,2,9,4,3,8 And since 8 can traverse to 1, then ANY position on the outer ring can be completed with jumps. $\endgroup$ – Jiminion Apr 7 '15 at 18:52
  • $\begingroup$ @BenFrankel My construction has been filled in, though it is complicated. It's hard to paint an $N$-dimensional picture. I could certainly write a program to output the Hamiltonian cycle. $\endgroup$ – Mike Earnest Apr 8 '15 at 0:38
  • $\begingroup$ @Jiminion From the question: "he may not pass through a cube that he has been to already". By the time you get to 3 and want to go to 8, you need to pass through 2 or 6, both of which have been visited already. Is there a solution for $N=2$? I suspect not: having visited all but 1 squares, the final jump has to go through at least one other non-centre square, and there aren't any such unvisited squares left. $\endgroup$ – Lawrence Apr 8 '15 at 0:48
0
$\begingroup$

Color the center cube (i.e. (1, 1, 1, 1, ..., 1)) black. Color the two cubes (0, 1, 1, 1, ..., 1) and (2, 1, 1, 1, ..., 1) adjacent to the center red. Finally, color the six cubes (0, 0, 1, 1, 1, ..., 1), (0, 2, 1, 1, 1, ..., 1), (1, 0, 1, 1, 1, ..., 1), (1, 2, 1, 1, 1, ..., 1), (2, 0, 1, 1, 1, ..., 1), (2, 2, 1, 1, 1, ..., 1) green. Notice each green is adjacent to a red or black.

We will show that we can jump through 3-cube starting on one red and ending at the other red for $N \geq 2$. Proof will proceed by induction, with the base case $N = 2$ being pretty straighforward. For the inductive case, start on the red (0, 1, 1, 1, ..., 1). Now jump to the green (2, 0, 1, 1, 1, ..., 1). You are now on the N-1 dimensional 3-cube with coordinates (2, *, *, *, .., *), where * means that coordinate can be 0, 1, or 2. In this subcube, the greens play the same role as the reds, and the red plays the role of the center. Hence, by induction, we can now jump all the way through this subcube avoiding only the red, starting on a green and ending on a green. The green we end on has coordinates, (2, 2, 1, 1, 1, ..., 1).

We now jump to the subcube (1, *, *, *, ..., *). In particular, we jump from (2, 2, 1, 1, 1, ..., 1) to (1, 0, 1, 1, 1, ..., 1). By induction, we can now jump through this subcube and end on the green (1, 2, 1, 1, 1, ..., 1).

Finally, we jump to the subcube (0, *, *, *, ..., *). We go from (1, 2, 1, 1, 1, ..., 1) to the green (0, 0, 1, 1, 1, ..., 1). By induction we can eventually, end on green (0, 2, 1, 1, 1, ..., 1). We can then jump to the red (2, 1, 1, 1, ..., 1), which completes the path.

$\endgroup$
  • $\begingroup$ Your answer lacks a value for N. I'll assume you mean N = infinite, but it's not stated in the answer. $\endgroup$ – Tim Couwelier Apr 7 '15 at 16:04
  • 2
    $\begingroup$ Your base case doesn't work: you can tour the $3\times 3$ square, but your starting square and ending square cannot be $(0,1)$ and $(2,1)$. These two squares must differ by a knight's move. $\endgroup$ – Mike Earnest Apr 7 '15 at 16:05
  • $\begingroup$ @MikeEarnest: Good point ... looks like I rushed that case a bit and now the proof doesn't work! $\endgroup$ – Tyler Seacrest Apr 7 '15 at 16:46
  • $\begingroup$ @TimCouwelier: I say at the start of the second paragraph that the proof works for all $N \geq 2$. Except as Mike points out the proof doesn't work ... $\endgroup$ – Tyler Seacrest Apr 7 '15 at 16:47

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.