17-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Twin Knights\n",
    "\n",
    "**a**\n",
    "\n",
    "- Suppose King Arthur holds a jousting tournament where the jousts are in pairs as in a tennis tournament (see problem 16)\n",
    "- The 8 knights in the tournament are evenly matched, and they include the twin knights Balin and Balan\n",
    "- *What is the chance that the twins meet in a match during the tournament?*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b**\n",
    "\n",
    "- Replace 8 by $2^{n}$ in the above problem\n",
    "- *Now, what is the chance that they meet?*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "### a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We'll go through the scenarios and figure out the probability for each\n",
    "\n",
    "**Face each other in the first round**\n",
    "\n",
    "- This requires that their numbers are either (1,2), (3,4), (5,6), or (7,8)\n",
    "- Let's assume Balin chooses first. There are 8 possible numbers he can choose\n",
    "    - But then there's only one number that Balan can choose so they face each other\n",
    "- We know that there are $8\\cdot7$ different ways the twins can be assigned positions in the ladder\n",
    "    - Therefore:\n",
    "        \n",
    "$$\n",
    "P(\\text{Facing each other in the first round}) = \\frac{8\\cdot1}{8\\cdot7} = \\frac{1}{7}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Face each other in the second round**\n",
    "\n",
    "- This requires a few conditions\n",
    "    1. The two twins are assigned to the same half of the bracket\n",
    "    2. They don't face each other in the first round\n",
    "    3. Both twins win their first match\n",
    "    \n",
    "- The probability that they're in the same half of the bracket, but not facing each other is $\\frac{8\\cdot2}{8\\cdot7} = \\frac{2}{7}$ and the probability that they both win their first match is $\\frac{1}{2}\\frac{1}{2} = \\frac{1}{4}$\n",
    "    - Therefore:\n",
    "    \n",
    "$$\n",
    "P(\\text{Face each other in the second round}) = \\frac{2}{7}\\frac{1}{4} = \\frac{1}{14}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Face each other in the final round**\n",
    "\n",
    "- The conditions for this are:\n",
    "    1. The twins are assigned to different halves of the bracket\n",
    "    2. Both twins win their first two matches\n",
    "    \n",
    "- The probability that they're assigned to different halves is $\\frac{8\\cdot4}{8\\cdot7} = \\frac{4}{7}$\n",
    "- The probability that they both win their first two matches is $\\frac{1}{2^{4}}=\\frac{1}{16}$ \n",
    "    - Therefore:\n",
    "    \n",
    "$$\n",
    "P(\\text{Facing each other in final round}) = \\frac{4}{7}\\frac{1}{16} = \\frac{1}{28}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Therefore\n",
    "\n",
    "$$\n",
    "P(\\text{Facing each other}) = \\frac{1}{7} + \\frac{1}{14} + \\frac{1}{28} = \\frac{1}{4}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_____\n",
    "\n",
    "- Tying out by simulation\n",
    "    - **Note**: the function below is pretty sloppy\n",
    "        - Whatevs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sim():\n",
    "    i_balin, i_balan = np.random.choice(np.arange(1,9), 2, replace=False)\n",
    "    \n",
    "    # Testing whether they face off in the first round\n",
    "    sorted_pair = sorted([i_balin, i_balan])\n",
    "    if (sorted_pair==[1,2]) or (sorted_pair==[3,4]) or (sorted_pair==[5,6]) or (sorted_pair==[7,8]):\n",
    "        return 1\n",
    "    \n",
    "    # Testing whether they face off in the second round\n",
    "    if ((i_balin in [1,2,3,4])&(i_balan in [1,2,3,4])) or ((i_balin in [5,6,7,8])&(i_balan in [5,6,7,8])):\n",
    "        win_balin, win_balan = np.random.randint(0, 2, 2)\n",
    "        if win_balin==win_balan==1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "    else:\n",
    "        # Testing whether they face off in the third round\n",
    "        win_balin1, win_balan1, win_balin2, win_balan2 = np.random.randint(0, 2, 4)\n",
    "        if win_balin1==win_balan1==win_balin2==win_balan2==1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.24973"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n_trials = 100000\n",
    "count = 0\n",
    "\n",
    "for _ in range(n_trials):\n",
    "    count += sim()\n",
    "\n",
    "count/n_trials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Eyyyyy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "### b. \n",
    "\n",
    "- The pattern we can see is:\n",
    "\n",
    "$$\n",
    "P(\\text{Facing each other in a tournament with }2^{n} \\text{ Jousters}) = \\frac{1}{2^{n}-1} \\sum_{i=0}^{n-1}\\frac{1}{2^{i}} = \\frac{2}{2^{n}-1}\\left (1 - \\frac{1}{2^{n}} \\right ) = \\frac{1}{2^{n-1}}\n",
    "$$"
   ]
  }
 ],
 "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
}