Solución parcial. . .
Haré el caso $R(3,n)$ .
Reclamación: $R(3,n) = 3 + n$ para todos $n \ge 3$ .
Para simplificar la discusión, en lugar de celdas con puntos rojos u "otros" puntos, utilizaremos celdas que contengan un punto o que estén vacías.
Primero mostramos $R(3,n) \le 3 + n$ para todos $n \ge 3$ .
En primer lugar, consideremos el caso $n = 3$ .
Supongamos que $R(3,3) > 6$ .
Así, supongamos que tenemos un rectángulo libre $3\,{\times}\,3$ matriz que contiene al menos $7$ puntos. Como sólo tenemos $3$ filas, alguna fila debe tener más de dos puntos, por lo tanto debe tener $3$ puntos (es decir, está "totalmente lleno"). Si cualquiera de las otras filas contiene al menos dos puntos, esos dos puntos junto con los correspondientes puntos de la fila totalmente llena darían lugar a un rectángulo. Por lo tanto, las dos filas que no están llenas deben tener como máximo un punto cada una. Pero entonces el número total de puntos es como máximo $5$ contradicción.
De ello se desprende que $R(3,3) \le 6$ .
A continuación, consideremos el caso $n = 4$ .
Supongamos que $R(3,4) > 7$ .
Así, supongamos que tenemos un rectángulo libre $3\,{\times}\,4$ matriz que contiene al menos $8$ puntos.
Obsérvese que si una matriz con puntos es libre de rectángulos, sigue siendo libre de rectángulos si alguna de las filas está permutada, o si alguna de las columnas está permutada.
Como sólo tenemos $3$ filas, alguna fila debe tener más de dos puntos, por lo que debe tener al menos $3$ puntos. Mediante una permutación adecuada de las filas y columnas, podemos suponer que la primera fila tiene $3$ puntos en su primera $3$ células (de izquierda a derecha). El $6$ celdas por debajo de las $3$ los puntos pueden tener como máximo un punto en cada fila, por lo que deben tener un punto en cada fila, de lo contrario no se puede alcanzar $8$ . Pero entonces la columna más a la derecha debe tener $3$ puntos, lo que da lugar a dos rectángulos, contradicción.
De ello se desprende que $R(3,4) \le 7$ .
Proceder por inducción en $n$ . . .
Así, supongamos que $R(3,n) \le 3 + n$ para algunos $n \ge 4$ .
Nuestro objetivo es mostrar $R(3,n+1) \le 3 + (n + 1) = 4 + n$ .
Supongamos que $A$ es un $3\,{\times}\,(n+1)$ matriz libre de rectángulos con $d$ puntos.
Si eliminamos cualquier columna de $A$ la nueva matriz es una $3\,{\times}\,n$ matriz libre de rectángulos, por lo tanto, por la hipótesis inductiva, contiene a lo sumo $3 + n$ puntos.
Hay $n + 1$ opciones para la columna eliminada, y en cada caso, la nueva matriz contiene como máximo $3 + n$ puntos. Si contamos el número total de puntos en todas estas nuevas matrices, el recuento es como máximo $(n + 1)(3 + n)$ . Pero para este total, cada uno de los puntos de la matriz original $A$ se cuenta exactamente $n$ veces, por lo tanto
$$d \le \frac{(n + 1)(3 + n)}{n} = \frac{3}{n} + 4 + n < 5 + n$$
Pero $d < 5 + n \implies d \le 4 + n$ .
De ello se desprende que $R(3,n+1) \le 4 + n$ , lo que completa la inducción.
Así, hemos demostrado $R(3,n) \le 3 + n$ para todos $n \ge 3$ .
A continuación mostramos $R(3,n) \ge 3 + n$ para todos $n \ge 3$ .
Basta con construir un $3\,{\times}\,n$ matriz con $3 + n$ puntos que no tienen rectángulos (es decir, para los que no hay $4$ puntos forman un rectángulo con lados horizontales o verticales).
Por lo tanto, considere el $3\,{\times}\,n$ matriz (las estrellas representan puntos)
$$ \begin{bmatrix} & *& *& *& \cdots& *\\ *& *& & & & \\ *& & *& & & \\ \end{bmatrix} $$
donde la primera fila tiene puntos en todas las columnas menos en la primera, y cada una de las otras dos filas contiene dos puntos, como se muestra.
Está claro que la matriz tiene $3 + n$ puntos, y está libre de rectángulos.
De ello se desprende que $R(3,n) \ge 3 + n$ para todos $n \ge 3$ .
Combinando los resultados, tenemos $R(3,n) = 3 + n$ para todos $n \ge 3$ como se iba a demostrar.
Notas:
- Utilizando un argumento mucho más sencillo, se puede demostrar $R(2,n) = 1 + n$ para todos $n \ge 2$ .
- Con argumentos similares a los utilizados para determinar $R(3,4)$ se puede demostrar que $R(4,4) = 9$ .
- Así, podría parecer razonable conjeturar que $R(m,n) = (2m - 3) + n$ para todos $n \ge m$ .
- Lamentablemente, según el enlace http://oeis.org/A072567 publicado por Matthew Conroy, está claro que la conjetura que propuse anteriormente es falsa. Además, parece probable que no haya ninguna expresión de forma cerrada para $R(m,n)$ se conoce actualmente.
