Ampliando la respuesta de Daniel Paleka, así es como probaría que el número más pequeño de tales aviones es [matemática] 3n [/ matemática]
Descargo de responsabilidad: probablemente esta no sea la mejor manera para que un concursante de la OMI resuelva este problema. ( Editar: probablemente lo sea)
Lema 1. Deje que [math] P [/ math] sea un polinomio en [math] \ mathbb {R} [x_1, \ ldots, x_n] [/ math] y deje [math] S_1 \ times \ cdots \ times S_n [ / math] ser una cuadrícula, [math] S_i \ subset \ mathbb {R} [/ math], de modo que [math] P [/ math] se desvanece en todos los puntos de la cuadrícula menos uno. Entonces [math] deg (P) \ geq \ sum_i (| S_i | – 1) [/ math].
La prueba requiere un buen resultado de Noga Alon llamado Combinatorial Nullstellensatz. Este no es un resultado particularmente profundo y, de hecho, cualquier persona con un conocimiento rudimentario de polinomios puede entender la prueba, pero tiene algunas aplicaciones de gran alcance (ver esto). Permítanme escribir ese resultado (Teorema 1.2 en el documento) sin prueba.
- Geometría: ¿Cuál es la intuición detrás de la fórmula para la circunferencia del círculo?
- Geometría: ¿Cuál es la intuición detrás de pi?
- Geometría: ¿Cuál es la intuición detrás del hecho de que el tercer lado de cualquier triángulo es menor que la suma y mayor que la diferencia de los otros dos lados?
- ¿Cuál es la intuición detrás del teorema de Pitágoras?
- ¿El espacio es euclidiano? Más específicamente, si dibujas un triángulo con lados perfectamente rectos, ¿la suma de todos los ángulos será de 180 grados?
Nullstellensatz de Alon. Sea [math] P [/ math] un polinomio en [math] F [x_1, \ ldots, x_n] [/ math], donde [math] F [/ math] es un campo arbitrario. Digamos que el grado de [matemáticas] P [/ matemáticas] es [matemáticas] d = \ sum_ {i = 1} ^ n t_i [/ matemáticas], donde [matemáticas] t_i [/ matemáticas] son algunos enteros no negativos y supongamos que el coeficiente de [math] x_1 ^ {t_1} \ cdots x_n ^ {t_n} [/ math] en [math] P [/ math] no es cero. Entonces, si [matemáticas] | S_i | > t_i [/ math] para todos [math] i [/ math] existen [math] s_i \ en S_i [/ math] tal que [math] P (s_1, \ ldots, s_n) \ neq 0 [/ math] .
Puede ser una buena idea jugar primero con ese teorema y ver qué significa realmente.
Ahora, así es como el Lema 1 se sigue de este teorema. Deje que [math] a = (a_1, \ ldots, a_n) [/ math] sea el punto en la cuadrícula donde [math] P [/ math] no se desvanece. Digamos, el grado de [matemáticas] P [/ matemáticas] es menor que [matemáticas] d = \ sum_i (| S_i | – 1) [/ matemáticas].
Tenga en cuenta que el polinomio [math] Q = \ prod_i \ prod_ {s \ in S_i \ setminus \ {a_i \}} (x_i – s) [/ math] es un polinomio de grado [math] d [/ math] que desaparece en todos los puntos de la cuadrícula excepto [matemáticas] a [/ matemáticas].
Sea [math] P (a) = \ lambda \ neq 0 [/ math] y [math] Q (a) = \ mu \ neq 0 [/ math].
Mire el polinomio [matemáticas] \ frac {1} {\ mu} Q – \ frac {1} {\ lambda} P [/ matemáticas]. Es un polinomio de grado [matemático] d [/ matemático] (dado que se supuso que el grado de [matemático] P [/ matemático] es menor que [matemático] d [/ matemático]) que desaparece completamente en la cuadrícula (incluido el punto [matemáticas] a [/ matemáticas]) y tiene el término distinto de cero [matemáticas] x_1 ^ {| S_1 | – 1} \ cdots x_n ^ {| S_n | – 1} [/ math] en él.
¡Esto contradice el nullstellensatz combinatorio!
Ahora, llegando al problema principal. Deje que [math] H_1, H_2, \ ldots, H_m [/ math] sean los [math] m [/ math] sean los planos que desaparecen en todos los puntos de la cuadrícula [math] \ {0, 1, \ ldots, n \} ^ 3 [/ math] pero el origen. Cualquier plano que no pase por el origen está determinado únicamente por una ecuación de la forma [matemática] a_1 x_1 + a_2 x_2 + a_3 x_3 = 1 [/ matemática].
Por lo tanto, tenemos los polinomios [math] P_i = u_i \ cdot x – 1 [/ math] que definen estos hiperplanos donde [math] u_i [/ math] son vectores distintos de cero en [math] \ mathbb {R} ^ 3 [/ matemáticas].
Ahora puede comprobar fácilmente que el polinomio [math] P = \ prod_i P_i [/ math] cumple las condiciones del Lema 1 con [math] S_i = \ {0, 1, \ ldots, n \} [/ math] para [ math] i = 1, 2, 3 [/ math] y por lo tanto tenemos [math] deg (P) \ geq 3n [/ math].
Pero a partir de la definición de [matemáticas] P [/ matemáticas] su grado es igual a [matemáticas] m [/ matemáticas], y hemos terminado.
Observación 1: Me parece que este problema está inspirado en el siguiente artículo de Alon y Füredi, Covering the Cube de Affine Hyperplanes, que de cierta manera generaliza los resultados de este artículo de Brouwer y Schrijver, El número de bloqueo de un afín espacio que utiliza una técnica polinómica muy similar. La prueba dada por Alon y Füredi en ese documento utiliza argumentos de dimensión en polinomios en lugar del nullstellensatz combinatorio que se puede tomar como otra solución a este problema (Teorema 2 de ese documento).
Observación 2: No existe una solución conocida para este problema que no utilice polinomios de alguna manera. Peter Scholze fue uno de los 5 concursantes que resolvió este problema por completo en 2007. Para su solución, puede ver la Solución 1 aquí.
Observación 3: Otra forma de probar el Lema 1 es usando el nullstellensatz combinatorio perforado por Ball y Serra. Ver Teorema 4.1 aquí.
Observación 4: Las investigaciones que comenzaron con esto y algunos problemas relacionados condujeron al siguiente trabajo mío conjunto con Pete Clark, Aditya Potukuchi y John Schmitt: [1508.06020] En ceros de un polinomio en una cuadrícula finita. Entonces, me gustaría agradecer al autor de esta pregunta.
