Rubik's Riddle: Newsletter Challenge (September 2018)

No...

There are some red herrings in this puzzle. The only important numbers are total possible configurations and number of configurations that require 10 or less moves to solve. A scrambled cube could have 43,252,003,274,489,856,000 possible configurations, of which only 251,285,929,522 are solvable in 10 moves or less. So the percentage that can be solved in 10 moves or less is 5.8 x 10^-7 percent (5.8 x 10^-9).

So the answer is no.

Oops, should have read more carefully:

Number of combinations 10 moves or less n1=251,85,929,522;

Number of combinations of completely random cube n2=43,252,003,274,489,856,000;

Probability of one solve being less than or equal to 10 moves: n1/n2

Probability of one solve being greater than 10 moves: 1 - n1/n2

Probability of t solves being greater than 10 moves: (1-n1/n2)^t

When (1-n1/n2)^t < .5, then the probability of having solved in less than 10 moves in t tries is > 0.5

Solving for t: t=log(.5)/log(1-n1/n2), t=119306339;

Total time =119306339 * 6 seconds = 22.684 years.

So, if the solver spent 8 hours a day, he could do it in about 68 years.

Perhaps I'm simply being dense. Please expand:

Probability of t solves being greater than 10 moves: (1-n1/n2)^t
When (1-n1/n2)^t < .5, then the probability of having solved in less than 10 moves in t tries is > 0.5

The probability that the number of moves required is greater to 10 is slightly less than 1. (1-n1/n2) = 0.99999999419019. The probability of solving twice (t=2) and both tries taking more than 10 moves would be that number squared, slightly less, but still close to 1. (1-n1/n2)² = .99999998838038.

After many years of twisting the cube (t=119306339 tries), the probability of never having solved in less than 10 moves would be

(1-n1/n2)^119306339 = 0.5

and the probability of having solved in less than 10 moves would be 1 - 0.5 = 0.5.

Got it!

After reading again the challenge (more carefully, as you advised), this explanation now makes complete sense.

Thank you for taking the time to compose this.

Your math is undeniably precise....but how much would you bet if the odds were 51% in your favor?

Agreed - I see that I simply restated your comment, so GA for ya..

251,285,929,522 configurations that require 10 or fewer turns to solve.
43,252,003,274,489,856,000 possible configurations.

251,285,929,522 / 43,252,003,274,489,856,000 < 0.5

The likelihood of anyone, in any amount of time, solving a randomly configured Rubik’s Cube in 10 moves or fewer is considerably less that 50%.

No, they couldn't devote their entire life to it because everyone needs eat, pee and sleep sometime.

Contrary to those before me, the answer is likely YES.

Obviously some will need convincing!

The first point is that in puzzle-land, the obvious is likely to be the wrong answer.

In this case the reported number of combinations is likely to be the something that misleads the unthinking and while this is not a mathematical answer it does turn out that the number of combinations is irrelevant.

To make the idea easy to visualise, consider some other sort of "cube" whose properties were that there are only 5 configuration types with 0 to 4 turn solutions, and that for each of these are (say) 1,4,8,16, and 1000 combinations or starting positions for each to the types respectively.

Would the answer for the above be "near 2" on the basis of configuration type and turns to solve or "near 4" on the basis of combinations or exact starting position ?

For our strange "cube" it would equally likely start at a type 0 through type 4 configuration with an average of 2 turns to complete over the long haul. and not be equally likely to start in each of the possible start positions or combinations possible

An early indication of the correct answer is that for the later to be the case, the resetter would have to mostly go to 4 turns before randomly selecting the final position. Whereas in reality he/she would normally equally go from 1 to 4 turns before selecting a final position.

The mathematical reason that the answer is not "near 4" is that the probability of being in any of the many start positions within in the type 4 group is very very small, and such that the total probability overall is still only 1/5 of all positions on a probability basis.

In practice, for the real cube, real life effects would also include that of not "neutrally" being reset for each new trial. This would come about because a human cube resetter would not invest the near 20 turns needed to get to the more remote combinations - and for that reason the practical answer would be likely less than 10 turns to solve in the long haul.

43,252,003,274,489,856,000 divided by 251,285,929,522

is about 172,122,614

So on average you'd need to solve that many combinations to get a "10 or less"

that's 17,212,261.4 minutes

I make that about 49 years at 16 hours a day: so I'd say the answer is yes.

Depends a bit on the exact definition of devotes their entire life to it.

I'm also assuming that "a perfect Rubik's cube solver" would actually solve a combination which could be solved in 10 moves, in 10 moves.

I'd say the odds that somebody could work 16 hrs a day, 7 days a week for 50 years, is greater than 100 Billion to one.....

That's working!

But what about playing?

If you don't have a cube, here is one to play with...

https://rubiks-cu.be/

Six seconds...that's slow!

This robot can solve a Rubik’s Cube in .38 seconds

https://techcrunch.com/2018/03/07/this-robot-can-solve-a-rubiks-cube-in-38-seconds/

Yess.
Dead easy.
Can be done in one...easily
Assuming your computer is already turned on or it would be three. The computer the software and the calc.
Cube solved.

Agree that the answer is "yes", but disagree with the number of combinations/permutations available.

Centre piece on every side is fixed WRT all others. Thus we only have 8 variable faces. If yellow and blue are opposite, then they will always be opposite, blue will never be on a face adjacent to yellow.

All 8 corner pieces have three fixed edges and thus are "dependant" Again, in the yellow/blue example, there will never be a corner with yellow and blue.

Or am I totally wrong??

I would add, in a truly random placement, would the cube always be solvable?

I would add, in a truly random placement, would the cube always be solvable?

Assuming you don't mess with the center pieces (like in #23) which would obviously invalidate it, the answer is still no.

You can't exchange a pair of edge pieces without also exchanging another pair somewhere else. You can't flip an edge piece without flipping another edge piece. And the rotation of corner pieces must add up to a whole number, so the possiblities are {+1/3, -1/3}, {+1/3, +1/3, +1/3}, {-1/3, -1/3, -1/3}, etc.

The bottom line is that there are 2x2x3 or 12 different cube arrangements, and you can't get from one to another. If you took a scrambled cube apart, exchanged two edge pieces, flipped an edge piece, or rotated a corner piece in either direction, and reassembled it, you would not be able to solve it. There are 12 different possiblities, only one of which can be solved. (See #21)

The math calculating the number of permutations does not consider the immovable center pieces. So rotating the cube as a whole does not count. Also, rotating the center face pieces is not included, although there are special "picture cubes" which would have more combination.

N=8! x 3⁷ x (12!/2) x 2¹¹.

There are 8! ways to arrange the 8 corner pieces. There are 3 ways to arrange each corner, but when 7 corners are oriented, the eighth is determined (3⁷). There are 12! ways to arrange the 12 edge pieces, but only half of these are reachable (parity). (12!/2) Finally, 11 of the 12 edge pieces can be flipped (2¹¹). The position of the 12th edge piece is determined by the other 11 (parity again).

"Mathematics

Permutations

The current colour scheme of a Rubik's Cube

The original (3×3×3) Rubik's Cube has eight corners and twelve edges. There are 8!(40,320) ways to arrange the corner cubes. Each corner has three possible orientations, although only seven (of eight) can be oriented independently; the orientation of the eighth (final) corner depends on the preceding seven, giving 3⁷(2,187) possibilities. There are 12!/2 (239,500,800) ways to arrange the edges, restricted from 12! because edges must be in an even permutation exactly when the corners are. (When arrangements of centres are also permitted, as described below, the rule is that the combined arrangement of corners, edges, and centres must be an even permutation.) Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones, giving 2¹¹ (2,048) possibilities.^[46]

{\displaystyle {8!\times 3^{7}\times (12!/2)\times 2^{11}}=43,252,003,274,489,856,000}

which is approximately 43 quintillion.^[47]

The puzzle was originally advertised as having "over 3,000,000,000 (three billion) combinations but only one solution".^[48] To put this into perspective, if one had as many standard sized Rubik's Cubes as there are permutations, one could cover the Earth's surface 275 times."

https://en.wikipedia.org/wiki/Rubik%27s_Cube

All centers blue? This can be solved, but only by unsticking and moving the colored plastics.

Try that in 6 seconds....

That colour rendition is totally unsolvable

If you took the cube apart and arranged the central 3D cross in a fixed position, putting the pieces back at random, then:

the first corner could be 1 of 8 the second 1 of 7. etc. ....: 8!

but each corner can be in any of 3 orientations.............: 3^8

the first edge could be 1 of 12 etc. ...............................: 12!

but each edge can be in 2 orientations.........................: 2^12

Multiply those 4 numbers together to get the total number of possible configurations (after dismantling).

But some of those combinations are not possible under normal manipulation:

If seven of the corners are correctly oriented then the eighth is always correct so divide by three.

You never end up with two edge pieces swapped (position wise), so divide by 2.

And you never end up with just one edge piece flipped (it's always two), so divide by 2 again.

See now that makes sense....So while it might be possible, it is not, in reality, likely...

If you take it apart and put it together randomly, you have one chance in twelve of getting a solvable cube...

They used symmetries just like you mentioned to get to that number of permutations. So in other words, I think the thing you are mentioning is already in the numbers.

Yes, but there is an obvious rounding error if the number ends in "000" rather than 064 0r some other number.

I suppose that I have a 1 in 1000 chance of being incorrect in that.

No, the number is exact:

Just do the arithmetic: 8! has lots of 2s and one 5; 12! has lots of 2s one 5 and one 10.

Those three tens ensure that the number ends in 000.

Thanks for the clarification.

Trick question.

The perfect solver would look at the cube and either say he/she could do it in 10 and take an average six seconds to do it, or would say "no, go away". Either way, it wouldn't take the rest of the solvers life. The key is whether the solver would recognize a 10 move solveable cube when he/she sees it.

The key is whether the solver would recognize a 10 move solveable cube when he/she sees it.

I have an algorithm that is 99.999999419019 % accurate, "just say no".

That's actually a good question. Since there are 251 billion combinations for cubes that can be solved in 10 moves or less, I would say that it wouldn't be likely that anyone could recognize all of them, but there are some that are simple enough to solve by inspection.

The puzzle specified a perfect cube solver, whom I assume could solve any cube with the same number of turns that scrambled it. If the cube could be solved just by inspection, a real cube solver could do this, but I believe that if he couldn't solve by inspection, he would probably need more moves to solve it than were used to scramble it.

Answer is posted.