Problema de sense tres en llínea

Archiu:No-three-in-line.svg

Un conjunt de 20 punts en una cuadrícula de 10 × 10, disposts de manera que no hi haja tres punts sobre la mateixa llínea recta de la cuadrícula

El problema de sense tres en llínea en geometria discreta planteja la qüestió de quants punts es poden colocar en una cuadrícula de $n\times n$ per a que no hi haja tres punts en la mateixa llínea recta. Este número està llimitat a $2n$ com a màxim, perque $2n+1$ punts situats sobre els elements d'una cuadrícula inclourien necessàriament una fila en tres o més punts, pel conegut principi del colomer. El problema va ser introduït per Henry Dudeney en 1900. Brass, Moser i Pach ho varen denominar "una de les qüestions geomètriques més antigues i més estudiades de punts colocats sobre una ret".

Encara que el problema s'ha pogut resoldre en $2n$ punts per cada $n$ fins a a lo manco $46$, es conjectura que es poden colocar menys de $2n$ punts en cuadrículas de gran tamany. Els métodos coneguts poden colocar linealmente molts punts en cuadrículas de tamany arbitrari, pero el millor d'estos métodos coloca una miqueta menys de $3n/2$ punts, pero no $2n$.

Encara que el seu orige procedix de la matemàtica recreativa, el problema té aplicacions en dibuix de grafos i en el problema del triàngul de Heilbronn.

Primer plantejament

El problema va ser plantejat per primera volta per Henry Dudeney en 1900, com un rompecabezas de matemàtiques recreatives, expressat en térmens de colocar els 16 peons d'un jugue d'escacs en el tauler de modo que no hi haja tres en una mateixa llínea recta. Est és exactament el problema de sense tres en llínea, per a el cas de $n=8$.. En una versió posterior del rompecabezas, Dudeney va modificar el problema, fent que la seua solució fòra única, en demanar una solució en la que dos dels peons estigueren en les caselles d4 i i5, atacant-se uns a uns atres en el centre del tauler.

Molts autors han publicat solucions a este problema per a valors menuts de $n$, i en 1998 se sabia que $2n$ punts podien colocar-se en una cuadrícula de $n\times n$ sense deixar tres en llínea recta para tot $n$ de fins a a lo manco 46, i per a alguns valors majors. El número de solucions (sense contar reflexions i rotacions com a distintes) per a valors menuts de $n$, començant en des de $n=2$, són

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... Plantilla:OEIS

Llímits superior i inferior

No es coneix el número exacte de punts que es poden colocar, com a funció de $n$,. No obstant, tant els llímits provats com els conjeturados acoten este número dins d'un ranc proporcional a $n$.

Métodos generals de colocació

Archiu:Erdős-no-3-in-line-12x12.svg

Colocació subóptima de $11$ punts en una cuadrícula de $12\times 12$, utilisant el método de Erdős. El cosí més gran $p$ menor que el tamany de la cuadrícula és $p=11$; la solució coloca els punts en les coordenades $(i,i^2$ mod $p)$ per a $i=0,1,\dots p-1$. Per eixemple, s'inclou $(4,5)$ perque $4^2=16\cong 5$ (${\displaystyle }$mod $11$)

Una solució ideada per Paul Erdős, publicada per Roth (1951), es basa en l'observació de que quan $n$ és un número primo, el conjunt de punts de la cuadrícula de costat $n$ $(i,i^2$ mod $n)$, per a $0\le i<n$, no conté tres punts colineales. Quan $n$ no és primer, es pot realisar esta construcció per a una cuadrícula $p\times p$ continguda en la cuadrícula $n\times n$, a on $p$ és el cosí més gran que està contingut en $n$. Degut a que la diferència entre dos número primo consecutius és molt més chicoteta que els propis cosins, $p$ sempre estarà prop de $n$, per lo que este método es pot utilisar per a colocar $n-o(n)$ punts en la cuadrícula $n\times n$ sense tres punts colineales.

El llímit de Erdős s'ha millorat posteriorment:Hall et al. (1975) va demostrar que, quan $n/2$ és primer, es pot obtindre una solució en $3(n-2)/2$ punts, colocant punts en còpies múltiples de la hipérbola $xy=k$ (mod $n/2$), a on $k$ pot elegir-se arbitrariamente sempre que siga distint de zero mod $n/2$. De nou, per a $n$ arbitrari es pot realisar esta construcció per a un número primo pròxim a $n/2$ per a obtindre una solució en $\frac{3}{2}n-o(n)$ punts.

Llímit superior

Com a màxim, els $2n$ punts poden colocar-se en una cuadrícula de tamany $n$. Si es coloquen més punts, llavors, segons el principi del colomer, a lo manco tres d'ells estarien en la mateixa llínea horisontal de la cuadrícula. Per a $n\le 46$, se sap que este llímit trivial és correcte.

Llímits conjeturados

Encara que es poden colocar exactament $2n$ punts en cuadrículas menudes,Guy y Kelly (1968) conjeturó que per a cuadrículas grans, existix un llímit superior significativament menor en la cantitat de punts que es poden colocar. Més precisament, conjeturaron que el número de punts que es poden colocar és com a màxim una cantitat sublineal major de $cn$, sent

$$c=\sqrt[3]{\frac{2{\pi }^2}{3}}\approx \mathrm{1.874.}$$

En acabant de que es va descobrir un error en el raonament heurístic que va conduir a esta conjectura, Guy va corregir l'error i va fer la conjectura més forta de que no es pot fer més que sublinealmente millor que $cn$ en.

$$c=\frac{\pi }{\sqrt{3}}\approx \mathrm{1.814.}$$

Bibliografia

Solució , p. 222. Publicat originalment en el Tribune de Londres, el 7 de novembre de 1906.

• «Simple Set Game Proof Stuns Mathematicians».