Bounds on Rubik’s Cube and Mirror Cube Con gurations 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 nd 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, ve or six faces with the same colour. We then return to the mirror cube and nd 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’ di erent 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 ipped 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 di erent colours each piece carries are what make the Rubik’s cube’s pieces distinct, whereas it is the pieces’ di erent 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 speci c 1Figure 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 Corner piece colours E1 blue, yellow C1 blue, yellow, orange E2 blue, orange C2 blue, yellow, red E3 blue, red C3 blue, white, orange E4 blue, white C4 blue, white, red E5 orange, yellow C5 green, yellow, red E6 red, yellow C6 green, yellow, orange E7 orange, white C7 green, white, red E8 red, white C8 green, white, orange E9 green, yellow E10 green, red E11 green, orange E12 green, white Table 1: Description of Rubik’s cube pieces in terms of their colours. Notice that each piece is distinct due to di erent 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 de ne 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 2Edge piece dimensions (cm) Corner piece dimensions (cm) E1 1.8 1.2 0.8 C1 1.6 1.2 0.8 E2 1.8 1.6 0.8 C2 2.0 1.2 0.8 E3 1.8 2.0 0.8 C3 1.6 2.4 0.8 E4 1.8 2.4 0.8 C4 2.0 2.4 0.8 E5 1.8 1.6 1.2 C5 2.0 1.2 2.8 E6 1.8 2.0 1.2 C6 1.6 1.2 2.8 E7 1.8 1.6 2.4 C7 2.0 2.4 2.8 E8 1.8 2.0 2.4 C8 1.6 2.4 2.8 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 Table 2: Dimensions of mirror cube pieces. Notice that every piece is distinct due to di erent dimensions. Figure 2: a, projection of the mirror cube in its solved state. Notice that all dimensions parallel to the red line do not a ect the projection made. b and c, examples of di erent permutations that yield the same projection as in 2a. as di erent \shadows on a wall." Notice that pieces’ dimensions that are orthogonal to the front face, and thus the shadow on the wall, do not a ect 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 di erent 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 o the puzzle. The parity of a permutation is either even or odd. The permutations of the Rubik’s 3cube, 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 de nition 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 satis ed. 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 ips. 1.2 The size of the cube group There are twelve edge positions corresponding to the twelve edge pieces, and eight cor- ner 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 di erent ways, whereas each corner can be oriented in three di erent 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: G = 0 @ 12! 212 | {z } ways to position and orient the edges 1 A 0 @ 8! 38 | {z } ways to position and orient the corners 1 A (1) = 5:1902403929::: 1020 (2) 5:19 1020: (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 13 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 ips 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 Edge 2 Orientation Corner 1 Corner 2 Orientation not ipped not ipped valid not twisted not twisted valid not ipped ipped invalid not twisted twisted cw invalid ipped not ipped invalid not twisted twisted ccw invalid ipped ipped valid twisted cw not twisted invalid twisted cw twisted cw invalid twisted cw twisted ccw valid twisted ccw not twisted invalid twisted ccw twisted cw valid twisted ccw twisted ccw invalid Table 3: We consider any two edges and any two corners and all the possible com- binations 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 = 0 B B @ 12!8! 2| {z } number of valid positions 1 C C A 0 B B @ 212 38 2 3 | {z } number of valid orientations 1 C C A (4) = 4:3252003274::: 1019 (5) 4:325 1019: (6) 1.3 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) and Pv < Gv 4:325 10 19: (8) 2 A lower bound on the mirror cube Following the preliminary upper bound on Pv, we nd a lower bound on the the number of valid and distinct projections by nding the exact number of valid and distinct 5projections created by up to and including three 90 turns. We de ne \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 de ne 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 di erent 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 projec- tions’ 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 de ne a projection, turning F clockwise is the same as turning B counterclockwise (Fig. 4). Thus, Dt1 = 0 @ 6 2 | {z } 2 distinct projections per face 1 A 2|{z} F and B produce identical projections = 10: (10) 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. 6Figure 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 di erent projection than from turning D twice, just as turning R twice yields di erent 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 0 B @ 2|{z} turn 1 face twice + 4|{z} turn each face once 1 C A | {z } UD and LR face sets + 0 B @ 1|{z} turn 1 face twice + 1|{z} turn both cw or both ccw 1 C A | {z } FB face set = 14: (11) 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 rst face turned. Each face can be turned cw or ccw, so one face translates into two possible turns. If the rst 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 rst turns are possible. If we rst 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. 7Figure 5: a, projection obtained by turning F cw, U cw. b, projection obtained by turning B ccw, U cw. If the rst turn is F or B, we have four possible rst turns. Note that there are four rst 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 di erent \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, 0 @ 8|{z} possible 1st turns 6|{z} possible 2nd turns 1 A | {z } 1st turn is U; D; L; R + 0 @ 4|{z} possible 1st turns 8|{z} possible 2nd turns 1 A | {z } 1st turn is F; B = 80: (12) Summing the results of Case 1 and 2 gives, Dt2 = 14 + 80 = 94: (13) 3 turns. We break the problem down into ve cases, where using the label \UD and LR face sets" means the rst turn must be face either U, D, L or R and using the label \FB face set" means the rst 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. 8For Case 1 we have, 2 0 B B @ 2|{z} turn a face twice; other face cw or ccw + 2|{z} turn other face twice; turn remaining face cw or ccw 1 C C A | {z } UD and LR face sets + 2|{z} FB face set = 10: (14) Case 2. The rst 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 di erence between Situation 1 and 2 is that for the combinations for the rst two turns changes from two to four as we are turning two di erent 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 6 6 6 6 6 6 4 2 0 B B @ 2|{z} number of faces that can be turned twice 6|{z} possible third; non parallel turns 1 C C A | {z } UD and LR face sets + 0 B B @ 2|{z} number of faces that can be turned twice 8|{z} possible third; non parallel turns 1 C C A | {z } FB face set 3 7 7 7 7 7 7 7 5 | {z } Situation 1 + (15) 2 6 6 6 6 6 6 6 4 2 0 B B @ 4|{z} turn a face cw or ccw; turn other face cw or ccw 6|{z} possible third; non parallel turns 1 C C A | {z } UD and LR face sets + 0 B B @ 4|{z} turn a face cw or ccw; turn other face cw or ccw 8|{z} possible third; non parallel turns 1 C C A | {z } FB face set 3 7 7 7 7 7 7 7 5 | {z } Situation 2 (16) = 120: (17) Case 3. The second and third turns are parallel to one another but not to the rst turn. Case 3 can be thought as the reverse of Case 2, Situation 2. However, in addition to 9di erent behaviour between the UD, LR sets and the FB set, depending on whether the second and third turns are FB turns or not, di erent numbers of projections are produced. That is for a UD or LR face set, there are four possible rst 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 rst 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 rst 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 2 6 6 6 6 6 6 6 6 6 6 6 6 4 0 B B B @ 4|{z} possible 1st turns (two turns per face) 4|{z} possible 2nd turns (two non parallel faces; not FB) 3|{z} possible 3rd turns (turns parallel to 2nd turn) 1 C C C A + 0 B B B @ 4|{z} possible 1st turns (two turns per face) 2|{z} possible 2nd turns (non parallel faces FB) 3|{z} possible 3rd turns (turns parallel to 2nd turn) 1 C C C A 3 7 7 7 7 7 7 7 7 7 7 7 7 5 | {z } UD and LR face sets + (18) 0 B B B @ 4|{z} possible 1st turns (two turns per face) 8|{z} possible 2nd turns (four non parallel faces) 3|{z} possible 3rd turns (turns parallel to 2nd turn) 1 C C C A | {z } FB face set (19) = 240: (20) Case 4. The rst 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 rst 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 rst or second turns. 10Thus, for Case 4 the number of projections can simply be calculated by, 3 0 B B B @ 4|{z} possible 1st turns (two turns per face) 8|{z} possible 2nd turns (four non parallel faces) 4|{z} possible 3rd turns (turns parallel to 1st turn) 1 C C C A | {z } UD; LR; and FB face sets = 384: (21) 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 di erent reasons. That is, in Case 5 the four possible turns come from the last remaining face set that is non-parallel to both the rst and second turn. Thus, the number of projections for Case 5 is given by, 3 0 B B B @ 4|{z} possible 1st turns (two turns per face) 8|{z} possible 2nd turns (four non parallel faces) 4|{z} possible 3rd turns (turns non parallel to 1st and 2nd turn) 1 C C C A | {z } UD; LR; and FB face sets = 384: (22) Summing the results of the ve 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 20X n=0 Dtn : (24) 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 nding the least upper bound. However, our results thus far allows us to obtain a lower bound, Lv, for the number 11of valid and distinct projections for the mirror cube: Lv = 3X n=0 Dtn = Dt0 + Dt1 + Dt2 + Dt3 (25) = 1 + 10 + 94 + 1138 (26) = 1243; (27) and thus, Lv = 1243 < Pv < 4:325 10 19 Gv: (28) 3 Least upper bounds on the Rubik’s cube We digress from bounding the number of mirror cube projections to nd 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 di erently 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 xed 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 xed orientation and position regardless of validity. After determining possible positions and orientations, in order to nd only the valid permutations we must adhere to the conditions for validity. However, if all pieces have xed 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 a ect the validity of the positions. Likewise if all edges or all corners have xed orientations, then we need not divide by two or three as the validity of the orientations have is assured. 12When 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 xed orientation. The remaining four corners are consequently restricted to positions not on the restricted face and have un xed orientations their orientations. Similarly for the edges, we restrict the four edges to the desired face in which they can swap but must have xed orientations. The remaining edges are again restricted to the remaining positions but do not have xed orientations. Thus, the number of permutations where one face is uniform in colour is 0 @ restricted corner positions z}|{ 4! remaining corner positions z}|{ 4! 1 A 0 @ restricted edge positions z}|{ 4! remaining edge positions z}|{ 8! 1 A 2| {z } number of positions (29) 0 B B B @ 4 corners with xed orientations z}|{ 14 4 corners with un xed orientations z}|{ 34 1 C C C A 0 B B B @ 4 edges with xed orientations z}|{ 14 8 edges with un xed orientations z}|{ 28 1 C C C A 3 2 | {z } number of orientations 6|{z} case occurrences (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 di erent sets of parallel faces: FB, RL, UD. Therefore, this case occurs three times. Notice that all the orientations of the corners are xed so we need not divide by three. 13Figure 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 di erent 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 x to obtain, 2 6 6 4 (4!4!) (4!4!4!) 2| {z } number of positions 14 14 14 14 24 2| {z } number of orientations 3|{z} case occurences 3 7 7 5 | {z } parallel faces case + (32) 2 6 6 4 (2!2!2!1!1!) (3!3!1!5!) 2| {z } number of positions 16 32 17 25 3 2 | {z } number of orientations 12|{z} case occurences 3 7 7 5 | {z } adjacent faces case (33) = 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 di erent 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 di erent 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 xed so we need not divide by three. 14Figure 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 x we nd, " (1!)8 (2!2!2!3!1!1!1!) 2 17 3 19 23 3 2 8 # | {z } all adjacent case + (35) 2 4 2!2!(1!)4 (3!3!1!1!2!2!) 2 18 110 22 2 12 3 5 | {z } all in a line case (36) = 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 di erent 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 xed so we need not divide by two or three. 15Faces all adjacent. There are twelve di erent 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 ve edges being shared. Notice that the orientations of all the corners are xed so we need not divide by three. After considering what to restrict and x we nd, 2 4 (1!)8 (2!)4(1!)4 2 18 18 14 3 3 5 | {z } faces in a ring case + (38) 2 4 (1!)8 2!2!(1!)8 2 18 17 21 2 12 3 5 | {z } faces all adjacent case (39) = 48: (40) When n = 5. For ve 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 nd 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 di erently 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 nd 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. 164 Improved upper bounds on the mirror cube For this section we de ne that a piece does not a ect a projection if identical projec- tions are produced regardless of whether that piece is present or not. We also adjust the de nition of an edge position to de ne the space where two edges determine the projection, which we name EPn where n = 1; 2; 3; 4, and corner position to de ne the corner space where a corner set exists, which we name CPn where n = 1; 2; 3; 4 (Fig. 11). With these new de nitions, 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 de ne 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 a ect the projections, we can improve the upper bound on the mirror cube for the number of valid distinct pro- jections. 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 simul- taneously having the necessary edge pieces such that they do not a ect to the corner positions’ projections. 4.1 The limited edge measurements Consider the de nition 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 a ects the projection in any way. Notice that 17technically, 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). Cface 1.8 1.8 height CF 1.8 1.8 2.4 CB 1.8 1.8 1.2 CR 1.8 1.8 2.0 CL 1.8 1.8 1.6 CU 1.8 1.8 0.8 CD 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 de nition 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 a ect the projection. The 1:8 1:8 dimensions of the front face’s centre are static so they do not a ect the projection either. All edge pieces \shorter" than a centre do not a ect the projection. This allows us to determine the heights that are able to a ect, 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. 18That is, the total number of distinct combinations of dimensions at the edge posi- tions, 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. l, measurement w 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 nd 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 a ect that corner position’s projection. If the corners have two di erent lw measurements, then there exists at least two edges that will not a ect that corner position’s projection. Claim. We can make all 72 edge position projections while arranging the remain- ing edges amongst the corner sets such that they do not a ect the corner position projections. 19PROOF. 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 small- est 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 a ect 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 a ecting 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 a ect 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 a ect 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 di- mensions 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 di erent 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 a ect the projection. Since we nd 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’ 20edges do not a ect 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 a ect 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 nd an improved upper bound. To nd 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) Therefore, P < 19046845440 = U: (43) To nd 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 = U 2 2 3 = (6 4 3 1) 8! 38 2 2 3 = 1587237120 1:587 109: (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 di cult to di erentiate 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 ipped 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. 21Figure 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 rst 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 nding a method to deal with these two cases e ectively, 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-RubiksCube- FundamentalTheoremCubology.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 2012-06-30
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 |
DOI | 10.14288/1.0107234 |
URI | http://hdl.handle.net/2429/42650 |
Affiliation |
Science, Faculty of |
Peer Review Status | Unreviewed |
Scholarly Level | Undergraduate |
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