¿Cómo demuestro que un conjunto de segmentos de línea [matemática] n [/ matemática] puede tener intersecciones [matemática] \ Theta (n ^ 2) [/ matemática]?

Answer 1

Necesita un argumento que muestre que hay una forma en que las líneas se pueden organizar para que cada línea pueda intersectarse entre sí. Eso le dará [matemática] \ displaystyle \ binom {n} {2} = \ frac {n (n-1)} {2} [/ matemática] intersecciones en total. Como dos líneas pueden cruzarse en un punto como máximo, ese será el máximo.

Puede hacerlo si selecciona [matemática] n [/ matemática] puntos en un semicírculo y dibuja sus líneas tangentes. Como cada par de puntos se encuentra en un semicírculo, sus líneas tangentes se encontrarán. Además, se encuentran en pares, es decir, no hay tres líneas tangentes a un círculo que puedan cruzarse en un punto.

19 líneas con [matemática] \ binom {19} {2} = 171 [/ matemática] puntos de intersección

Answer 2

Estaba viendo el problema de probar que las líneas [math] n [/ math] pueden tener intersecciones [math] \ binom {n} {2} [/ math] y me encontré con esta elegante solución en Math StackExchange. Brevemente:

Considere una familia de líneas [matemáticas] L_ {k}: y = kx + k ^ {2} [/ matemáticas]

para [math] i \ neq j, L_ {i} \ text {y} L_ {j} [/ math] siempre se cruzan en el punto [matemáticas] P (i, j) = (- ij, – (i + j)) [/ matemáticas]

Dada la suma s y el producto p de dos números, están determinados únicamente por la ecuación cuadrática: [matemática] x ^ {2} -sx + p = 0 [/ matemática]. Esto significa [matemáticas] P (i, j) = P (k, l) [/ matemáticas] iff [matemáticas] \ {i, j \} = \ {k, l \} [/ matemáticas], es decir, las dos líneas son lo mismo.

Tomar n líneas únicas de esta familia dará lugar a exactamente [math] \ binom {n} {2} [/ math] puntos de intersección únicos.

Las líneas [matemáticas] L _ {- 2}, L _ {- 1}, L_ {0}, L_ {1}, L_ {2} [/ matemáticas] que se cruzan en 10 puntos diferentes.

Answer 3

Aunque esto podría no dar el número máximo de intersecciones posibles entre las líneas, me gusta esta solución porque es muy simple y elegante.

Organice n / 2 líneas horizontalmente y crúcelas todas con las otras n / 2 líneas verticalmente como una cuadrícula. Tiene n ^ 2/4 número de puntos de intersección que es suficiente para demostrar que es Theta (n ^ 2).

Answer 4

Establecemos un gráfico no dirigido [matemáticas] G = [/ matemáticas] usando las siguientes reglas:

(a) el vértice [matemática] v_i \ en V [/ matemática] se representa para la línea [matemática] i [/ matemática] para toda [matemática] i = 1,2, \ puntos, n [/ matemática]

(b) edge [math] e_ {ij} \ en E [/ math] si y solo si la línea [math] i [/ math] se cruza con la línea [math] j [/ math] para todos [math] i, j = 1,2, \ puntos, n [/ matemáticas]

Dado que dos líneas distintas tienen como máximo un punto de intersección, el gráfico [matemáticas] G [/ matemáticas] es único y el grado máximo de nodo es [matemáticas] n-1 [/ matemáticas] en el caso de que cada línea se cruce con el resto de [matemáticas ] n-1 [/ math] líneas.

Sea el número máximo de puntos de intersección de [math] n [/ math] líneas N, su límite superior es exactamente el número de bordes del gráfico [math] G [/ math] como está completamente conectado, que se calcula mediante:

[matemáticas] \ displaystyle {| E | = \ frac {n (n-1)} {2} = \ Theta (n ^ 2)} \ ge N \ qquad (1) [/ math]

Es fácil verificar que una configuración como una cuadrícula generada por [math] \ left [\ frac {n} {2} \ right] [/ math] líneas paralelas en dirección vertical y [math] \ left [\ frac { n} {2} \ right] [/ math] líneas paralelas en dirección horizontal tiene:

[math] \ displaystyle {\ left [\ frac {n} {2} \ right] ^ 2 = \ Theta (n ^ 2) \ le N \ qquad (2)} [/ math] puntos de intersección

De (1) y (2) tenemos la conclusión.