1x1xN math/probability question with bonus problems

[JBCM627]

So for some reason, I just can't seem to wrap my head around the following problem, after like hours of number pushing... and I really don't think it should be *that* difficult. Hopefully this description is clear enough...

The long story:
While trying to clean up an MxNxL scrambler I recently made (http://www.thewonderidiot.net/timer/scramble.html), I decided to try and optimize 1x1xN scrambling, as it seems fairly simple to do. No, the cleaner version isn't up yet, and I'm working on images too... anyway, instead of generating a random position then solving that, I wanted to try and generate random moves on the cube as it would use the generator function I had already written. There are of course some simple and obvious ways to do this, one of which I will probably end up implementing... but the first thing I tried to do was the aforementioned: use the main generator (big while loop) function to generate the scramble. This means that I tried to generate a scramble with a random length, as the generator will only generate actual moves (no 0 turns). The scramble length would obviously have to be biased, as for example a 1x1x2 would have 4 states, 3 of which require a move. So the length would be 1, 3/4 of the time, and 0 1/4 of the time. Which leads me to...

Cutting to the chase:
For a 1x1xN cube, what is the probability that m moves will be required to solve a random cube? (worth 10 points)


*Also, a bonus problem for any puzzle builders out there, should the cubes always be forced to retain their shape, or is it possible to have some wierd (fully functional, like super functional) cube that deforms into a non-rectangular-prism shape? As in, what options should be present to restrict moves? (worth 1 point)

*Super bonus: extend the formula to an MxNx1, NxNx1, NxNxN, or other higher dimensional cube/puzzle, or prove the impossibility to generalize to this. (This could eliminate need to generate 'random positions' on cubes... but I have the suspicion that due to the fact that there is more than one way to generate some positions with the same ammount of moves, this may imply the impossibility of extending the formula, or at the very least invalidate the way I would use it to generate scrambles. This could also be used to find longest scramble length for any cube, which as well makes me think it may not be possible.) (worth 1 point)

 

[cmhardw]

Cutting to the chase:
For a 1x1xN cube, what is the probability that m moves will be required to solve a random cube? (worth 10 points)

Let one of the end pieces of the 1x1xN puzzle (the ones with 5 stickers) be fixed in space to define orientation. This piece is not allowed to turn. Given this setup, the probability that m moves are required to solve the puzzle correctly, with respect to the one piece fixed in space, is:

P = C(n-1,m)*3^m/4^(n-1)

Where C(n,k)=n!/[k!*(n-k)!]

1) This is true for m <= n-1
2) If m > n-1 the probability is 0

I'd be interested to look at this if block turns are allowed too (basically, like saying that you can turn that one fixed piece).

--edit--
For a 1x1xN puzzle the minimum number of pieces that are all lined up the same way, and can be considered solved, is 1 + floor[(n-1)/4]

So let O(n) = 1 + floor[(n-1)/4]

Now, the probability that m moves are required to solve the puzzle if you define any O(n) number of pieces that are aligned the same way to be fixed in space is:

P = C(n-O(n),m)*3^m/4^(n-O(n))

or expanded that comes out to:

P = C(n-1-floor[(n-1)/4],m)*3^m/4^[n-1-floor((n-1)/4)]

1) The above is the probability if m <= n-O(n)
2) For m > n-O(n) the probability is 0

final answer ;-) (this does not allow block turns though, that part I am interested to look at, but not tonight).
--edit--


--edit #2--
Actually, the above can't be the correct formula, because it doesn't correctly count the number of ways on a 1x1x4 cube that you must do 3 turns. My formula gives 27/64 for n=4 and m=3, but it should be 3/32 if you just do a direct count. My formula counts the number of ways that, if you rotate the puzzle such that at least 1 + floor[(n-1)/4] pieces are "solved", that m of the remaining ones are misaligned from the solved ones. For cases when m is close to n-[1 + floor[(n-1)/4]] though this counts as possible that all the mis-aligned ones are rotated the same direction, which isn't useful for our purposes because we would not see that as m turns needing to be done to be solved but (n-m) turns needing to be done.

Wow, now I'm really interested in this problem. Too tired to think about it right now, but I'll mull over it some more tomorrow.
--edit #2--

Chris

 

[JBCM627]

awesome, thanks a lot chris, works perfectly (well, at least for the smaller N cases that I tested and verified by hand ). (10 pts)

I think I sort of understand the first part of this... correct me if I'm wrong,

let b = # breaks on N axis (N-1)
probability of choosing a break to misalign = C(b, m)
probability of doing a non-0 move = 3^m

but I'm not too sure where the 1/4^(b), nor the b-floor(b/4) come in. could you explain further? Thanks!

Also, scrambling with the block turns I have more or less been ignoring, as that is just equivalent to turning all the layers above the fixed block... as in just a move + a cube rotation. The scrambler I made is interesting in this way, in that for example on a 4x4x4 it will never generate a Dw move, as this is just an Uw + [U']. See comments the src code (at the top) of the scrambler above for more details if you are interested

Edit: Uploaded updated scrambler per changes. Also, note about potential bias in WCA scrambler, see: WCA Forum. Opinions?

 

[JBCM627]

Oh, duh... *1/4^(b) possible moves

Still not seeing the b-floor[b/4], though...

 

[cmhardw]

Oh, duh... *1/4^(b) possible moves

Still not seeing the b-floor[b/4], though...

Test it out, for any scrambled 1x1xN you will always have at least 1 + floor[(n-1)/4] pieces in the same orientation.

If n=5 or a 1x1x5 you will always have at least 1 + floor[(5-1)/4] = 1 + floor(1) = 2 pieces in the same orientation.

If n=50 then you will always have at least 1 + floor[(50-1)/4] = 1 + floor(12.25) = 1 + 12 = 13 pieces in the same orientation.

I'm getting closer to what I believe is the correct formula, but I'm way too tired right now and it's late. Will look at it tomorrow.

Chris

 

[JBCM627]

--edit #2--
Actually, the above can't be the correct formula, because it doesn't correctly count the number of ways on a 1x1x4 cube that you must do 3 turns. My formula gives 27/64 for n=4 and m=3, but it should be 3/32 if you just do a direct count. My formula counts the number of ways that, if you rotate the puzzle such that at least 1 + floor[(n-1)/4] pieces are "solved", that m of the remaining ones are misaligned from the solved ones. For cases when m is close to n-[1 + floor[(n-1)/4]] though this counts as possible that all the mis-aligned ones are rotated the same direction, which isn't useful for our purposes because we would not see that as m turns needing to be done to be solved but (n-m) turns needing to be done.

Wow, now I'm really interested in this problem. Too tired to think about it right now, but I'll mull over it some more tomorrow.
--edit #2--

Chris

Edit: Hmm, that sort of makes sense, but not entirely: for a 1x1xN, why wouldnt it just have 4^(N-1) possible states, or 4 possible misalignments for each break? Why 4^[N-1-floor((n-1)/4)]?

I think it is correct for a 1x1x4 (I got out a 4x4x4 to count these), which has:
1 state with 0 layers turned
9 states with 1 layer turned
27 states with 2 layers turned
27 states with 3 layers turned
= 64 possible states, and so 27/64 for n=4, m=3;
and by turned, I mean misaligned to produce a previously unaccounted for state.

I also updated the online scrambler to alert you of the probabilities to make it a bit easier to test forumlae; save it as html and edit the formulas on lines 235 and 236:

turns[i] = choose(n-Math.floor(n/4), i)*Math.pow(3,i)/Math.pow(4,n-Math.floor(n/4));
alert("probability of " + i + " turns: " + choose(n-Math.floor(n/4), i)*Math.pow(3,i) + "/" + Math.pow(4,n-Math.floor(n/4)));

where i is m, # of moves
and n is N-1, or b, or the number of breaks
and turns is storing the number of moves for a specific i.

Just type in any 1x1xN cube and it should come up with the alerts (and a scramble) when you generate a scramble.

 

[JBCM627]

Does anyone reading this want to help with generating images for the NxMxL scrambler? I have version up that doesn't remotely work but the idea should:http://www.thewonderidiot.net/timer/scramble2.html