Antes de abordar la $N^2$ problema, vamos a dar una solución de la $4^2 = 16$ problema de los comensales, agrupándolos en cinco platos sentados en cuatro mesas de cuatro comensales cada una:
Primer plato:
X X X X O O O O O O O O O O O O
O O O O X X X X O O O O O O O O
O O O O O O O O X X X X O O O O
O O O O O O O O O O O O X X X X
Segundo plato:
X O O O O X O O O O X O O O O X
X O O O O X O O O O X O O O O X
X O O O O X O O O O X O O O O X
X O O O O X O O O O X O O O O X
Tercer curso:
X O O O O O X O O X O O O O O X
O X O O O O O X X O O O O O X O
O O O X O X O O O O X O X O O O
O O X O X O O O O O O X O X O O
Cuarto curso:
X O O O O O O X O X O O O O X O
O O X O O X O O O O O X X O O O
O X O O O O X O X O O O O O O X
O O O X X O O O O O X O O X O O
Quinto curso:
X O O O O X O O O O X O O O O X
O O O X O O X O O X O O X O O O
O O X O O O O X X O O O O X O O
O X O O X O O O O O O X O O X O
La disposición de $N^2$ comensales en $N$ tablas a través de $N+1$ platos de una comida equivale a lo que en geometría de incidencia se denomina un plano afín finito .
Un plano afín es un sistema de puntos y líneas tal que:
- Dos puntos distintos cualesquiera se encuentran sobre una única recta.
- Cada línea tiene al menos dos puntos.
- Dada una recta y un punto, existe un único en paralelo línea que contiene el punto.
- Existen tres puntos no lineales (puntos que no están todos en la misma línea).
NB: Por líneas paralelas entendemos líneas disjuntas o igual líneas.
Los comensales son nuestros puntos $N$ -conjuntos de comensales servidos en mesas separadas durante un plato son nuestras líneas paralelas: cada comensal está exactamente en una de las $N$ mesas durante un curso.
Si una recta de un plano afín contiene $n$ puntos, decimos que es un plano afín finito de orden $n$ . Pueden practicarse las siguientes deducciones:
- Todas las líneas contienen $n$ puntos.
- Cada punto está contenido en $n+1$ líneas.
- Existen $n^2$ puntos en total.
- Hay un total de $n^2 + n$ líneas en total.
En todos los ejemplos conocidos de planos afines finitos, $n$ es un primo o una potencia de primos. Un plano afín finito de orden $n$ existe si y sólo si un plano proyectivo finito de orden $n$ existe, y por tanto es equivalente a la existencia de $n-1$ cuadrados latinos mutuamente ortogonales de orden $n$ .
Un famoso problema abierto lo plantea la conjetura de que $n$ no es una primera potencia es imposible. Este Conjetura de la primera potencia sigue siendo un tema de investigación activa.
La inexistencia de dos cuadrados latinos ortogonales de orden 6 (Euler/Tarry; véase D. Stinson's Una breve prueba... para un tratamiento moderno de 4 páginas) implica que no existe ningún plano afín finito de ese orden, y Las extensas investigaciones informáticas de Lam demostró que no existe ningún plano afín finito de orden 10. Muchos resultados adicionales de no existencia ( $n=14,21,22,\ldots$ ) se muestran mediante Teorema de Bruck-Ryser-Chowla .
El caso abierto más pequeño es actualmente el pedido $n=12$ .
El álgebra lineal puede utilizarse para construir planos afines o planos proyectivos de campos finitos (necesariamente de orden de potencia primo), y los resultados se denominan Geometrías de Galois . Se sabe que hay planos afines que no son isomorfos a ninguno de ellos (pero hasta ahora sólo para órdenes de potencia primos).
Construcción: Sea un campo finito $\mathbb{F}_q$ donde $q=p^k$ tienen un orden de potencia primo. Partición del producto cartesiano $\mathbb{F}_q\times \mathbb{F}_q$ en $q+1$ familias de líneas paralelas que pasan por cada par de puntos distintos $(x_1,y_1),(x_2,y_2)$ . Cada línea tiene $q$ puntos, por lo que cada punto tendrá $q+1 = \frac{q^2-1}{q-1}$ líneas a través de él. Cualquier $q$ líneas paralelas deben cubrir el plano, y las $q+1$ Las clases de rectas paralelas se parametrizan por su "pendiente". $s=0,\ldots,q-1,\infty$ donde pendiente infinita significa líneas "verticales" (primera coordenada constante) y en caso contrario $s= \frac{y_2-y_1}{x_2-x_1}$ .
Construir el campo finito de orden $q=p^k$ puede hacerse como un anillo de cociente $\mathbb{Z}_p[X]/f(X)$ donde $f(X)\in \mathbb{Z}_p[X]$ es un polinomio irreducible de grado $k$ . Tuve ocasión de construir un campo finito de orden $5^3=125$ mediante este método en esta respuesta .
