el uso de puntos para crear líneas de

Question

Tom dio un total de $9$ caramelos, además de un número infinito de líneas y él necesita su lugar, de tal modo que de ello se sigue la siguiente condición:

1) cuando se conectan dos caramelos con una línea, debe haber tres caramelos en esa línea o no podemos colocarlo;

2) un caramelo puede ser en diferentes líneas

Mostrar el número máximo de líneas que puede ser creado siguiendo esta regla. Una imagen que se proporciona a continuación para tener 5 puntos: Este es un problema con la extensión de la KSEA 2018 grado 11 examen de matemáticas (finalizado el concurso de matemáticas, celebrada en 4/7) , y tuve que lidiar con esto. Primero de todo he comenzado con pequeños ejemplos:

$3$ candy- $1$ líneas

$4$ candy- $1$ línea

$5$ candy- $2$ líneas

$6$ candy- $4$ líneas

Aunque estoy bastante seguro acerca de estos ejemplos, estoy muy inestable para avanzar; no tengo un método sistemático. Una de mis ideas es argumentar por la combinatoria; para cada línea generada, habrá un total de $3 \choose 2$ formas de conectar dos caramelos quitado. Entonces traté de esto para desmentir que el 5 caramelos puede generar de 3 líneas; pero $5 \choose 2$- 3$3 \choose 2$ no es negativo que muestra mi camino no funciona... no puedo realmente llegar a una solución adecuada para esto. Alguna sugerencia será muy apreciada.

Answer 1

El número máximo de líneas $\mathcal{N}$$10$.

Este número $10$ se logra mediante la siguiente configuración:

Esta límites $\mathcal{N}$, desde abajo, por $10$.

Para un límite superior, vamos a $S \subset \mathbb{R}^2$ ser cualquier conjunto de $n \ge 3$ puntos en el plano y $L$ ser el conjunto de líneas que contengan al menos 2 puntos de $S$.

Fuera de estos $n$ de los puntos, podemos formulario de $\frac12 n(n-1)$ pares de ellos. Para cualquier línea en $L$, si contiene $m$ puntos de $S$, contendrá $\frac12 m(m-1)$ pares. Aviso un par exclusiva de determinar una línea, esto significa que el conjunto de pares asociados con diferentes líneas en $L$ son disjuntas. Si dejamos $N_m$ el número de líneas que contienen $m$ puntos de $S$, tenemos:

$$\frac{n(n-1)}{2} = \sum_{m \ge 2} N_m \frac{m(m-1)}{2}\tag{*1}$$

Esto lleva a $\quad\displaystyle\frac{n(n-1)}{2} \ge N_2 + 3 N_{\ge 3}\quad$ donde $\quad N_{\ge 3} \stackrel{def}{=} \sum\limits_{m\ge 3} N_m$.
En $1958$, Kelly y Moser ha mostrado$\color{blue}{{}^{[1]}}$:

Si $S$ no radica en una sola línea, a continuación,$N_2 \ge \frac{3n}{7}$.

Para el problema en cuestión, tenemos $n = 9$. Resultado anterior implica

$$N_{\ge 3} \le \frac13 \left(\frac{9(9-1)}{2} - \frac{3(9)}{7}\right) = \frac{75}{7}$$ Desde LHS es un número entero, nos encontramos con $N_{\ge 3} \le 10$ si $S$ se encuentra en una sola línea. Si $S$ se encuentra en una sola línea, es claro $N_{\ge 3} = 1$. Combinar estos, podemos concluir de cualquier conjunto $S$ $9$ de los puntos, podemos construir en la mayoría de los $10$ líneas que pasan a través de $3$ o más puntos de $S$.

Esto establece el límite superior $\mathcal{N} \le 10$. Se combinan con el límite inferior, llegamos a la conclusión de $\mathcal{N} = 10$.

Aquí el problema está relacionado con el huerto de plantación problema que se pregunta cómo plantar $n$ de los árboles para que no ser $r(n,k)$ filas rectas con k árboles en cada fila. La variante de encontrar el máximo número de $3$líneas de punto para $n$ puntos es debido a Sylvester. Mira Borwein y Moser encuesta del artículo$\color{blue}{{}^{[2]}}$ para obtener más información acerca de la Sylvester problema. En particular, se tiene una prueba de la Kelly y Moser resultado del mencionado anteriormente.

---

Notas/Referencias

• $\color{blue}{[1]}$ - Kelly, L. M. y Moser, W. 1958. En el número de ordinario líneas determinada por $n$ puntos. Canadá. J. Math. 10, 210-219. MR: 20, #3494.

• $\color{blue}{[2]}$ - Borwein, P & O. J. Moser, W. (1990). Una encuesta de Sylvester problema y sus generalizaciones. Aequationes Mathematicae. 40. 111-135. 10.1007/BF02112289.

Answer 2

Límite inferior de al menos 9, como se ve aquí.

Answer 3

No creo que este es un problema fácil. Puede el autor tal vez publicar o enlazar directamente a la pregunta que inspiró desde el KSEA 2018 examen? Me echó un rápido vistazo al ejemplo de los problemas de ese examen, pero no lo encontramos.

Algunos del pensamiento sobre el problema con 9 caramelos:

1) Si utiliza un $3 \times 3$ patrón de red, usted puede encontrar de 8 líneas con 3 caramelos, así que el número de líneas que se pueden colocar es de al menos 8.

2) Se puede colocar en la mayoría de las 12 líneas. Uno puede ver esto de la siguiente manera: Cada uno de los dulces puede ser parte de más de 4 líneas, debido a que cada línea debe contener 2 otros dulces, pero los 'dulces' nunca puede ser el mismo entre las diferentes líneas (si fuera así, las líneas deben ser idénticos, como 2 diferentes puntos determinan una línea). Eso significaría que en la mayoría de las $4\times 9 = 36$ líneas, pero como cada línea se tienen en cuenta al menos tres veces de esta manera (a menos de 3 caramelos), esto se reduce a un máximo de 12 líneas.