20
$\begingroup$

I have the following toy, perhaps some of you have seen it before.

The toy

It consists of a bunch of cubes with an elastic string in the middle. You can bend it into different shapes like this:

One shape

Or this:

Another shape

Or even this:

Final shape

Here is the product page for it on Amazon if you want more of a description.

From one block to the next, you can orient the next either on the top, or on one of the four sides. With this, I think you have no more than $5^{11}$ possible choices you can make while playing with it. But some of these will give the same shape up to translation and rotation. There's also the problem of cubes colliding, excluding some choices.

For instance, in the very first picture, there is only one way to make that shape. In the second, I think there are about 8. For instance, you can "rotate" the loop by placing the start and end points at a different place. In the third, I think there is an argument that there are no other ways to make that shape, since you don't have four subunits forming a square.

All this is to ask, how many different shapes can I make with this toy? If I have a toy with $n$ subunits instead, what is the answer then?

[If this question is related to any serious areas of math or well known problems, let me know! I suspect there might be some connection with protein folding, but I know nothing about such things. Or perhaps there is some algebraic way to think about this, where my question translates into counting the number of orbits under some group action.]

$\endgroup$
6
  • $\begingroup$ I'm pretty sure that something similar to (if not) Burnside's Lemma will be of some application here! seems very much like the kind of problem that group theory excels at dealing with (although in hindsight I'm not sure if a group that describes the symmetries of this shape would be that trivial...) $\endgroup$ – Tim Aug 1 '13 at 22:03
  • $\begingroup$ If you "close the loop" as in the second picture, and restrict yourself to those sorts of shapes, perhaps it would be easier to find some sort of group action. $\endgroup$ – abnry Aug 1 '13 at 22:07
  • $\begingroup$ I'm interested in any simplified versions of the question as well. For instance, what if we require the toy to be only in the plane? $\endgroup$ – abnry Aug 1 '13 at 22:45
  • 1
    $\begingroup$ Take a look at this page for polyominoes for a simplified discussion. I expect your number to be very large $\endgroup$ – cactus314 Aug 1 '13 at 23:07
  • 1
    $\begingroup$ It might be interesting to see what upper bounds can be discovered for this, as I imagine it would be hard to come up with the actual number. I spent a pleasant afternoon once discussing a similar problem: how may shapes could one have in a game of n-tris, a generalization of tetris where the shapes were all comprised of n connected squares with no holes. $\endgroup$ – Codie CodeMonkey Aug 1 '13 at 23:35
14
$\begingroup$

I believe these are Self-Avoiding walks. These related to Sloane sequence A001411:

1, 4, 12, 36, 100, 284, 780, 2172, 5916,...


(from MathWorld - A Wolfram Web Resource: wolfram.com)

The self-avoiding walks on a cubic lattice, A001412

1, 6, 30, 150, 726, 3534, 16926, 81390,...

Sloane's Encyclopedia of Integer Sequences offers 317 number patterns related to self-avoiding walks.

Self-avoiding walks are related to computational chemistry and statistical mechanics.

Such problem are related to the work of 2010 Fields Medalist Stanislav Smirnov who showed the number of such paths on the hexagonal lattice grow was $(\sqrt{2 + \sqrt{2}})^n$

$\endgroup$
4
  • 3
    $\begingroup$ This is correct if (all the colors are unique and) colors are considered to distinguish configurations, but otherwise multiple different self-avoiding walks can lead to the same shape - the two four-unit walks that are at the end of your penultimate line and third in your last line (the 'hump' and the 'curl') give the same shape (basically, the P pentomino). Your enumeration also has two rotationally-identical shapes (#s 4 and 6 on the penultimate line), so I think there may be one 4-unit walk you're missing... $\endgroup$ – Steven Stadnicki Aug 2 '13 at 0:06
  • $\begingroup$ #4 on the penultimate is also the same as #3 on the last. Whenever you have a bend I think you will have this sort of situation of repeated shapes. $\endgroup$ – abnry Aug 2 '13 at 2:31
  • $\begingroup$ @Glorfindel I don't know much about licensing/copyright as to whether including Mathworld's image like this under the license of a stackexchange post is okay, but assuming it is, you should probably give a more detailed citation as requested at mathworld.wolfram.com/about/faq.html#copyright $\endgroup$ – Mark S. Mar 11 '19 at 9:53
  • 1
    $\begingroup$ @MarkS. good question. I think it qualifies as Fair Use, and it's better than the original which didn't include any attribution at all. I might modify the script to produce a more elaborate citation. $\endgroup$ – Glorfindel Mar 11 '19 at 10:01

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.