Polish the answer of 1.d

1 files changed, 22 insertions, 18 deletions

diff --git a/main.tex b/main.tex
index 2803200..0fa91ec 100644
--- a/main.tex
+++ b/main.tex
@@ -39,7 +39,6 @@
 \end{question}
 
 \begin{commandline}[Gale-Shapley algorithm, from lecture slides, edited for the context]
-
     \begin{verbatim}
     Initialize each person to be free.
     while (some student is free and hasn't applied to every college) {
@@ -53,7 +52,6 @@
             c rejects m (c)
     }
     \end{verbatim}
-
  \end{commandline}
 
 A quick trace of the algorithm;
@@ -124,33 +122,39 @@ $S'$ could not have occurred since men propose in accordance to their preference
 
 % 1}}} %
 
-% question d TODO {{{1 %
+% question d ✅ {{{1 %
 
 \begin{question}
     Give an instance of $n$ colleges, $n$ students, and their preference lists so that the Gale-Shapley algorithm requires only $O(n)$ iterations, and prove this fact.
 \end{question}
 
-% TODO: you abused n and now they're both fucked <05-11-20, yigit> %
+For a proposer agnostic formation, arrange the preference lists of colleges and students as follows;
 
-Arrange the preference lists such as every $m^{\text{th}}$ student arranges their preference list such as;
-
-\begin{equation}
+\begin{gather*}%
     \label{eq:student_prefs}
-    C_n, C_{n-1}, C_{n-2}, \dots, C_{1}
-\end{equation}
+    C_{1} \rightarrow \left\{ S_{1}, S_{n}, S_{n-1}, \dots, S_{2} \right\} \\
+    C_{2} \rightarrow \left\{ S_{2}, S_{n}, S_{n-1}, \dots, S_{3} \right\} \\
+    \dots  \\
+    C_{k} \rightarrow \left\{ S_{k}, S_{n}, S_{n-1}, \dots, S_{k+1} \right\} \\
+    \dots \\
+    C_{n} \rightarrow \left\{ S_{n}, S_{n-1}, S_{n-2}, \dots, S_{1} \right\} \\
+\end{gather*}
 
-Whereas every college can arrange their preference list as;
+\begin{gather*}%
+    \label{eq:student_prefs}
+    S_{1} \rightarrow \left\{ C_{1}, C_{n}, C_{n-1}, \dots, C_{2} \right\} \\
+    S_{2} \rightarrow \left\{ C_{2}, C_{n}, C_{n-1}, \dots, C_{3} \right\} \\
+    \dots  \\
+    S_{k} \rightarrow \left\{ C_{k}, C_{n}, C_{n-1}, \dots, C_{k+1} \right\} \\
+    \dots \\
+    S_{n} \rightarrow \left\{ C_{n}, C_{n-1}, C_{n-2}, \dots, C_{1} \right\} \\
+\end{gather*}
 
-\begin{equation}
-    \label{eq:college_prefs}
-    S_n, S_{n-1}, S_{n-2}, \dots, S_{1}
-\end{equation}
+Where the student list $\{S_1, S_2, \dots, S_{n}\}$ and college list $\{C_1, C_2, \dots, C_{n}\}$ are shifted.
 
-The arrangement in (\ref{eq:college_prefs}) is not crucial since no college will be given a chance to \enquote{trade up}.
+In this setup, ever proposer will propose to the first suitor in their preference list which is guaranteed to be free since they are not the first on any other suitor's preference list.
 
-Every proposer applies to colleges in decreasing order from their preference list.
-For $n=1$, $S_1$ applies to $C_1$ and the algorithm terminates in $n=1$ steps.
-For $n=k$, $S_1$ applies to $C_1$ which is free, $S_2$ applies to $C_2$ which is again free up to $S_k$ which can freely apply to $C_k$ and the algorithm terminates in $k$ steps after every student applied to the college on top of their preference list which was guaranteed to be free.
+The algorithm in this instance runs in $\mathcal{O}(n)$ iterations, every proposer will follow the (a) branch in the algorithm given under Question~\ref{q:1_a}.
 
 % 1}}} %