jupyter-notebooks/the-locker-prank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Locker Prank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "Via Popular Science,\n",
    "\n",
    "_There are 100 lockers that line the main hallway of Chelm High School. Every night, the school principal makes sure all the lockers are closed so that there will be an orderly start to the next day. One day, 100 mischievous students decide that they will play a prank. The students all meet before school starts and line up. The first student then walks down the hallway, and opens every locker. The next student follows by closing every other locker (starting at the second locker). Student 3 then goes to every third locker (starting with the third) and opens it if it’s closed, and closes it if it’s open. Student 4 follows by opening every fourth locker if it’s closed and closing it if it’s open. This goes on and on until Student 100 finally goes to the hundredth locker. When the principal arrives later in the morning, which lockers does she find open?_\n",
    "\n",
    "Here is the [problem statement](https://scottpdawson.com/the-locker-prank/) (nicely written out on Scott Dawson's blog) and here is the [Popular Science solution](https://www.popularmechanics.com/science/math/a31155135/solution-riddle-locker-prank/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mathematical Approach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Brainstorming:\n",
    "\n",
    "Let's think about each locker number's list of factors (e.g., locker 6 has factors 1, 2, 3, and 6 itself). Let's also think about the factors as _visitors_ -- because they are! What you may notice (perhaps after some time with pen/paper/whiteboard) is that Students 1, 2, 3, and 6 must visit Locker 6.\n",
    "\n",
    "#### First key realization:\n",
    "\n",
    "* If a locker is visited an even number of times, it has to be shut\n",
    "\n",
    "So, Locker 6 is definitely shut at the end of this prank.\n",
    "\n",
    "##### Corollary:\n",
    "\n",
    "* If a locker is visited an odd number of times, it has to be open\n",
    "\n",
    "#### Third key realization:\n",
    "\n",
    "* Only perfect squares have an odd number of factors (visitors)\n",
    "    * Why? For instance, consider 9, which has factors 1, 3, and 9\n",
    "        * Important: Even when a factor is \"repeated\" as in $ 3 \\times 3 = 9$, it only counts as 1 factor!\n",
    "        * And there aren't two copies of Student 3, right?!\n",
    "        \n",
    "        \n",
    "#### Answer:\n",
    "\n",
    "Only the Lockers with perfect squares for their numbers are left open. These are lockers\n",
    "\n",
    "$$1, \\, \\, 4, \\, \\,  9, \\, \\,  16, \\, \\,  25, \\, \\,  36, \\, \\,  49, \\, \\,  64, \\, \\,  81, \\,  \\text{and} \\,  100.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Brute Force Approach (using Python!)\n",
    "\n",
    "The third realization in the above math approach is a little trickier than the others. (Or, at least, took me longer to reach than the first two. Your experience may vary.)\n",
    "\n",
    "But for fun, let's say you got the first two realizations but didn't care to think through which numbers have an odd number of factors. Why don't we make Python do the work for us?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import the numpy package, for vector operations and remainder calculations\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(100, 1)\n"
     ]
    }
   ],
   "source": [
    "track = np.zeros((100,1)) # define a 100x1 vector filled with 0's to encode information about each locker\n",
    "print(np.shape(track)) # let's check that the shape is what we think it is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 0. 0. 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  0. 0. 0. 1.]]\n"
     ]
    }
   ],
   "source": [
    "# think of \"i\" as a single locker (we have to go up to 101 because of python indexing)\n",
    "for i in range(1,101):\n",
    "    \n",
    "    c = 0 # counts visits to locker i\n",
    "    \n",
    "    # think of \"j\" as a single student\n",
    "    for j in range(1,101):\n",
    "        \n",
    "        # check if student j is a factor/visitor of locker i (if so, i/j will have a zero remainder)\n",
    "        if np.remainder(i,j) == 0:\n",
    "            c = np.copy(c) + 1 # this counts as a visit, so increase c by 1\n",
    "        else:\n",
    "            c = np.copy(c) # if the remainder is nonzero, the student doesn't visit locker i\n",
    "    \n",
    "    # if locker i was visited an even number of times, it will be closed\n",
    "    # which we encode with a \"0\" in the storage vector \"track\"\n",
    "    if np.remainder(c,2) == 0:\n",
    "        track = np.copy(track) # keep this entry as a zero -- closed\n",
    "    \n",
    "    # if the locker was not visited an even number of times, it will be open\n",
    "    # which we encode with a \"1\" in the storage vector \"track\"\n",
    "    else:\n",
    "        track[i-1] = 1 # open\n",
    "\n",
    "print(np.transpose(track)) # let's take a look at the track vector (transposed so it's not super \"tall\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Locker 1 is open\n",
      "Locker 4 is open\n",
      "Locker 9 is open\n",
      "Locker 16 is open\n",
      "Locker 25 is open\n",
      "Locker 36 is open\n",
      "Locker 49 is open\n",
      "Locker 64 is open\n",
      "Locker 81 is open\n",
      "Locker 100 is open\n"
     ]
    }
   ],
   "source": [
    "# Now let's print out the lockers that are open\n",
    "# The i+1 in the print statement again has to do with python indexing, which starts counting at 0\n",
    "for i in range(100):\n",
    "    if track[i] == 1:\n",
    "        print('Locker', i+1, 'is open')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Success! The answers match with both approaches"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py3",
   "language": "python",
   "name": "py3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}