# Message #1809

From: Roice Nelson <roice3@gmail.com>

Subject: Re: [MC4D] Re: God’s Number for n^3 cubes.

Date: Thu, 30 Jun 2011 23:52:58 -0500

Small typo correction in the second to last bullet about parallelizing… I

meant to write *O(3^n)* pieces will move during a twist. I seem to have

trouble with accidentally reversing this notation some times :S

Roice

On Thu, Jun 30, 2011 at 10:16 PM, Roice Nelson <roice3@gmail.com> wrote:

> I’ve seen the origami documentary Melinda mentions, and really enjoyed it.

> Definitely recommended for members of this group. I also hadn’t known Erik

> Demaine was interested in twisty puzzles till I saw this paper yesterday. I

> got to see him give a talk at the Gathering For Gardner last year, on

> origami derived fonts. There was a Rubik block at that conference, and

> about 6 of us presented (mine was an intro to MagicTile and the Klein

> Quartic hyperbolic puzzle). I’d like to think that block of talks helped

> stoke interest towards a paper like this, though I’m sure it’s just the

> dominating gravitational pull of Rubik’s Cube - it is bound to suck

> in anyone who dares wander too close :)

>

> After reading the paper intro and a few of the sections while thinking

> about the 3^n, it feels like the latter would be a more difficult problem.

> It does seems quite possible that the order of God’s Number for the 3^n

> will grow exponentially rather than polynomially. Some simple observations

> I could make were the following (no accuracy guarantees!):

>

> - The number of pieces (cubies) to solve will be of order O(3^n). When

> limiting to 3-per-side, we won’t get any dimensional reduction like they did

> (where number of cubies they had to solve ended up being proportional to

> area rather than volume). The number of cubies to solve will effectively be

> all of them.

> - Related to the above, 1C pieces are solved already (2n of these), but

> they become negligible. O(3^n-2n) = O(3^n)

> - I think no particular cubie type will dominate the calculations,

> though cubie types with smaller numbers of colors become less important with

> larger n. For example, see these google charts made for counts for a

> 3^10<http://chart.apis.google.com/chart?chxr=0,0,10%7C1%2C0%2C15360%26chxs%3D0%2C676767%2C11.5%2C0%2Clt%2C676767%26chxt%3Dx%2Cy%26chs%3D660x330%26cht%3Dlxy%26chco%3D3072F3%26chds%3D0%2C10%2C0%2C15360%26chd%3Dt:0,1,2,3,4,5,6,7,8,9,10%7C1,20,180,960,3360,8064,13440,15360,11520,5120,1024&chdlp=b&chls=2,4,1&chma=5,5,5,25&chtt=Number+of+cubies+vs.+cubie+type+in+3%5E10>and counts

> for a 3^20<http://chart.apis.google.com/chart?chxr=0,0,20%7C1%2C0%2C635043840%26chxs%3D0%2C676767%2C11.5%2C0%2Clt%2C676767%26chxt%3Dx%2Cy%26chs%3D660x330%26cht%3Dlxy%26chco%3D3072F3%26chds%3D0%2C20%2C0%2C635043840%26chd%3Dt:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20%7C1,40,760,9120,77520,496128,2480640,9922560,32248320,85995520,189190144,343982080,515973120,635043840,635043840,508035072,317521920,149422080,49807360,10485760,1048576&chdlp=b&chls=2,4,1&chma=5,5,5,25&chtt=Number+of+cubies+vs.+cubie+type+in+3%5E20>

> .

> - Unlike in the n^3, the growing number of higher-C piece types in the

> 3^n take longer and longer to solve, so it won’t be accurate to say each

> could be solved in constant time, as was true in the paper. 2^C has been a

> good "folk algorithm length" for how long it takes me to solve a piece with

> C colors. I don’t know how to combine piece type counts with

> length-to-solve estimates into the a very rough big O estimate for God’s

> Number, but that feels like a first step. It seems complicated since many

> individual piece type counts get involved.

> - In the paper, they are able to divide out a factor by showing

> parallelization is possible on the O(n) pieces that move during a twist of

> an n^3. On the 3^n, a full third of the puzzle moves during a twist, so

> O(n^3), and this is a much more significant number to have the opportunity

> to try to parallelize. But I have no clue how to estimate how much

> parallelization might be possible. Even if one found some desirable

> tactics, finding an optimal parallelization and showing it so seems much

> more daunting.

> - I wonder if some of the previous Goldilocks discussion might find

> some applicability to the 3^n problem.

>

> Cheers,

> Roice

>

>

> On Wed, Jun 29, 2011 at 11:39 PM, schuma <mananself@gmail.com> wrote:

>

>> Very interesting.

>>

>> I’m actually more interested in the asymptotics of the god’s number for

>> 3^n, instead of n^3. Maybe 2^n is easier because it only contains nC pieces.

>> I thought about this question before but never took it seriously. Actually

>> every information theorist would consider the asymptotics as the dimension

>> goes to infinity because that’s what happens in information theory.

>>

>> In this type of results, the lower bound (converse) is typically more

>> tricky to find. But this paper shows that for n^3 it can be found by a

>> rather simple counting argument. This is an encouraging message. Maybe the

>> asymptotics of 3^n can also be established by a counting argument.

>>

>> I’ve heard of Erik Demaine before because of his entertaining research

>> about origami. But I never knew he was interested in twisty puzzles.

>>

>> Nan

>

>