\documentclass{article}
\usepackage[utf8]{inputenc}
\begin{document}
\par
Ejercicio 6 del Capitulo 1
\par Sea $\{S_i\}_{i= 1..n}$ la lista de barcos, y $\{P_i\}_{i= 1..n}$ la lista de puertos. Sea $A$ un array n*m, donde $A(i,j)$ dice el lugar donde se encuentra el barco $i$ el dia $j$.
Construiremos $\sigma : \{1 \cdots n\}\rightarrow \{1 \cdots m\}$ que dice el dia en que se trunca cada barco, y probaremos la correctitud del algoritmo, es decir, las condicion: $\forall i,j \in\{1 \cdots n\}$  $(\forall d > \sigma(i))$ $ \sigma(j) \geq d \Rightarrow A(j,d)\neq A(i,\sigma(i)).$
\\[12pt]
\par
\par d = m
\par listS = $\{1 \cdots n\}$
\par listP = $\{1 \cdots m\}$
\par Mientras  notEmpty(list) hacer\{
\par 	Encontrar $P_{i_1} \cdots P{i_l}$ en listP de los puertos que terminan su trabajo en el dia d, para los barcos en listS\footnote{Es decir, son los puertos que no reciben mas barcos de $listS$ luego del dia $d$}. . Asignar $\sigma(S_{j_1})$ = d $c\dots \sigma(s_{j_l})$ = d, donde $A(j_k,d) = i_k$.
\par Eliminar $P_{i_1} \cdots P_{i_l}$ de listP.
\par Eliminar $S_{j_1} \cdots S_{j_l}$ de listS.
\par d = d+1
\par \}
\\[12pt]
\par Correctitud:
\par Veamos ahora que se cumple la condicion de correctitud anteriormente propuesta:   Supongamos por absurdo $\exists i,j \in\{1 \cdots n\}$  $(\exists d_0 > \sigma(i)) A(j,d_0)=A(i,\sigma(i))$ y $\sigma(j) \geq d_0$. $\sigma(j) = d_0$ es imposible pues seria $A(j,d_0) = A(i,d_0)$, lo cual es absurdo por hipotesis. Entonces, se debe tener $\sigma(j) > d_0$. Pero en el paso del algoritmo en que $d = d_0$ $j$ aun no ha truncado y por lo tanto $j\in listS$. El algoritmo calcula que la labor de $A(i\sigma(i))$ no ha terminado, pues $j$ pasara por alli el dia $d_0$. Pero esto se contradice con el algoritmo.
Ahora falta ver que
\end{document}