3
$\begingroup$

One of Martin Gardner's "Mathematical Games" columns (Scientific American June 1981, pp24–29; reprinted in The Last Recreations (1997), pp274–283, and The Colossal Book of Mathematics (2001) pp203–211) describes the following problem due to Scott Kim:

First we must define a snake. It is a single connected chain of identical unit cubes joined at their faces in such a way that each cube (except for a cube at the end of a chain) is attached face to face to exactly two other cubes. The snake may twist in any possible direction, provided no internal cube abuts the face of any cube other than its two immediate neighbors. The snake may, however, twist so that any number of its cubes touch along edges or at corners. A polycube snake may [...] have just one end and be infinite in length, or it may be infinite and endless in both directions.

We now ask a deceptively simple question. What is the smallest number of snakes needed to fill all space? We can put it another way: Imagine space to be completely packed with an infinite number of unit cubes. What is the smallest number of snakes into which it can be dissected by cutting along the planes that define the cubes?

[...] Kim has found a way of twisting four infinitely long one-ended snakes into a structure of interlocked helical shapes that fill all space. The method is too complicated to explain in a limited space; you will have to take my word that it can be done. [...] Kim has conjectured that in a space of $n$ dimensions the minimum number of snakes that completely fill it is $2(n-1)$, but the guess is still a shaky one.

In the reprints (I can't find this ever printed in the Scientific American back issues, but maybe I missed it), Gardner adds:

Dr. Koh Chor Jin, a physicist at the National University of Singapore, sent a clever proof that given a finite volume of space it is possible to cover it with two of Kim's cube-connected snakes. However, as Kim pointed out, Jin's construction does not approach all of space as a limit [...]

So my question for StackExchange is: What was Scott Kim's (or, what is a) four-snake space-filling construction? And what was Koh Chor-Jin's (or, what is a) way to cover any finite volume with two snakes?

This guy is also looking for information on the problem.

Footnote: At first I wondered if $2(n-1)$ was a typo for $2^{n-1}$, since obviously it takes one snake (not zero snakes) to fill 1-space. But it's consistently typeset as $2(n-1)$ in all three primary sources, so I think the "for $n\ge 2$" is implied.

$\endgroup$
2
  • 1
    $\begingroup$ I think I see how to cover any finite volume with one black snake and one white snake, by extruding a sufficiently wide 2D checkerboard straight across it and then joining up pairs of black ends and pairs of white ends until we're left with two finite snakes. I don't see a "proof" exactly, but it doesn't seem that there would be any difficulty. And indeed the technique fails to work for infinite volumes. $\endgroup$
    – Quuxplusone
    Commented Nov 15, 2022 at 17:58
  • $\begingroup$ Thanks to Scott Kim for writing up his solution and posting it here. Thanks also to @Display name for posting a link to the March 2023 video where Scott explains his solution! For posterity, here it is: youtu.be/-I_1WVkyfVQ?t=4198 $\endgroup$
    – Quuxplusone
    Commented May 7, 2023 at 19:01

2 Answers 2

Reset to default
1
$\begingroup$

here's a video of Kim showing his solution, enjoy. https://youtu.be/-I_1WVkyfVQ?t=4198

$\endgroup$
3
  • 1
    $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Commented May 7, 2023 at 13:24
  • 2
    $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$
    – HeroZhang001
    Commented May 7, 2023 at 13:27
  • $\begingroup$ Hi, and thanks — I had missed that particular G4G meetup! I asked Scott at one of the previous meetups, and he actually came here and posted his own answer to the question, which was also deleted (as yours soon will be) by overzealous mods. So I got his diagram already. I keep meaning to blog it in a form that could be cross-posted over here and maybe survive the mods, but I keep being busy with other things... $\endgroup$
    – Quuxplusone
    Commented May 7, 2023 at 18:58
0
$\begingroup$

I've finally gotten around to copying Scott Kim's answer onto my own blog. So here, for SO's benefit, is the same thing four ways:

Shown here is a space-filling solution with 4 snakes.

The red and yellow snakes spiral around each other to form a 2x2x3 solid (one cube higher than wide), ending at the two top squares marked with black dots.

Then the green and blue snakes coil around each other to build a shell enclosing the red and yellow snakes, starting in the middle of the bottom, spiraling out, climbing up the walls, spiraling in, and stopping one cube short of closing the shell.

The process then repeats. First, the ends of the red and yellow snakes poke up through the holes in the blue-green shell (see cubes marked with white dots) and spiral down to form a shell with two holes at the bottom for the green and blue snakes to escape.

Then the blue and green snakes poke up through the holes and spiral down to form a shell with no holes at the top, but two holes at the bottom. The process continues, building red-yellow and blue-green shells, alternately up and down.

What’s remarkable is that the diagonal of kinks that run down the shell always end at the right place to neatly finish the structure with no mess.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .