Bounds on Rubik’s Cube and Mirror Cube Configurations Grace Hsu, Sissi Liu Science One Program The University of British Columbia Vancouver, Canada 30 June 2012 Abstract Given a 3×3×3 mirror cube, we find the number of valid and distinct projections up to and including three 90 ◦ turns. Next, we calculate the number of valid permutations of the traditional 3 × 3 × 3 Rubik’s cube such that it has at least one, two, three, four, five or six faces with the same colour. We then return to the mirror cube and find improved upper bounds for the number of distinct projections. 1 Introduction A mirror cube is a 3 × 3 × 3 twisty puzzle with a skewed pivot mechanism, which translates into skewed centres and the distinct dimensions of all its pieces (Fig. 1a), unlike the uniform cubes of the traditional Rubik’s puzzle. We use the more general term “pieces,” as opposed to the conventional term “cubies,” since the mirror cube’s pieces do not have a cubic shape (Fig. 1b). Because of the pieces’ different dimensions, when the puzzle is turned, the mirror cube’s shape changes and so shape, instead of colour, is used to return to the mirror cube’s solved state. The solved state of a Rubik’s cube is when each and every face is uniformly one colour, whereas that of the mirror cube is when the puzzle’s overall shape is cubic (Fig. 1a). Both the Rubik’s cube and mirror cube are composed of a core pivot mechanism on to which the six static centres and twenty movable pieces are attached. Twelve of these pieces have two faces, which we call edges, and eight have three faces, which we call corners. A piece’s position describes the space it occupies on the cube. Clearly, as none of the corner pieces share any sides with the centre piece, a corner piece cannot occupy an edge position and neither can an edge piece occupy a corner position. A piece’s orientation describes how it is twisted or flipped at its position. We label the edges E1 to E12 and the corners C1 to C8 for both puzzles as seen in Figure 1a. Comparing Tables 1 and 2 proves that the different colours each piece carries are what make the Rubik’s cube’s pieces distinct, whereas it is the pieces’ different dimensions that make the mirror cube pieces distinct. Thus, the mirror cube is analogous to the Rubik’s cube as each and every corner and edge has one specific 1 Figure 1: a, labelled mirror cube in its solved state; the Rubik’s cube is labelled the same way. Notice that all the edges but none of the corners share exactly one dimension with the square centres (1.8 cm). b, a corner piece on the left and edge piece on the right. c, the mirror cube’s established front face. position and orientation in the puzzle’s solved state. We use the general term “cube” to refer to both the Rubik’s and mirror cube. Edge piece colours E1 blue, yellow E2 blue, orange E3 blue, red E4 blue, white E5 orange, yellow E6 red, yellow E7 orange, white E8 red, white E9 green, yellow E10 green, red E11 green, orange E12 green, white Corner piece colours C1 blue, yellow, orange C2 blue, yellow, red C3 blue, white, orange C4 blue, white, red C5 green, yellow, red C6 green, yellow, orange C7 green, white, red C8 green, white, orange Table 1: Description of Rubik’s cube pieces in terms of their colours. Notice that each piece is distinct due to different colour combinations. The cube has six faces that can be turned independently. Once a front face (F), facing the puzzle-holder, has been established, we can label the remaining faces: back (B), left (L), right (R), up (U) and down (D) (Fig. 2). Each of these six faces may only perform discrete 90 ◦ turns in either the clockwise (cw) or counterclockwise (ccw) direction. Now that we have labelled the mirror cube, we define a projection as the overall shape of the mirror cube as seen from the perspective where we are facing the front face (Fig. 2). In other words, if we shine a light perpendicular to the F, the shadow produced on the wall would be a projection. Distinct projections can be thought of 2 Edge piece dimensions (cm) E1 1.8 × 1.2 × 0.8 E2 1.8 × 1.6 × 0.8 E3 1.8 × 2.0 × 0.8 E4 1.8 × 2.4 × 0.8 E5 1.8 × 1.6 × 1.2 E6 1.8 × 2.0 × 1.2 E7 1.8 × 1.6 × 2.4 E8 1.8 × 2.0 × 2.4 E9 1.8 × 1.2 × 2.8 E10 1.8 × 1.6 × 2.8 E11 1.8 × 2.0 × 2.8 E12 1.8 × 2.4 × 2.8 Corner piece dimensions (cm) C1 1.6 × 1.2 × 0.8 C2 2.0 × 1.2 × 0.8 C3 1.6 × 2.4 × 0.8 C4 2.0 × 2.4 × 0.8 C5 2.0 × 1.2 × 2.8 C6 1.6 × 1.2 × 2.8 C7 2.0 × 2.4 × 2.8 C8 1.6 × 2.4 × 2.8 Table 2: Dimensions of mirror cube pieces. Notice that every piece is distinct due to different dimensions. Figure 2: a, projection of the mirror cube in its solved state. Notice that all dimensions parallel to the red line do not affect the projection made. b and c, examples of different permutations that yield the same projection as in 2a. as different “shadows on a wall.” Notice that pieces’ dimensions that are orthogonal to the front face, and thus the shadow on the wall, do not affect or contribute to the projection (Fig. 2a). There are multiple permutations that produce the same projection as seen after comparing Figures 2a, 2b and 2c. A projection is valid if and only if it can be attained through some combination of allowed face turns starting from the solved state. The total number of permutations a cube has is the total number of different ways all the pieces can be positioned and oriented. A permutation describes both the pieces’ position and orientation. Permutations are valid if and only if the permutation can be attained through some combination of allowed face turns. Whereas an invalid permutation means that the only way to return to the solved state is by physically ripping pieces off the puzzle. The parity of a permutation is either even or odd. The permutations of the Rubik’s 3 cube, and thus the mirror cube, can be expressed as a group. A theorem of group theory found in [1] (Theorem 5.4) states that any permutation can be expressed as a product of 2-cycles. That is, any permutation can be achieved by some combination of 2-cycles, which can be thought of as swapping the positions of two edges or two corners. If an odd number of 2-cycles are required, then the permutation has odd parity, and if an even number of 2-cycles are required, then the permutation has even parity. For any permutation, the cube’s corners have odd or even parity depending on the number of swaps taken to reach the permutation from the solved state. For example, if we swap one corner for any other corner, one swap has been performed, and thus this is an odd permutation of the puzzle’s corners. An odd permutation of the corners means that it has odd parity. A similar definition applies for the edges. We now have the vocabulary to outline the conditions for valid permutations. 1.1 Conditions for validity A permutation is valid if and only if all of the following conditions, compiled from The Fundamental Theorems of Cubology in [3], are satisfied. 1. The edges and corners have the same parity. 2. There are an equal number of counterclockwise twists and clockwise twists of the corners. 3. There are an even number of edge flips. 1.2 The size of the cube group There are twelve edge positions corresponding to the twelve edge pieces, and eight corner positions that correspond to the the eight corner pieces. Basic combinatorics yields the number of ways to position the edge and corner pieces as 12! and 8! respectively. Each edge can be oriented two different ways, whereas each corner can be oriented in three different ways, therefore there are 212 ways to orient all twelve edges and 38 ways to orient all eight edges. We multiply these four terms to attain the total number of valid and invalid permutations of a Rubik’s cube, named G: 12! × 212 G= × ways to position and orient the edges 20 8! × 38 (1) ways to position and orient the corners = 5.1902403929... × 10 (2) 20 ≈ 5.19 × 10 . (3) To attain the number of valid permutations, we must satisfy the conditions for validity. Firstly, Theorem 5.7 in [1] states that there are as many even permutations as odd permutations. As the edges and corners must have the same parity, then half of total permutations are valid. Essentially, the pieces only have valid positions for half of the permutations. We must also divide the total permutations by three as only 31 of the possible combinations of corner twists satisfy the second condition. Similarly, we must divide the total permutations by two again as only 12 of the possible combinations of edge flips satisfy the third condition. We refer the reader to the formal proof provided by 4 [3], though with Table 3 we can easily see why we must divide by two and three to be left with valid orientations. Edge 1 not flipped not flipped flipped flipped Edge 2 not flipped flipped not flipped flipped Orientation valid invalid invalid valid Corner 1 Corner 2 not twisted not twisted not twisted twisted cw not twisted twisted ccw twisted cw not twisted twisted cw twisted cw twisted cw twisted ccw twisted ccw not twisted twisted ccw twisted cw twisted ccw twisted ccw Orientation valid invalid invalid invalid invalid valid invalid valid invalid Table 3: We consider any two edges and any two corners and all the possible combinations of orientations. We determine the fraction of valid of the combinations by applying the second condition for validity. With these consequences due to the conditions of validity in mind, the number of valid permutations, named Gv is, Gv = G = 2×2×3 12!8! 2 × number of valid positions 19 212 × 38 2×3 (4) number of valid orientations = 4.3252003274... × 10 19 ≈ 4.325 × 10 . 1.3 (5) (6) Preliminary upper bounds on the mirror cube We have shown how the Rubik’s cube and mirror cube are analogous, so the total number of valid and invalid permutations of a Rubik’s cube is equal to the total number of valid and invalid permutations of a mirror cube. Let P be the number of valid and invalid distinct projections and Pv be the number of valid distinct projections. We showed that multiple permutations can produce the same projection. Thus we have upper bounds for mirror cube projections such that, P < G ≈ 5.19 × 1020 , (7) Pv < Gv ≈ 4.325 × 1019 . (8) and 2 A lower bound on the mirror cube Following the preliminary upper bound on Pv , we find a lower bound on the the number of valid and distinct projections by finding the exact number of valid and distinct 5 projections created by up to and including three 90 ◦ turns. We define “one turn” as turning a face 90 ◦ either clockwise or counterclockwise (Fig. 3). As we calculate the projections turn by turn starting from the solved state, we can be sure that they are valid. Let the number of valid and distinct projections that can only be produced by exactly n turns be Dtn , where n = 0, 1, 2, 3, .... We define the three sets of parallel faces, up and down, right and left, and front and back as face sets UD, RL and FB. Faces in different sets are said to be non-parallel to one another. Figure 3: The three non-parallel face sets with arrows indicating the direction of a clockwise turn. a, the RL face set. b, the UD face set. c the FB face set,. Initially we check that every projection is distinct for 0 turns and 1 turn, from which we begin to recognize the face sets’ patterns of behaviour and split into cases accordingly. For 2 turns and 3 turns, we combine visual measurements of the projections’ dimensions with the previously developed knowledge of behaviour to determine whether projections are distinct. 0 turns. Obviously if we do not turn any faces, Dt0 = 1. (9) 1 turn. We attain Dt1 by manual counting. Each face can be turned clockwise (cw) or counterclockwise (ccw), and both turns produce a distinct projection. However, because we establish a front face and how we define a projection, turning F clockwise is the same as turning B counterclockwise (Fig. 4). Thus, Dt1 = 6×2 2 distinct projections per face − 2 = 10. (10) F and B produce identical projections 2 turns. We break the problem down into two cases. Case 1. The two turns are parallel to one another. We have two situations to consider: turning the same face twice, or turning both faces in a set once each. 6 Figure 4: a, projection made by turning F cw. b and c, clearly, turning F and B in opposite directions produces the same projection. we show these turns from two angles to show that the F and B faces completely “stack” with one another. Situation 1: As four 90 ◦ turns is equivalent to zero turns, turning any face twice cw yields identical projections as that when turning the same face ccw twice. Face sets UD and RL have similar behaviour, in that turning U twice yields a different projection than from turning D twice, just as turning R twice yields different projections than from turning L twice. This is unlike the behaviour of FB, as turning F twice yields identical projections as when turning B twice. Situation 2: If we turn both faces in a set once each, we get four distinct projections per set of parallel faces due to combinations of cw and ccw turns. Again, face sets UD and RL behave similarly. However, the FB set yields only 4−1−2 = 1 distinct projections since turning both faces cw produces an identical projection as if both faces are turned ccw which we can rationalize as Figures 4b and 4c demonstrate how turning F cw is equivalent to turning B ccw and vice versa. Additionally, the projections made by turning the two faces in opposite directions (cw and ccw) can be made by turning either F or B once, which we have already counted under Dt1 (Fig. 4). We sum the projections produced by each situation for Case 1 and get, 2× 2 turn 1 face twice + 4 + turn each face once 1 + turn 1 face twice UD and LR face sets 1 = 14. (11) turn both cw or both ccw FB face set Case 2. The two turns are not parallel to one another. In this case, we consider the number of projections if we turn a face once, and then turn another face once such that the second face is not one within the set of the first face turned. Each face can be turned cw or ccw, so one face translates into two possible turns. If the first turn is U, D, L or R, similar behaviour is observed. Each face can be turned cw or ccw so for UD and LR, eight first turns are possible. If we first turn U, then our second turn can only be R, L, F or B. However, a second turn of F or B produce identical projections so we really have three possible faces for our second turn, which multiplied by two yields six possible second turns. 7 Figure 5: a, projection obtained by turning F cw, U cw. b, projection obtained by turning B ccw, U cw. If the first turn is F or B, we have four possible first turns. Note that there are four first turns as opposed to two because despite that turning F cw and B ccw produces the same projection, the second turn makes them distinct due to the different “thicknesses” of the pieces in F and B that are no longer orthogonal to the established front face (Fig. 5). In this situation, our second turn can be R, L, U or D, not F or B, so we have four possible faces for for our second turn, which multiplied by two yields eight possible second turns. Thus the number of projections for Case 2 is, × 8 possible 1st turns 6 + possible 2nd turns × 4 possible 1st turns 1st turn is U, D, L, R 8 = 80. (12) possible 2nd turns 1st turn is F, B Summing the results of Case 1 and 2 gives, Dt2 = 14 + 80 = 94. (13) 3 turns. We break the problem down into five cases, where using the label “UD and LR face sets” means the first turn must be face either U, D, L or R and using the label “FB face set” means the first turn must be either F or B. Case 1. The three turns are all parallel to one another. Turning a face three times in the same direction, is the same as turning it once in the opposite direction, whose projections are covered by Dt1 . Therefore, we only look at the situation where one face is turned once, and its parallel face is turned twice. Once again we have similar behaviour for face sets UD and LR. That is, turning a face twice and then the other face in the set cw or ccw yields four projections per face set. For face set FB, since all turns are parallel and turning F twice produces the same projection as turning B twice, we have two projections, which are from turning either F or B twice, and then the other face cw or ccw. 8 For Case 1 we have, 2× 2 + turn a face twice, other face cw or ccw 2 turn other face twice, turn remaining face cw or ccw + 2 = 10. (14) FB face set UD and LR face sets Case 2. The first two turns are parallel to one another, but the third turn is not. We have two situations to consider: turning the same face twice and then a non-parallel face once, or turning a face once, its parallel face once, and then a non-parallel face once. Situation 1: Face sets UD and RL behave such that for a set, we have two faces that can be turned twice and then three non-parallel faces for the following turn, which translates into six possible third turns. We have three non-parallel faces because both F and B turns produce the same projection. For face set FB, we still have two faces that can be turned twice as the third turn will lead to distinct projections for the same reason as in 2 turns, Case 2. However, there are then four non-parallel faces for the following turn, which translates into eight possible third turns. Situation 2: The only difference between Situation 1 and 2 is that for the combinations for the first two turns changes from two to four as we are turning two different parallel faces once as opposed to a single face twice. For Case 2, we sum the results of the two situations to get, + 2 × 6 2 × 8 + 2 × number of faces that possible third, number of faces that possible third, can be turned twice can be turned twice non−parallel turns non−parallel turns UD and LR face sets FB face set Situation 1 (15) + 4 × 6 4 × 8 2 × turn a face cw or ccw, possible third, turn a face cw or ccw, possible third, turn other face cw or ccw non−parallel turns turn other face cw or ccw non−parallel turns UD and LR face sets FB face set Situation 2 (16) = 120. (17) Case 3. The second and third turns are parallel to one another but not to the first turn. Case 3 can be thought as the reverse of Case 2, Situation 2. However, in addition to 9 different behaviour between the UD, LR sets and the FB set, depending on whether the second and third turns are FB turns or not, different numbers of projections are produced. That is for a UD or LR face set, there are four possible first turns as each face can turn cw or ccw. If the second turn is U, D, L or R, there are then four possible second turns since only two of these faces (UD or LR) that are not parallel to the first face turned. However, if the second turn is F or B, since the second and third turns are both parallel, there are half, or rather two possible second turns that will yield distinct projections. This is a scenario we have encountered when considering 2 parallel turns. For the FB face set, there are also four possible first turns. There are then eight possible second turns as we must make a non-parallel turn and there are four other faces not in the set. Lastly for all face sets, there are three possible third turns as we must make a turn parallel to the second turn and there are two faces in a set. We have three instead of four possible turns because one turn will reverse the second turn. Reversing the second turn yields a projection that can be attained by one turn, which has already been covered by Dt1 . Thus, for Case 3 the number of projections is calculated by, 2× × 4 possible 1st turns turns per face) possible 2nd turns (two non−parallel faces; not FB) (two × 4 possible 1st turns (two turns per face) × 4 3 possible 3rd turns (turns parallel to 2nd turn) × 2 possible 2nd turns (non−parallel faces FB) 3 possible 3rd turns (turns parallel to 2nd turn) + + UD and LR face sets (18) 4 possible 1st turns (two turns per face) × 8 possible 2nd turns (four non−parallel faces) × 3 possible 3rd turns (turns parallel to 2nd turn) FB face set (19) = 240. (20) Case 4. The first and third turns are parallel to one another but not to the second turn. The order of the parallel and non-parallel turns causes the behaviour of UD, LR and FB to all be the same. In fact, the number of possible first and second turns are the same as that in Case 3’s FB face set. However, there are four possible third turns as there are two parallel faces in any set and none of the four turns could reverse any of the first or second turns. 10 Thus, for Case 4 the number of projections can simply be calculated by, 3× × 4 possible 1st turns (two turns per face) × 8 possible 2nd turns (four non−parallel faces) 4 possible 3rd turns (turns parallel to 1st turn) = 384. (21) UD, LR, and FB face sets Case 5. All three turns are non-parallel to one another. Case 4 and 5 have identical expressions but note that there are four possible third turns for different reasons. That is, in Case 5 the four possible turns come from the last remaining face set that is non-parallel to both the first and second turn. Thus, the number of projections for Case 5 is given by, 3× × 4 possible 1st turns (two turns per face) × 8 possible 2nd turns (four non−parallel faces) 4 possible 3rd turns (turns non−parallel to 1st and 2nd turn) = 384. UD, LR, and FB face sets (22) Summing the results of the five cases (14), (17), (20), (21) and (22) yields, Dt3 = 10 + 120 + 240 + 384 + 384 = 1138. (23) At this point, let’s consider “God’s Number,” which is the maximum number of turns required to solve any valid permutation of the Rubik’s/mirror cube. As God’s Number has been shown to be 20 by Thomas Rokicki et al. [2], the least upper bound for the number of valid and distinct projections for the mirror cube would be 20 Dtn . (24) n=0 Past n = 3, the number of cases will likely become too great and complex for manual calculation to be reasonable. However, we cannot disregard cases because the “turn-by-turn” method depends on the behavioural patterns of the face sets for each case to avoid manual counting of each individual projection. The problem then, is that the behavioural patterns are inconsistent, particularly that of FB, due to the increasing number of turns and the increasing ways the turns can be ordered. At some n it also becomes near impossible to determine whether projections are being repeated without having noted every single projection already counted for comparison. Even at n = 2 notice that for 2 Turns, Situation 2, we already encounter this problem of having to recognize the double-counting of projections that have already been made with fewer turns. Thus, the turn-by-turn method to be impractical for finding the least upper bound. However, our results thus far allows us to obtain a lower bound, Lv , for the number 11 of valid and distinct projections for the mirror cube: 3 Lv = Dtn = Dt0 + Dt1 + Dt2 + Dt3 (25) = 1 + 10 + 94 + 1138 (26) = 1243, (27) n=0 and thus, Lv = 1243 < Pv < 4.325 × 1019 ≈ Gv . 3 (28) Least upper bounds on the Rubik’s cube We digress from bounding the number of mirror cube projections to find the number of valid permutations of the Rubik’s cube such that it has at least n faces that are each uniformly one colour (n = 1, 2, 3, 4, 5, 6). The consistent behaviour observed in judging the allowed positions and orientations is what allows for the following basic procedure to be applied for all cases. We start by splitting the problem into cases and consider the number of times each case occurs. Next we calculate, using combinatorics, the number of permutations per case and multiply by the case frequency. Lastly, we sum the results of each case. This procedure is derived from the idea that we start with a cube in its solved state and consider what pieces can be swapped and orientated differently to retain the uniform colouring of n faces. Notice that edges and corners shared by two or more faces that must be uniformly coloured must have both a fixed position and orientation. This is obvious for edges, but for two corners, even if they have the same colours, if their positions are swapped, their orientation becomes twisted. In other words, the colours also do not align as desired (Fig. 6) Figure 6: Shared corners and edges have a fixed orientation and position regardless of validity. After determining possible positions and orientations, in order to find only the valid permutations we must adhere to the conditions for validity. However, if all pieces have fixed positions, then we need not divide by two since we consider the cube as starting from its solved state, so nothing has been done to affect the validity of the positions. Likewise if all edges or all corners have fixed orientations, then we need not divide by two or three as the validity of the orientations have is assured. 12 When n = 1. Figure 7: We must only keep the white face must be uniform in colour so all pieces with white are restricted to the face with the white centre. The pieces must also be oriented such that white remains on the front face. For one face to be uniform in colour, there is only one way this can occur (Fig. 7). Thus, there is one case. There are six faces that could be uniform in colour, which means that the case occurs six times. In terms of the corners, we must restrict the four that have the desired colour to the four positions on the face whose centre is the matching colour. These four corners also have a fixed orientation. The remaining four corners are consequently restricted to positions not on the restricted face and have unfixed orientations their orientations. Similarly for the edges, we restrict the four edges to the desired face in which they can swap but must have fixed orientations. The remaining edges are again restricted to the remaining positions but do not have fixed orientations. Thus, the number of permutations where one face is uniform in colour is restricted corner positions remaining corner positions restricted edge positions remaining edge × 4! × 4! × 4! positions 8! number of positions (29) 4 corners with fixed orientations 14 4 corners with unfixed orientations × 34 4 edges with fixed orientations × 14 × 8 edges with unfixed orientations 28 × 3×2 6 case occurrences number of orientations (30) = 5778953994240. (31) When n = 2. For two faces to be uniform in colour, there are two ways this can occur (Fig. 8). Thus, there are two cases. Parallel faces. There are three different sets of parallel faces: FB, RL, UD. Therefore, this case occurs three times. Notice that all the orientations of the corners are fixed so we need not divide by three. 13 × 2 Figure 8: a, an example of the parallel faces case, where F and B are the faces that must be uniform in colour. b, an example of two adjacent faces that must be of uniform colour. Adjacent faces. There are twelve different sets of adjacent faces: UR, UL, UF, UB, FR, RB, BL, LF, DR, DL, DF, DB. Therefore, this case occurs twelve times. A set of adjacent faces means that two corners and an edge are being shared between the faces. We apply the same combinatorics techniques after considering what to restrict and fix to obtain, (4!4!) × (4!4!4!) 14 × 14 × 14 × 14 × 24 × × 2 2 number of positions + 3 (32) case occurences number of orientations parallel faces case (2!2!2!1!1!) × (3!3!1!5!) 16 × 32 × 17 × 25 × × 2 3×2 number of positions 12 (33) case occurences number of orientations adjacent faces case = 105504768. (34) When n = 3. For three faces to be uniform in colour, there are two ways this can occur (Fig. 9). All adjacent faces. There are eight different sets of all adjacent faces: UFR, URB, UBL, ULF, DFR, DRB, DBL, DLF. Three faces all adjacent mens that four corners and three edges are being shared. Faces in a line. There are twelve different sets faces that are all in a line: BUF, UFD, FDB, DBU, LUR, URD, RDL, DLU, LFR, FRB, RBL, BLR. In this case, four corners and two edges are being shared. Notice that the orientations of all the corners are fixed so we need not divide by three. 14 Figure 9: a, an example of the all adjacent faces case, where faces ULF must be uniform in colour. b, an example of the faces in a line case, where faces LFR must be uniform in colour. After considering what to restrict and fix we find, 17 × 3 × 19 × 23 (1!)8 × (2!2!2!3!1!1!1!) × ×8 + 2 3×2 (35) all adjacent case 4 2!2!(1!) × (3!3!1!1!2!2!) 2 18 × 110 × 22 × × 12 2 (36) all in a line case = 7680. (37) When n = 4. For four faces to be uniform in colour, there are two ways this can occur (Fig. 10). Figure 10: a, an example of the faces in a ring case, where faces LFRB must be uniform in colour. b, an example of the faces all adjacent case, where faces DLRB must be uniform in colour. Faces in a ring. There are three different sets of faces in a “ring,”: UFDB, URDL, LFRB. In this case, all corners and four edges are being shared. Notice that the orientations of all corners and edges are fixed so we need not divide by two or three. 15 Faces all adjacent. There are twelve different sets faces such that all four are adjacent, or rather there are two adjacent faces that are not uniform in colour: DLFB, DRFB, DLRB, DLRF, UDLB, UDLF, UDRF, UDRB, ULFB, URFB, ULRB, ULRF. There are six corners and five edges being shared. Notice that the orientations of all the corners are fixed so we need not divide by three. After considering what to restrict and fix we find, (1!)8 × (2!)4 (1!)4 (38) × 18 × 18 × 14 × 3 + 2 faces in a ring case 8 (1!) × 2!2!(1!)8 2 18 × 17 × 21 × × 12 2 (39) faces all adjacent case = 48. (40) When n = 5. For five faces to be uniform in colour, there is only one way this can occur. That is, the cube must be in its solved state as the centres are static. Thus, there is only one permutation for n = 5. When n = 6. Having six faces uniform in colour describes a cube in its solved state, of which there is only one permutation. We intended to use the colours of the Rubik’s cube to model the projections of the mirror cube. However, this does not work as each face of the mirror cube involves multiple dimensions that cannot be simply translated to the one colour per face system of the Rubik’s cube. That is, if we translate the least upper bounds found for the Rubik’s cube to the mirror cube, we will have found the number of permutations for n sides to be “smooth” as smoothness on a mirror cube is the equivalent to a face with uniform colouring. We reiterate that the procedure to find these least upper bounds is derived from the idea that we start with a cube in its solved state, and then consider what pieces can be swapped and orientated differently to retain the uniform colouring of n faces. Initially, one way we approached the problem by considering a core and a pile of pieces. Then we find the number of ways to “place” the pieces on the core. This way of thinking should yield the same answer but instead caused undue confusion in that it was not always clear whether over or under-counting was occurring. The salient point is that the perspective from which we approach a problem is crucial. Thus, a change in perspective is the key what ultimately allowed for the calculation of the improved upper bound for the number of mirror cube projections in the following section. 16 4 Improved upper bounds on the mirror cube For this section we define that a piece does not affect a projection if identical projections are produced regardless of whether that piece is present or not. We also adjust the definition of an edge position to define the space where two edges determine the projection, which we name EPn where n = 1, 2, 3, 4, and corner position to define the corner space where a corner set exists, which we name CPn where n = 1, 2, 3, 4 (Fig. 11). With these new definitions, that we are able to say an edge in a corner set is at a corner position. Figure 11: Mirror cube with labelled edge and corner positions. For this projection, blue highlights the edge positions’ projection, and red highlights the corner positions’ projection. Additionally, we further define a projection as the combination of the edge positions’ projection, which is made by the pieces in the four edge positions, and corner positions’ projection, which is made by the pieces in the four corner positions (Fig. 11). By using the limiting properties of the edge positions and showing that the edges can be arranged such that those in corner positions do not affect the projections, we can improve the upper bound on the mirror cube for the number of valid distinct projections. That is, we must show that we have the necessary edge pieces to produce all the possible edge position projections at the edge positions in addition to simultaneously having the necessary edge pieces such that they do not affect to the corner positions’ projections. 4.1 The limited edge measurements Consider the definition of a projection. When we look at the mirror cube from the front, it is the eight positions surrounding the centre that determines a projection’s dimensions. The four edge positions labelled EP1 , EP2 , EP3 and EP4 have only the two edge pieces in the front and back faces of the cube. Therefore, only edges determine the dimensions, and thus the projections, at the edge positions. Even though technically the dimensions of all the edge pieces given in Table 2 include 1.8 cm, this dimension is always shared with the centres to form the cube structure. Thus, the 1.8 cm can be disregarded as it appears in the same places for all permutations, meaning it never affects the projection in any way. Notice that 17 technically, one of the measurements at every edge position is always 1.8 cm due to the centre, but we established that this 1.8 cm can be ignored (Fig. 12). Therefore, we call the remaining, non-1.8 cm, measurement at the edge positions the height. Due to the skewed core of the mirror cube, there is a minimum “height” measuring from each centre at the edge positions (Table 4, Fig. 12). Cf ace CF CB CR CL CU CD 1.8 × 1.8 × height 1.8 × 1.8 × 2.4 1.8 × 1.8 × 1.2 1.8 × 1.8 × 2.0 1.8 × 1.8 × 1.6 1.8 × 1.8 × 0.8 1.8 × 1.8 × 2.8 Table 4: Dimensions of center pieces. Notice that in order for the cube is structured such that the centres have square faces with that only vary in height. Furthermore, the definition of a projection allows us to ignore the heights of CF and CB their heights are orthogonal to the front/back faces. 1.8 cm 1.8 cm Figure 12: Minimum heights at the edge positions due to the static centres. Clearly, CF and CB do not affect the projection. The 1.8 × 1.8 dimensions of the front face’s centre are static so they do not affect the projection either. All edge pieces “shorter” than a centre do not affect the projection. This allows us to determine the heights that are able to affect, or rather, create distinct projections, by considering the number of possible heights at an edge position that exceed the minimum height set by centres. All the possible edge measurements are in centimetres: 0.8, 1.2, 1.6, 2.0, 2.4 and 2.8. Therefore, at EP1 the minimum height is 0.8, so there are six possible distinct heights at EP1 . At EP2 the minimum height is 1.6, so there are four possible distinct heights at EP2 . At EP3 the minimum height is 2.0, so there are three possible distinct heights at EP3 . Lastly at EP4 , the minimum height is 2.8, so there is only one possible distinct height at EP4 . 18 That is, the total number of distinct combinations of dimensions at the edge positions, or rather, the number of edge positions’ projections is 6 × 4 × 3 × 1 = 72. (41) Note that there is redundancy in the edge dimensions as every measurement (excluding 1.8 cm) appears on four separate edge pieces, which ensures that all edge positions’ projection can be made. 4.2 Arranging the edges at the corner positions Consider the remaining four corner positions, at which we have four corner sets, such that each set contains the two corners and one edge (Fig. 13). That is, two corners and one edge collectively control the projection made at each corner position. w measurement l, measurement Figure 13: Example of a corner set outlined and an example of C7’s lw measurement at its current position in CP4 . We label the (horizontal) length measurement and (vertical) width measurement of a piece at a corner position as l and w respectively (Fig. 13) such that the dimensions of a corner position is called an lw measurement, or lw for simplicity’s sake. Pieces have the same lw measurement would produce identical shadows on the wall. The possible measurements making up lw are 0.8 cm, 1.2 cm, 1.6 cm, 2.0 cm, 2.4 cm, and 2.8 cm. By comparing the dimensions of the edges and corners in Table 2, we find that for every corner’s lw, there exists at least one edge piece’s lw that is smaller or equal to that corner’s lw. In each corner set we have two corners, each with an lw measurement. If they are the same, then there exists at least one edge that will not affect that corner position’s projection. If the corners have two different lw measurements, then there exists at least two edges that will not affect that corner position’s projection. Claim. We can make all 72 edge position projections while arranging the remaining edges amongst the corner sets such that they do not affect the corner position projections. 19 PROOF. The most limiting situation for the corner positions is when the corner pairs at all four corner sets have the same lw measurements. That is, we have the smallest number of lw measurements, which translates into the smallest pool of edges that could be placed at the corner positions such that they do not affect the corner positions’ projection. If we show that for the most limiting situation for the corner positions we are able to make all 72 edge position projections, then for all other, less-limited situations, we must still be able to do the same. This is because for less-limited situations, there must be at least one corner set whose corners do not have the same lw measurement, which means there is a greater variety of lw measurements. This translates into an even greater number of edges that could occupy corner positions without affecting the projection. Therefore, if for the smallest number of available edges we can make all edge position projections, then we must still be able to do the same with a greater pool of edges. Now we consider the edge positions’ most limiting projection, where none of the edges exceed the minimum heights set by the centres. If for this most limiting projection we are able to arrange the remaining edges at the corner positions such that they do not affect the projection, then for all other less-limiting edge position projections we must be able to do the same. This is because when we exceed the minimum heights set by the centres, there is a corresponding increase in the number and size of edges that are able to “hide” at the edge positions. That is, larger edges being placed at the edge positions translates into smaller edges being left at the corner positions, in which case the remaining edges at the corner positions certainly will not affect the projection. There is redundancy in the edge and corner dimensions such that every possible measurement appears on exactly four pieces, which we observe in Table 2. There are two corner pieces per corner position so redundancy of the corner dimensions means that a measurement can only appear at a maximum of two corner positions as both corners in a corner position must hold that same measurement to have the same lw measurements. In other words, any l or w measurement could not be in more than two corner positions. Table 2 shows that every lw appears on exactly two pieces, which must be the two corners in the same corner position as we are looking at the most limiting situation for corner positions. From this we also know that all the corner positions must have different lw. Furthermore, Table 2 also shows that for every corner’s lw, there exists an edge piece whose lw is the same. Therefore, we indeed have four edges to arrange in the corner positions such that they do not affect the projection. Since we find that the 1.8 cm in the edge positions is trivial, we only need each of the minimum heights 0.8 cm, 1.6 cm, 2.0 cm, 2.8 cm to be on two pieces (eight pieces total) in order to be able to arrange the edge pieces to make the most limiting edge positions’ projection. However, because of the redundancy of the edge dimensions and that a measurement can only appear at a maximum of two corner positions, we are left with edges whose measurements do not exceed the minimums set by the centres. That is, we certainly have each of the minimum heights on two pieces. Thus, we have shown that even when we consider the most limiting situation for the corner positions with the edge positions’ most limiting projection, we are able to arrange the edges such that the corner positions’ 20 edges do not affect the corner positions’ projection, while the remaining edges still allow for the most limiting edge positions’ projection to be made simultaneously. It follows then, that for all other less-limiting situations for the corner positions and 71 other edge positions’ projections, we are still able to arrange the edges at the corner positions such that they do not affect the corner positions’ projections. Because, Table 2 also shows that for every edge’s lw, there exists an corner piece whose lw is the same, then any projection that can be made with some edge can also be made with the corresponding corner. In short, the edges at the corner positions can be ignored. 4.3 Calculating the improved upper bounds As the edge positions limit the number of measurements that produce distinct edge position projections, when we combine this with how we can ignore the edges in corner positions without eliminating possible projections, we can find an improved upper bound. To find an improved upper bound for the number of valid and invalid distinct projections, which we name U , we multiply the number of distinct projections due to the edge positions and then multiplying by the possible positions and orientations of the corners to attain an upper bound of, U = (6 × 4 × 3 × 1) × 8! × 38 = 19046845440 ≈ 1.905 × 1010 . (42) P < 19046845440 = U. (43) Therefore, To find an improved upper bound for purely the number of valid distinct projections, which we name Uv , we apply the conditions for validity to attain: Uv = (6 × 4 × 3 × 1) × 8! × 38 U = = 1587237120 ≈ 1.587 × 109 . 2×2×3 2×2×3 (44) Thus we incorporate the lower bound to yield a range of Lv = 1243 < Pv < 1587237120 = Uv . (45) Although we have reduced the upper bound by ten orders of magnitude of both P and Pv by using the limiting properties of the edge positions on the number of projections, the main problem lies with the corner sets. The corner positions’ projections are difficult to differentiate further since they depend on two corners and we encounter two situations. We can have total dominance of one corner’s lw measurement over that of the other (Fig. 14a). This situation is already complicated by the three possible orientations of the corners, which are then flipped depending on their position. Even if we just examine the projection made by one corner set, the comparison process is tedious and time-consuming. Of course, the corners all depend on one another, so we cannot even calculate the projections of each corner set separately, as combining the results is another complicated problem. 21 Figure 14: a, example of total dominance, where the corner projection depends on two lengths. b, example of partial dominance, where the corner projection depends on four lengths. The second situation is yet more convoluted, in which partial dominance occurs (Fig. 14b). That is, the l measurement of one corner overtakes that of the other corner, but the first corner’s w measurement is overtaken by the other corner. Because one of the parts is protruding from the other, we must consider the lw measurements of both corner pieces. Therefore currently, the issue is finding a method to deal with these two cases effectively, such that we can approach the number of distinct projections made by the corner positions. Another change in perspective that evades the issue of total and partial dominance entirely is a plausible avenue to explore. 5 Acknowledgements We owe a great deal to our mentor Fok-Shuen Leung for his guidance, time spent listening to our barely coherent explanations, and encouragement as we limped along meandering paths that more often than not lead to dead ends. James Charbonneau was also a wonderful source of knowledge throughout this project, particularly for his instruction regarding group theory. Thank you very much for everything. References [1] Gallian, J. A. (2010). Contemporary Abstract Algebra Belmont, CA: Brooks Cole. [2] Gods Number is 20. (n.d.). Retrieved from http://www.cube20.org/ [3] Mulholland, J. (2011). Rubiks Cube: The Fundamental Theorem of Cubology [PDF]. Retrieved from http://people.math.sfu.ca/ jtmulhol/math302/notes/20-RubiksCubeFundamentalTheoremCubology.pdf 22
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Undergraduate Research /
- Bounds on Rubik's cube and mirror cube configurations
Open Collections
UBC Undergraduate Research
Bounds on Rubik's cube and mirror cube configurations Hsu, Grace; Liu, Sissi Jun 30, 2012
pdf
Page Metadata
Item Metadata
Title | Bounds on Rubik's cube and mirror cube configurations |
Creator |
Hsu, Grace Liu, Sissi |
Date Issued | 2012-06-30 |
Description | Given a 3x3x3 mirror cube, we find the number of valid and distinct projections up to and including three 90° turns. Next, we calculate the number of valid permutations of the traditional 3x3x3 Rubik's cube such that it has at least one, two, three, four, five or six faces with the same colour. We then return to the mirror cube and find improved upper bounds for the number of distinct projections. |
Type |
Text |
Language | eng |
Series | University of British Columbia. Science One Research Projects |
Date Available | 2012-07-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0107234 |
URI | http://hdl.handle.net/2429/42650 |
Affiliation |
Science, Faculty of |
Peer Review Status | Unreviewed |
Scholarly Level | Undergraduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 51869-Hsu_G_et_al_Sci_One_Prog_2011-2012.pdf [ 30.48MB ]
- Metadata
- JSON: 51869-1.0107234.json
- JSON-LD: 51869-1.0107234-ld.json
- RDF/XML (Pretty): 51869-1.0107234-rdf.xml
- RDF/JSON: 51869-1.0107234-rdf.json
- Turtle: 51869-1.0107234-turtle.txt
- N-Triples: 51869-1.0107234-rdf-ntriples.txt
- Original Record: 51869-1.0107234-source.json
- Full Text
- 51869-1.0107234-fulltext.txt
- Citation
- 51869-1.0107234.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.51869.1-0107234/manifest