01-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Sock Drawer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A drawer contains red socks and black socks\n",
    "- When two socks are drawn at random, the probability that both are red is 1/2\n",
    "\n",
    "a. *How small can the number of socks in the drawer be?*\n",
    "\n",
    "b. *How small if the number of black socks is even?*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "______\n",
    "\n",
    "# a.\n",
    "\n",
    "- Let's first consider a very simple case: one black sock and two red socks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "list_socks = ['R1', 'R2', 'B']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We loop through the possible permutations of socks drawn from the drawer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "R1 R2\n",
      "R1 B\n",
      "R2 R1\n",
      "R2 B\n",
      "B R1\n",
      "B R2\n"
     ]
    }
   ],
   "source": [
    "for sock_1 in list_socks:\n",
    "    for sock_2 in [x for x in list_socks if x!=sock_1]:\n",
    "        print(sock_1, sock_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So, there are 6 permutations, and only 2 of them involve both socks being red\n",
    "    - Therefore, the probability that we draw 2 red socks in this setup is only 1/3\n",
    "    \n",
    "- We note that we don't really care about the order the socks are drawn, just the total number\n",
    "    - So, we could have calculated this probability as:\n",
    "    \n",
    "$$\n",
    "P(\\text{2 red socks}) = \\frac{2}{3}\\frac{(2-1)}{(3-1)} = \\frac{2}{3}\\frac{1}{2} = \\frac{1}{3}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We can generalize this for $r$ red socks in a drawer of $N$ socks as:\n",
    "\n",
    "$$\n",
    "P(\\text{2 red socks}) = \\frac{r}{N}\\frac{r-1}{N-1}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We know that we want this probability to be equal to 1/2 so\n",
    "\n",
    "$$\n",
    "\\frac{1}{2} = \\frac{r(r-1)}{N(N-1)} \\implies N(N-1) = 2r(r-1)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Let's loop through some possible values to see if we achieve this equality"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loop():\n",
    "    found = False\n",
    "\n",
    "    N = 3\n",
    "\n",
    "    while not found:\n",
    "        N += 1\n",
    "        for r in range(N):\n",
    "            if N*(N-1)==2*r*(r-1):\n",
    "                return N, r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 3)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "loop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- According to this output, if we have 4 socks total with 3 red and 1 black, our probability of selecting 2 red socks is 1/2\n",
    "    - Let's confirm this by looping through the permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "R1 R2 True\n",
      "R1 R3 True\n",
      "R1 B False\n",
      "R2 R1 True\n",
      "R2 R3 True\n",
      "R2 B False\n",
      "R3 R1 True\n",
      "R3 R2 True\n",
      "R3 B False\n",
      "B R1 False\n",
      "B R2 False\n",
      "B R3 False\n"
     ]
    }
   ],
   "source": [
    "list_socks = ['R1', 'R2', 'R3', 'B']\n",
    "\n",
    "for sock_1 in list_socks:\n",
    "    for sock_2 in [x for x in list_socks if x!=sock_1]:\n",
    "        print(sock_1, sock_2, sock_1[0]==sock_2[0]=='R')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- As we can see, there are 6 permutations **with** two red socks, and 6 permutations **without**\n",
    "    - So, our probability of getting two red socks is indeed 1/2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "# b.\n",
    "\n",
    "- We can use the logic from above, with a small tweak\n",
    "    - We make a small change to our `loop` function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loop2():\n",
    "    found = False\n",
    "\n",
    "    N = 3\n",
    "\n",
    "    while not found:\n",
    "        N += 1\n",
    "        for r in range(N):\n",
    "            b = N-r\n",
    "            if (N*(N-1)==2*r*(r-1))&(b%2==0):\n",
    "                return N, r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(21, 15)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "loop2()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So, according to this new function, we'll need 21 socks with 15 of them being red\n",
    "    - We can loop through the permutations to confirm this result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "list_socks = 15*['R']+(21-15)*['B']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "420 210 0.5\n"
     ]
    }
   ],
   "source": [
    "n = 0\n",
    "count = 0\n",
    "\n",
    "for i, sock_1 in enumerate(list_socks):\n",
    "    list_temp = list_socks[:i] + list_socks[i+1:]\n",
    "    for sock_2 in list_temp:\n",
    "        n += 1\n",
    "        if sock_1 == sock_2 == 'R':\n",
    "            count += 1\n",
    "            \n",
    "print(n, count, count/n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Eyyy\n",
    "    - Confirms our result"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}