{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an ipython (jupyter) worksheet with code from the lecture notes for the course\n",
    "**Permutation Puzzles: A Mathematical Perspective**, by Jamie Mulholland\n",
    "\n",
    "Coures webpage: http://www.sfu.ca/~jtmulhol/math302 <br />\n",
    "Course notes booklet: http://www.sfu.ca/~jtmulhol/math302/notes/302notes.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 5: From Puzzles to Permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 Oval Track Puzzle\n",
    "\n",
    "The permutation corresponding to the legal moves $R$, $R^{-1}$, and $T$ are as follows:\n",
    "$$\n",
    "\\begin{array}{l}\n",
    "R = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) \\\\\n",
    "R^{-1} = (1,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2)\\\\\n",
    "T = (1,4)(2,3)\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "Note that $T^{-1}=T$.  This is due to the fact that spinning the turntable in either direction achieves the same result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Oval Track Puzzle\n",
    "S20=SymmetricGroup(20)\n",
    "R=S20(\"(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)\")\n",
    "T=S20(\"(1,4)(2,3)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 5.6**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,2)(3,20)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R*T*R^(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,18,15,12,9,6,4,2,19,16,13,10,7,20,17,14,11,8)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R^(-4)*T*R^(2)*T*R^(-1) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Other calculations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,3)(4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R*T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4,6,8,10,12,14,16,18,20,5,7,9,11,13,15,17,19)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(R*T)^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,3)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(R*T)^(17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hungarian Rings Puzzle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Hungarian Rings Puzzle\n",
    "S38=SymmetricGroup(38)\n",
    "L=S38(\"(1,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2)\")\n",
    "R=S38(\"(1,38,37,36,35,6,34,33,32,31,30,29,28,27,26,25,24,23,22,21)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 5.8**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2,38,20,19,18,17,16,15,14,13,12,11,10,9,8,7,34,5,4,3)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R^(-1)*L*R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,25)(6,11)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L^5*R^5*L^(-5)*R^(-5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rubik's Cube"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Rubik's Cube\n",
    "S48=SymmetricGroup(48)\n",
    "R=S48(\"(25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24)\")\n",
    "L=S48(\"(9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35)\")\n",
    "U=S48(\"(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19)\")\n",
    "D=S48(\"(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)\")\n",
    "F=S48(\"(17,19,24,22)(18,21,23,20)(6,25,43,16)(7,28,42,13)(8,30,41,11)\")\n",
    "B=S48(\"(33,35,40,38)(34,37,39,36)(3,9,46,32)(2,12,47,29)(1,14,48,27)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,3,38,43,11,35,27,32,30,17,9,33,48,24,6)(2,5,36,45,21,7,4)(8,25,19)(10,34,26,29,31,28,18)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R*U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$RU$ is the product of a 15-cycle, 3-cycle, and two 7-cycles.  Therefore, we know its order is lcm(15,7,3)=105"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "105"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(R*U).order()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, raising it to the power of 15 would kill the 15-cycle and the 3-cycle, leaving us with some 7-cycles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2,5,36,45,21,7,4)(10,34,26,29,31,28,18)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(R*U)^(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Other calculations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "R^2*U^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(R^2*U^2)^3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(R^2*U*F)^(18)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.3",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}