\documentclass[11pt]{article}

%\usepackage{customizations}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[enableskew]{youngtab}
\usepackage{hyperref}
\usepackage{graphicx}

\renewcommand{\mod}[1]{\ensuremath{\;\textrm{mod }{#1}}}
\usepackage[all]{xy}



\textwidth=15cm
\oddsidemargin=0.7cm
\voffset=-1cm
\textheight=20cm

\begin{document}

\newcommand{\x}{\times}

\title{
  MATH 157: Mathematics in the world \\
  \Large{Homework 9 (Due April 16th, 2019 at 1:00PM)}
}
\date{}

\maketitle

\vspace{-1cm}

\subsection*{Problem 1}
100 hostages are being held by a bunch of pirates who like to play math games.
The pirates set up the following game.

They label the 100 hostages with number 1 - 100, and ask them to go into a secret room one by one.
The pirates randomly put 100 pieces of paper labeled by 1 - 100 into the 100 boxes labeled by 1 -100.
These boxes are put in the secrete room, and each hostage can open 50 of them.
If the hostage opens a box containing his/her number, he/she will get a {\em pass}.
He/she will then leave the room, and a pirate will close all the boxes that he/she opened.
The next person in line will enter the room and repeat the process.

If {\em every hostage} gets a pass, they will be saved.
Otherwise, all of them will be thrown into the ocean.
The hostages are allowed to discuss the strategy before hand, but no more communication when the game starts.

\begin{enumerate}
\item What is the the probability of surviving if everyone randomly opens 50 boxes?
\item If there are only 2 hostages with 2 boxes, what is the optimal strategy for them to survive?
\\\\

In the 100 hostages problem, we will consider the following strategy:
each prisoner opens the box with his own number, then the box whose number is contained in the first box, and so on.

Consider the sequence of numbers that a certain prisoner encounters: $x_0$
 (the inital box numbered with the prisoner's own number), $x_1$ (number contained in box $x_0$), $x_2$ (number contained in box $x_2$), ... 
Since each number is contained in only one box, this sequence cannot contain any repeated element as long as it doesn't loop back to $x_0$. Eventually the sequence has to loop back to $x_0$ since it will run out of numbers. At that point, the prisoner has found his own name. The critical problem for the prisoner is whether the loop completes before or after the prisoner has opened the maximum of 50 boxes.

A way to arrange distinct numbers into as many boxes is called a {\em permutation}. Opening box number $k$ and looking at the number that it contains is called applying that permutation. Repeated applications of a permutation eventually runs into a loop; such a loop is called a {\em cycle}.
Therefore, the probability of surviving with this strategy equals to the probability of having no cycles of length 51 or above in a permutation of size 100.

\item How many ways to to arrange 100 numbers into 100 (numbered) boxes?
\item How many ways to arrange 100 numbers into 100 (numbered) boxes so that we have a cycle of size $c$ with $c \geq 51$?
\item What is the probability of surviving applying this strategy?
\end{enumerate}

\subsection*{Problem 2}
This time the pirates put two randomly red and blue hats on each hostage's head. 
Each hostage will see the colors of other people's hats, but not the colors of his own. 
The hostages are not allowed to pass any info to each other. 
At the pirates' signal each has to write the number of blue hats on his head. 
If they are all correct, all of them survive. 
If at least one of them is wrong, all of them die.

After observing other people's hats, a hostage needs to decide on a number in between $0$ and $2$. 
Therefore, we can model a strategy for a hostage as a function
$$
f: D^{n-1} \longrightarrow \{0,1,2\}
$$
where $D = \{(rr), (rb), (br), (bb)\}$ denote the $4$ combinations of blue and red hats, and $n$ is the number of hostages.

\begin{enumerate}
\item A strategy is called a {\em constant strategy} if the number the hostage writes does not depend on hats on other hostages' head, i.e., the strategy function $f$ is a constant function. 
What is the optimal probability of surviving if hostages only use constant strategies?
\item We will consider the following {\em dynamical strategy}:
each hostage `assumes' that the total number of blue hat is a multiple of $3$.
That is, if a hostage sees the total number of blue hats on other hostages' head is a multiple of 3, he/she writes $0$. 
If he/she sees 1 more than a multiple of $3$, he/she writes $2$.
If he/she sees 2 more than a multiple of $3$, he/she writes $1$.

Similarly, we can have strategies that each hostage `agrees' that the total number of blue hat is $k \mod 3$.

Show that there is at least one such strategy with probability at least $1/3$.
\\\\
We will now analyze the case $n=2$ in more detail.
\item If $n=2$, how many strategies are there for each hostage?
\item Consider the strategy:
each hostage `assumes' that the total number of blue hat is $2$. 
Compute the probability of surviving.
\item(Extra Credit) Write a program that shows the above strategy optimal for $n=2$. 
How many different combinations of strategies also give the optimal bound?
\end{enumerate}

\subsection*{Problem 3}
Alice and Bob are playing a game together. Alice observes a sequence of independent unbiased random bits $(A_n)$, i.e., $A_n = 0$ or $1$ with equal probability.
Similarly, Bob observes a sequence of independent unbiased random bits $(B_n)$.
Alice writes a number $a$ and Bob writes a number $b$ without communication. 
They win the game if $A_b = B_a = 1$.
\begin{enumerate}
\item How do we model a strategy for Alice (and Bob)? \footnote{You can check how we model strategies in Problem 2}
\item What are the optimal constant strategies?
\item Can you come up with a dynamical strategy which gives better probability of wining?
\end{enumerate}

\subsection*{Problem 4}
Let 
\begin{align*}
T_\alpha:S^1 = \mathbb{R}/\mathbb{Z} &\longrightarrow S^1 = \mathbb{R}/\mathbb{Z}\\
x \mod 1&\mapsto x+\alpha \mod 1
\end{align*}
be rigid rotation. Assume $\alpha$ is an irrational number, we will show that $0, T_\alpha(0), T^2_\alpha(0) = T_\alpha(T_\alpha(0)), ... $ is dense in the following way.
\begin{enumerate}
\item Show that $T^k_\alpha(0) = k \alpha$.
\item Show that $0, T_\alpha(0), T^2_\alpha(0) = T_\alpha(T_\alpha(0)), ... $ are all distinct.
\item Given $K$, use pigeon hole principle to show that there exists $n$ such that $T^n_\alpha(0) < 1/K$.
\item Use the previous one or otherwise, show that for any $K$, and any $x\in S^1 = \mathbb{R}/\mathbb{Z}$, there exists $n$ such that $|T^n_\alpha(0)-x| < 1/K$.
\end{enumerate}

\subsection*{Problem 5}
A monkey is typing letters A-Z randomly and independently of each other, each letter with probability $1/26$. We are interested in finding out the expected time for the monkey to type ABCDE.
Let $E_k$ be the expected time that the monkey types ABCDE given that the monkey has typed the first $k$ letters correctly.
\begin{enumerate}
\item Use first step analysis to write down equations about $E_k$.
\item Compute $E_0$.
\item Do the same analysis for ABRACADABRA.\footnote{Be careful here, the equations are different from the first case. Assume the monkey has typed 4 correct letters, if the next letter the monkey types is B, then we are back to the situation where monkey has typed 2 correct letters (instead of 0!).}
\end{enumerate}



\end{document}







