Una función de teoría de números para caracterizar subconjuntos libres de punto medio

Question

Recientemente, estuve repasando un curioso trabajo de matemáticas recreativas titulado "On the Diagonal Queens Domination Problem". El resultado principal del trabajo es establecer el valor mínimo $diag(n)$ del número de reinas necesarias para mantenerse en la diagonal de un $n \times n$ tablero de ajedrez para que ataquen todas las casillas del tablero.

Los autores hacen uso de algún lema ingenioso y hacen una observación que $diag(n) = n + 1 - r_3(\lceil \frac{n}{2} \rceil)$ . Aquí, $r_3(.)$ denota el valor mínimo $k$ de manera que cualquier $k$ -subconjunto de elementos de $[n]$ contiene un $k$ término de progresión aritmética (a la declaración del teorema de Roth). Para demostrar este enunciado, los autores hacen uso de un enunciado de la teoría de los números que no demuestran. Yo tampoco puedo demostrarlo por mí mismo debido a mi limitada formación en teoría de números (y quizás porque soy denso). El enunciado dice lo siguiente

Una colección de $k$ números pares o $k$ Los números Impares (los números de la colección tienen la misma paridad, esto mantendrá su suma par) es el subconjunto de suma par sin punto medio de $[n]$ $\mathit{if\ and\ only\ if}$ toda la mitad de los números de la colección (redondeados hacia abajo si no son enteros) es un subconjunto sin punto medio de $\lceil \frac{n}{2} \rceil$ .

Algunas definiciones para aclarar la cuestión. Un subconjunto $X$ de $[n]$ es libre de punto medio si para dos elementos cualesquiera $i,j \in X$ $(i+j)/2 \not\in X$ . Un subconjunto es de suma par si $i+j$ es incluso para cualquier $2$ elementos $i,j \in X$ .

Espero que la pregunta esté clara. En caso de que no lo sea, le pido disculpas y le ruego que me haga saber lo que no está claro.

Answer 1

No sé si he entendido bien el problema, ya que parte de la información parece extraña y creo que hay un error, así que primero reformularé la pregunta antes de responderla. Por favor, indíqueme si lo he entendido mal.

En lugar de "subconjunto sin punto medio de $\lceil \frac{n}{2} \rceil$ ", creo que querías decir "subconjunto sin punto medio de $[\lfloor \frac{n}{2} \rfloor]$ ". En primer lugar, faltaban los paréntesis para convertir el número en un conjunto, pero lo más importante es que necesitamos el suelo y no el techo, ya que de lo contrario el teorema fallaría simplemente porque el conjunto de mitades podría contener $\lceil \frac{n}{2} \rceil$ y esto evitaría que el conjunto original fuera un subconjunto de $[n]$ .

Con esto fuera del camino, parece que ni $k$ ni $n$ ni $[n]$ son realmente relevantes para el problema, por lo que abandonaré todas las referencias a ellos. Además, la propiedad "suma par" está garantizada por la colección que contiene o bien sólo números pares o bien sólo números Impares, por lo que es un poco confuso afirmarlo como parte de la equivalencia a demostrar.

Con estas aclaraciones, yo replantearía el teorema como sigue:

Un conjunto $S$ que contiene sólo números pares o sólo números Impares es libre de punto medio si el conjunto $H$ de todas las mitades de sus elementos (redondeado hacia abajo si no es entero) no tiene punto medio.

Esto parece ser una propiedad puramente "local" que se puede demostrar con sólo mirar cada par de números individualmente:

En primer lugar, dejemos que los números de $S$ sea par, y tome dos números $2m$ y $2n$ . Entonces las mitades de estos números son $m$ y $n$ respectivamente, y $(2m + 2n) / 2 = m + n$ por lo que el teorema queda demostrado si podemos demostrar que $m + n \notin S \Leftrightarrow (m + n) / 2 \notin H$ . Ahora bien, si $m + n$ es impar, esto es vacuo ya que el número impar $m + n$ no puede estar en el conjunto $S$ de los números pares y los no enteros $(m + n) / 2$ no puede estar en el conjunto $H$ de números enteros. Si $m + n$ es par, el " $\Leftarrow$ "es obvio, y la dirección " $\Rightarrow$ " se deduce porque "S" sólo contiene números enteros pares, por lo que el otro número de los que $(m + n)/2$ es una mitad (redondeada), $m + n + 1$ no está en $S$ o bien. Esto demuestra el teorema para $S$ que contiene sólo números pares.

Ahora dejemos que los números de $S$ sea impar, y tome dos números $2m+1$ y $2n+1$ . Entonces las mitades de estos números, redondeadas hacia abajo, son $m$ y $n$ respectivamente, y $(2m+1 + 2n+1) / 2 = m + n + 1$ por lo que el teorema queda demostrado si podemos demostrar que $m + n + 1\notin S \Leftrightarrow (m + n) / 2 \notin H$ . De nuevo, si $m + n$ es impar, esto es vacuamente cierto ya que el número par $m + n + 1$ no puede estar en el conjunto $S$ de los números Impares y los no enteros $(m + n) / 2$ no puede estar en el conjunto $H$ de números enteros. Si $m + n$ es par, el " $\Leftarrow$ " es de nuevo evidente, y la dirección " $\Rightarrow$ " se deduce porque "S" sólo contiene enteros Impares, por lo que el otro número de los que $(m + n)/2$ es una mitad (redondeada), $m + n$ no está en $S$ o bien. Esto demuestra el teorema para $S$ que sólo contiene números Impares.