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
>
>