THE RAINBOW MASTERBALL Some rules for the rainbow masterball (referred to simply as "masterball" in the following): A masterball sphere has 32 tiles of 8 distinct colors. We shall assume that the masterball is in a fixed position in space, centered at the origin. A geodesic path from the north pole to the south pole is called a "longitudinal line" and a closed geodesic path parallel to the equator is called a "latitudinal line". There are 8 longitudinal lines and 3 latitudinal lines. In spherical coordinates, the longitudinal lines are at the angles which are multiples of Pi/4 (i.e., at theta = nPi/4, n=1,..,8) and the latitudinal lines are at phi = Pi/4, Pi/2, 3Pi/4. (Here Pi is the usual 3.141592...) The sphere shall be oriented by the right-hand rule - the thumb of the right hand wrapping along the polar axis points towards the north pole. We assume that one of the longitudinal lines has been fixed once and for all. This fixed line shall be labeled "1", the next line (with respect to the orientation above) as "2", and so on. Allowed moves: One may rotate the masterball east-to-west by multiples of Pi/4 along each of the 4 latitudinal bands or by multiples of Pi along each of the 8 longitudinal lines. A "facet" will be one of the 32 subdivisions of the masterball created by these geodesics. A facet shall be regarded as immobile positions on the sphere and labeled either by an integer i in {1,...,32} or by a pair (i,j) in [1,4]\times [1,8], whichever is more convenient at the time. If a facet has either the north pole or the south pole as a vertex then we call it a "small" or "polar" facet. Otherwise, we call a facet "large" or "middle". A "coloring" of the masterball will be a labeling of each facet by one of the 8 colors in such a way that (a) each of the 8 colors occurs exactly twice in the set of the 16 small facets, (b) each of the 8 colors occurs exactly twice in the set of the 16 large facets. A "move" of the masterball will be a change in the coloring of the masterball associated to a sequence of manuevers as described above. If we now identify each of the 8 colors with an integer in {1, ...,8} and identify the collection of facets of the masterball with a 4x8 array of integers in this range. To "solve" an array one must, by an appropriate sequence of moves corresponding to the above described rotations of the masterball, put this array into a "rainbow" position so that the matrix entries of each column has the same number. Thus the array 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 is "solved". The array 6 7 8 1 2 3 4 5 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 corresponds to a rotation of the north pole facets by 3Pi/4. NOTATION We use "matrix" notation to denote the 32 facets of the masterball. The generators for the latitudinal rotations are denoted r1, r2, r3, r4, so, for example, r1 sends 11 12 13 14 15 16 17 18 21 22 23 24 25 26 27 28 31 32 33 34 35 36 37 38 41 42 43 44 45 46 47 48 to 12 13 14 15 16 17 18 11 21 22 23 24 25 26 27 28 31 32 33 34 35 36 37 38 41 42 43 44 45 46 47 48 As you look down at the ball from the north pole, this move rotates the ball clockwise. The other moves r2, r3, r4 rotate the associated band of the ball in the same direction - clockwise as viewed from the north pole. The generators for the longitudinal rotations are denoted f1, f2,...,f8, so for example, f1 sends 12 13 14 15 16 17 18 11 21 22 23 24 25 26 27 28 31 32 33 34 35 36 37 38 41 42 43 44 45 46 47 48 to 44 43 42 41 16 17 18 11 34 33 32 31 25 26 27 28 24 23 22 21 35 36 37 38 15 14 13 12 45 46 47 48 With these rules, one can check the relation f5=r1^4*r2^4*r3^4*r4^4*f1*r1^4*r2^4*r3^4*r4^4. Exerccise: Find similar identities for f6, f7, f8. Also, one can check that r1=(f3*f7)^{-1}*r4^{-1}*f3*f7. Exercise: There are similar identities for r2, r3, r4. Find them. Identify the facets of the masterball with the entries of the array 8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 24 23 22 21 20 19 18 17 32 31 30 29 28 27 26 25 (there is a reason for labeling the facets "backwards" like this but it's not important). We may express the generators of the masterball group in disjoint cycle notation as a subgroup of S_{32} (the symmetric group on 32 letters): r1^{-1} = (1,2,3,4,5,6,7,8), r2^{-1} = (9,10,11,12,13,14,15,16), r3^{-1} = (17,18,19,20,21,22,23,24), r4^{-1} = (25,26,27,28,29,30,31,32), f1 = (5,32)(6,31)(7,30)(8,29)(13,24)(14,23)(15,22)(16,21), f2 = (4,31)(5,30)(6,29)(7,28)(12,23)(13,22)(14,21)(15,20), f3 = (3,30)(4,29)(5,28)(6,27)(11,22)(12,21)(13,20)(14,19), f4 = (2,29)(3,28)(4,27)(5,26)(10,21)(11,22)(12,23)(13,24), f5 = (1,28)(2,27)(3,26)(4,25)(9,20)(10,19)(11,18)(12,17), f6 = (8,27)(1,26)(2,25)(3,32)(16,19)(9,18)(10,17)(11,24). f7 = (7,26)(8,25)(1,32)(2,31)(15,18)(16,17)(9,24)(10,23), f8 = (6,25)(7,32)(8,31)(1,30)(14,17)(15,24)(16,23)(9,22), Exercise: Verify that the properties of a permutation puzzle are satisfied for this puzzle. 2x2 RUBIK'S CUBE The "pocket" Rubik's cube has 6 sides, or "faces", each of which has 2x2=4 "facets", for a total of 24 facets: ______________ /______/u_____/ | /______/______/| | 6 sides: front (f), back (b), | | | | | left (l), right (r), | | | r/| up (u), down (d) |______f______ /| | | | | | | | | | |/ |______|______|/ Fix an orientation of the Rubik's cube in space. Therefore, we may label the six sides as f, b, l, r, u, d, as in the picture. It has 8 subcubes. Each face of the cube is associated to a "slice" of 4 subcubes which share a facet with the face. The face, along with all of the 4 cubes in the "slice", can be rotated by 90 degrees clockwise. We denote this move by the upper case letter associated to the lower case letter denoting the face. For example, F denotes the move which rotates the front face by 90 degrees to clockwise. ______________ /______/u_____/ | | /______/______/| | | / \ | _|_ | | | | | | / | \ | r/| | The move F | |__ /__f__\___ /| | | | | __ | | | | | | | | |\__|__/ | |/ \ / | |______|______|/ <------------------- As in chapter 2, we label the 24 facets of the 2x2 Rubik's cube as follows: +--------------+ | 1 2 | | u | | 3 4 | +--------------+--------------+--------------+--------------+ | 5 6 | 9 10 | 13 14 | 17 18 | | l | f | r | b | | 7 8 | 11 12 | 15 16 | 19 20 | +--------------+--------------+--------------+--------------+ | 21 22 | | d | | 23 24 | +--------------+ The 24 facets will be denoted by xyz where x is the face on which the facet lives and y, z (or z, y - it doesn't matter) indicate the 2 edges of the facet. Written in clockwise order: front face: fru, frd, fld, flu back face: blu, bld, brd, bru right face: rbu, rbd, rfd, rfu left face: lfu, lfd, lbd, lbu up face: urb, urf, ulf, ulb down face: drf, drb, dlb, dlf Exercise: Verify that the properties of a permutation puzzle are satisfied for this puzzle. For future reference, we call this system of notation (which we will also use for the 3x3 and 4x4 Rubik's cube) the "Singmaster notation". 3x3 RUBIK'S CUBE Much has been written on the Rubik's cube (see, for example, [Ru] or[Si]). In this section we shall, for the most part, simply introduce enough basic notation to allow us to check that the puzzle is in fact a permutation puzzle. The Rubik's cube has 6 sides, or "faces", each of which has 3x3 = 9 "facets", for a total of 54 facets. We label these facets 1, 2, ..., 54 as follows: +--------------+ | 1 2 3 | | 4 u 5 | | 6 7 8 | +--------------+--------------+--------------+--------------+ | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | 12 l 13 | 20 f 21 | 28 r 29 | 36 b 37 | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | +--------------+--------------+--------------+--------------+ | 41 42 43 | | 44 d 45 | | 46 47 48 | +--------------+ then the generators, corresponding to the six faces of the cube, may be written in disjoint cycle notation as: F:= (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11), B:= (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27), L:= ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35), R:= (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24), U:= ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19), D:= (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40). Exercise: Check this. The notation for the facets will be similar to the notation used for the 2x2 Rubik's cube. The corner factes will have the same notation and the edge facets will bve denoted by xy, where x is the face the facet lives on and y is the face the facet borders to. In clockwise order, starting with the upper right-hand corner of each face: front face: fru, fr, frd, fd, fld, fl, flu, fu back face: blu, bl, bld, bd, brd, br, bru, bu right face: rbu, rb, rbd, rd, rfd, rf, rfu, ru left face: lfu, lf, lfd, ld, lbd, lb, lbu. lu up face: urb, ur, urf, uf, ulf, ul, ulb, ub down face: drf, dr, drb, db, dlb, dl, dlf, df Exercise: Verify that the properties of a permutation puzzle are satisfied for this puzzle. 4x4 RUBIK'S CUBE The 4x4 Rubik's cube has 6 sides, or "faces", each of which has 4x4 = 16 "facets", for a total of 96 facets. As usual, we fix an orientation of the cube in space, so we may pick a front face, back face, ... . We label these facets 1, 2, ..., 96 as follows: +-----------------+ | 49 50 51 52 | | 61 62 63 64 | u | 73 74 75 76 | | 85 86 87 88 | +------------------+-----------------+-----------------+-----------------+ | 53 54 55 56 | 1 2 3 4 | 5 6 7 8 | 9 10 11 12 | | 65 66 67 68 | 13 14 15 16 | 17 18 19 20 | 21 22 23 24 | l f r b | 77 78 79 80 | 25 26 27 28 | 29 30 31 32 | 33 34 35 36 | | 89 90 91 92 | 37 38 39 40 | 41 42 43 44 | 45 46 47 48 | +------------------+-----------------+-----------------+-----------------+ | 57 58 59 60 | | 69 70 71 72 | d | 81 82 83 84 | | 93 94 95 96 | +-----------------+ Notation: We need notation for the facets and for the moves. Facets: To label the facets, we must pick an orientation of each face, say clockwise. For example, the the front face may be labeled as +---------------------+ | flu fu1 fu2 fru | | fl1 f4 f1 fr1 | f | fl2 f3 f2 fr2 | | fld fd2 fd2 frd | +---------------------+ The labeling of the other faces is similar. Exercise: Label the other 5 faces. Moves: Parallel to each face x are 4 slices of 16 subcubes each labeled X1, X2, X3, X4, in order of their distance from the face. For example, the front face f has 16 subcubes comprising the F1 slice, the two inner slices are F2, F3, and the last slice F4 is actually the same as the first slice B1 associated to the back face. The 12 generators (written in disjoint cycle notation), corresponding 2 each to the six faces of the cube are given by: U1=(49, 52, 88, 85)( 62, 63, 75, 74)( 50,64,87,73) (51,76,86,61)(5,1,53,9)(6,2,54,10)(7,3,55,11)(8,4,56,12), U2=(17, 13, 65, 21)( 18, 14, 66, 22)( 19,15,67,23)(20,16,68,24), L1=(96,48,49,1)(84,36,61,13)(72,24,73,25)(60,12,85,37) (89,53,56,92)(90,65,55,80)(91,77,54,68)(66,67,79,78), L2=(59,11,86,38)(71,23,74,26)(83,35,62,14)(95,47,50,2), F1=(89,5,93,92)(77,17,81,80)(65,29,69,68)(53,41,57,86) (1,4,40,37)(2,16,39,25)(3,28,38,13)(14,15,27,26), F2=(73,6,81,91)(74,18,82,79)(75,30,83,67)(76,42,84,55), R1=(40,88,9,57)(28,76,21,69)(16,64,33,81)(4,52,49,93) (41,5,8,44)(42,17,7,32)(43,29,6,20)(18,19,31,30), R2=(39,87,10,58)(27,75,22,70)(15,63,34,82)(3,51,46,94), B1=(52,53,44,60)(51,65,32,59)(50,77,20,58)(49,89,8,57) (9,12,48,45)(10,24,47,33)(11,36,46,21)(22,23,35,34), B2=(54,72,43,64)(66,71,31,63)(78,70,19,62)(90,69,7,61), D1=(57, 60, 96, 93)( 58, 72, 95, 81)(59, 84, 94, 69) (70,71,83,82)(45,89,37,41)(46,90,38,42)(47,91,39,43)(48,92,40,44), D2=(33, 77, 25, 29)( 34, 78, 26, 30)(35, 79, 27, 31)(36,80,28,32). Exercise: Verify that the properties of a permutation puzzle are satisfied for this puzzle.