2125-Qiang-Ye-devoir-7.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <center>Devoir 7 IFT2125-A-H19</center>\n",
    "\n",
    "**Student**: Qiang Ye (20139927) \n",
    "\n",
    "**Date**: 24 Jan 2019\n",
    "\n",
    "mailto: samuel.ducharme@umontreal.ca\n",
    "<hr>\n",
    "\n",
    "**Question**\n",
    "\n",
    "Vous faites partie d’un groupe de $n$ personnes ($n > 1$) enlevées par des ravisseurs. Au bout de quelques mois, ces derniers en ont marre de vous car vous leur compliquez la vie. Ils vous appellent un soir et vous disent que le lendemain matin, il vont se débarasser de vous. On vous alignera en file indienne de manière à ce que chacun voit ceux qui sont devant lui et chacun entend ce qui est dit. Ensuite, chacun aura un chapeau déposé sur sa tête, soit rouge, soit noir, sans que la couleur lui soit visible. Pour terminer, les ravisseurs vont commencer à poser la même question, en commençant par la personne à la fin de la queue : **Quelle est la couleur de ton chapeau?** La bonne réponse donne la liberté, la mauvaise l’exécution sur le coup.\n",
    "\n",
    "Vous avez donc la nuit pour réfléchir à une méthode qui libérerait le plus grand nombre des hotages.\n",
    "\n",
    "1. Combien de personnes peuvent être sauvées?\n",
    "2. Comment? C’est-à-dire, écrivez un algorithme pour répondre à la question des raviseurs et expliquez - ou prouvez - pourquoi en l’exécutant le nombre d’exécutés (sic) sera minimisé. L’algorithme comprendra une boucle de $1$ à $n$ à l’intérieur de laquelle il y aura, entre autre, la réponse de la i-ème personne.\n",
    "<hr>\n",
    "\n",
    "**Answer**\n",
    "1. Au moins $n-1$ personnes devraient être sauvées, sauf celle qui parle en premier(la dernière personne dans la file); il y a une possibilité de 50% que toutes les personnes pourraient être sauvées.\n",
    "\n",
    "2. \n",
    "\n",
    "**Strategy**:\n",
    "\n",
    "We use index $1$ to $n$ represents the persons from the head to the tail of the line respectively.\n",
    "    \n",
    "Suppose $C_i$ represents the number of the hats with one kind of color in front of the $i_{th}$ person in the line. Obviously, we can define: \n",
    "\n",
    "$$C_1 = 0$$. \n",
    "We count RED hat in this problem, yet counting BLACK doesn't change the problem and the solution at all.\n",
    "    \n",
    "Let $D_i$ be the declaration of the $i_{th}$ person about the color of the hat on his/her head. \n",
    "\n",
    "$$D_i \\in \\{0, 1\\} \\tag{0}$$\n",
    "\n",
    "where 1 means the color being counted, 0 means the other color.\n",
    "    \n",
    "Let $H_i$ be the number of hats with the color being counted in the declaration history(by the persons after current person). For $1\\le i < n$,\n",
    "$$H_i = \\sum_{j = i+1}^{n} D_j \\tag{1}$$\n",
    "and define: \n",
    "$$H_n = 0 \\tag{2}$$\n",
    "\n",
    "For the $n_{th}$ person, \n",
    "\n",
    "$$ D_n = \\mathbf 1_{\\{C_n \\text{ mod } 2 = 1\\}} = C_n \\text{ mod } 2  \\tag{3} $$    \n",
    "For the $i_{th}$ person,\n",
    "\n",
    "\\begin{align*}\n",
    "&D_i = \\mathbf 1_{\\{(C_i + H_i - D_n) \\text{ mod } 2 \\neq D_n\\}}\\\\\n",
    "\\Longleftrightarrow & D_i = \\mathbf 1_{\\{ (C_i + H_i ) \\text{ mod } 2 = 1\\}}\\\\\n",
    "\\Longleftrightarrow & D_i = (C_i + H_i) \\text{ mod } 2 \\tag{4}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Formular (4) can also be applied to the last person based on our definition by formula (2).\n",
    "\n",
    "Use this strategy, the last person has 50% chance to be saved or executed, wherase the rest should be saved.\n",
    "    \n",
    "**Proof**:\n",
    "Step1: If $C_n \\text{ mod } 2 = 1$, $D_n = 1$, means the last person saw there are Odd number of RED hat in front of him/her and he/she declare his/her own cat color is also RED. otherwise, he/she will declare BLACK.\n",
    "\n",
    "Note that $H_{n-1} = D_n$. $D_{n-1} = \\mathbf 1_{\\{C_i \\text{ mod } 2 \\neq D_n\\}}$ is very obvious, which means if both $C_n$ and $C_{n-1}$ are the same, then $D_{n-1}$ should be BLACK, otherwise, RED.\n",
    "\n",
    "Step2: Suppose the strategy is valid for $i_{th}$ person, that is formula (4) is valid for $i_{th}$ person; furthermore, we also have:\n",
    "\n",
    "$$ C_i = C_{i-1} + D_{i-1} \\text{, and } H_i = H_{i-1} - D_i \\tag{5}$$\n",
    "\n",
    "Taking (5) to (4), also based on **(0)**, we then come to:\n",
    "\n",
    "\\begin{align*}\n",
    "&D_i = (C_{i-1} +D_{i-1} + H_{i-1} - D_i) \\text{ mod } 2 \\\\\n",
    "\\Longleftrightarrow& 0 = (C_{i-1} + D_{i-1} + H_{i-1}) \\text{ mod } 2\\\\\n",
    "\\Longleftrightarrow& D_{i-1} = (C_{i-1} + H_{i-1}) \\text{ mod } 2 \\tag{6} \\\\\n",
    "\\end{align*}\n",
    "   \n",
    "This proves that if the strategy is valid for $i_{th}$ person, then it is also valid for $(i-1)_{th}$ person. As we alredy knew it's valid for the last person, we therefore can conclude it's valid for all $n$ persons in the line.\n",
    "\n",
    "**Algorithm**:\n",
    "```\n",
    "    input: n_person\n",
    "    initialization: declare_history = [], a empty list with elements in {0, 1}\n",
    "    output: declare_history\n",
    "    def strategy_for_hat_color_problem():\n",
    "        for person_index from 0 to n-1:\n",
    "            n_red_before = number of red(1) hats before current person\n",
    "            n_red_history = count number of red(1) hats in declare_history\n",
    "            declare = (n_red_before + n_red_history) % 2\n",
    "            declare_history.insert(0, declare)\n",
    "        \n",
    "        return declare_history\n",
    "```\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Codes**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def declare_of_person(index, hat_colors_before, declare_history):\n",
    "    \"\"\"the declaration of the person with index\n",
    "    params\n",
    "        index: from 0 to n_person-1, int\n",
    "        hat_colors_before: true hat colors before current person, [int]\n",
    "        declare_history: a list of declaration of person standing behind \n",
    "            current person, should have n_person-1-index elements, the first \n",
    "            element is the person just behind current person, [int]\n",
    "    returns\n",
    "        declaration of current person: 1: red, 0: black, int\n",
    "        \n",
    "        declare_history: alsmo modified.\n",
    "    \"\"\"\n",
    "    # count the number of red hats before himself/herself\n",
    "    n_red_before = sum(hat_colors_before)\n",
    "    n_red_history = sum(declare_history) if len(declare_history) > 0 else 0\n",
    "    # the following three lines are equivalent.\n",
    "    declare = (n_red_before + n_red_history) % 2\n",
    "    #declare = 1 if (n_red_before + sum(declare_history)) % 2 == 1 else 0\n",
    "    #declare = 0 if (n_red_before + sum(declare_history[:-1])) % 2 == declare_history[-1] else 1\n",
    "    \n",
    "    print(\"Index:{:>2}, red_before: {:<2}, Declare:{}\".format(index, n_red_before, declare))\n",
    "    declare_history.insert(0, declare)\n",
    "    return declare"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index:19, red_before: 9 , Declare:1\n",
      "Index:18, red_before: 9 , Declare:0\n",
      "Index:17, red_before: 8 , Declare:1\n",
      "Index:16, red_before: 8 , Declare:0\n",
      "Index:15, red_before: 7 , Declare:1\n",
      "Index:14, red_before: 7 , Declare:0\n",
      "Index:13, red_before: 6 , Declare:1\n",
      "Index:12, red_before: 6 , Declare:0\n",
      "Index:11, red_before: 5 , Declare:1\n",
      "Index:10, red_before: 5 , Declare:0\n",
      "Index: 9, red_before: 4 , Declare:1\n",
      "Index: 8, red_before: 4 , Declare:0\n",
      "Index: 7, red_before: 3 , Declare:1\n",
      "Index: 6, red_before: 2 , Declare:1\n",
      "Index: 5, red_before: 2 , Declare:0\n",
      "Index: 4, red_before: 1 , Declare:1\n",
      "Index: 3, red_before: 1 , Declare:0\n",
      "Index: 2, red_before: 1 , Declare:0\n",
      "Index: 1, red_before: 1 , Declare:0\n",
      "Index: 0, red_before: 0 , Declare:1\n",
      "true color: [1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]\n",
      "   declare: [1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]\n",
      "\n",
      "Check if the first 19 persons all tell correct hat colors: True\n"
     ]
    }
   ],
   "source": [
    "n_person = 20\n",
    "hat_colors = [random.randint(0, 1) for _ in range(n_person)]\n",
    "declare_history = []\n",
    "\n",
    "for i in range(n_person-1, -1, -1): # from the last person to the first\n",
    "    declare_of_person(i, hat_colors[0:i], declare_history)\n",
    "    \n",
    "print(\"true color:\",hat_colors)\n",
    "print(\"   declare:\", declare_history)\n",
    "print(\"\\nCheck if the first {} persons all tell correct hat colors:\".format(n_person-1), end = \" \")\n",
    "print(declare_history[:-1] == hat_colors[:-1]) # do not compare the last"
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}