Encontrar la cadena máxima dentro de un grafo acíclico dirigido problema de palabras.

Question

Supongamos que 55 alumnos matriculados en un curso se alinean arbitrariamente. Demuestre que puedo recorrer la fila e identificar 8 estudiantes (no necesariamente consecutivos) que estén en orden creciente de estatura o en orden decreciente de estatura. Supongamos que no hay dos alumnos exactamente de la misma altura.

He intentado utilizar el teorema de Mirsky para demostrar encontrar la cadena máxima, pero estoy atascado en encontrar el número mínimo de anticadenas posibles.

Answer 1

Se trata de una aplicación directa del teorema de Erdős-Szekeres.

Prueba: Entregar a cada alumno $i$ en línea un par de valores $(x_i,y_i)$ donde $x_i$ representa la longitud de la cadena creciente más larga de alumnos que termina con el alumno $i$ y $y_i$ representa la longitud de la cadena decreciente más larga de alumnos que termina con el alumno $i$ . Obsérvese que no hay dos alumnos que tengan el mismo par de valores: dado cualquier $j>k$ si estudiante $j$ es más alto que el alumno $k$ entonces $x_j>x_k$ y en caso contrario $y_j>y_k$ . Sólo hay 49 pares de números entre $(1,1)$ y $(7,7)$ por lo que entre 55 estudiantes debe haber uno con un valor u otro superior a 7. Esto representa la existencia de una cadena monótona que es 8 o más estudiantes como se desee.