Don't take life too seriously: it's just a temporary situation

Corridore solitario (congettura del)

Algebra  Congetture 

La congettura proposta da J.M. Wills nel 1967 e appropriatamente chiamata “congettura del corridore solitario” da L. Goddyn nel 1998, afferma che data una pista circolare di lunghezza unitaria, se n corridori iniziano dallo stesso punto e corrono nello stesso senso a velocità diverse, prima o poi ciascuno di essi si troverà a essere solitario, ossia a distanza almeno 1 / n dagli altri.

 

In termini algebrici la congettura può essere formulata così: dati n numeri reali x1, x2, … xn, per ogni m tra 1 e n esiste un valore di k tale che per ogni r tra 1 e n diverso da m ||k * (x(m) – x(r))|| ≥ 1 / n, dove ||x|| indica il valore assoluto della differenza dall’intero più vicino a x.

 

Willis dimostrò che per dimostrare la congettura basta considerare velocità razionali o addirittura intere.

 

Per n fino a 3 è banale dimostrare che la congettura è vera e che se le velocità sono intere, ogni corridore si trova ad essere solitario entro il primo giro del più lento. La congettura è stata dimostrata vera solo per pochi valori superiori di n, come mostra la tabella seguente.

n

Autori della dimostrazione e anno

1

Banale

2

Banale

3

Banale

4

U. Betke e J.M. Will, 1972

5

Thomas W. Cusick e Carl Pomerance, 1984

6

T. Bohman, R. Holzman.e D. Kleitman, 2001

7

J. Barajas e O. Serra, 2008

 

E’ noto che la distanza minima 1 / n non può essere aumentata.

Alcuni progressi sono stati fatti nella direzione di trovare una distanza minima dagli altri per il corridore solitario:

  • è semplice dimostrare che ogni corridore si troverà prima o poi a distanza almeno uguale a 1 / (2 * n – 2) dagli altri;

  • nel 1994 Chen dimostrò che la distanza minima è almeno 1 / (2 * n – 3 + 1 / (2 * n – 5));

  • Chen e Thomas W. Cusick nel 1999 portarono il limite a 1 / (2 * n – 5), per 2n – 5 primo;

  • nel 2017 Terence Tao aumentò la distanza minima a 1 / (2 * n – 2) + c * log(n) / (n * log(log(n)))^2, per una costante c.

 

Ram Krishna Pandey dimostrò nel 2009 che la congettura vale se le velocità sono interi in progressione aritmetica.

 

Arturas Dubickas dimostrò nel 2011 che, ordinando i corridori in modo che le velocità siano crescenti, per n >16341 la congettura vale se il rapporto tra le velocità di due corridori consecutivi è almeno 1 + 33 * log(n) / n.

 

Nel 2012 Pat Devlin dimostrò che la congettura vale se le velocità sono numeri primi differenti.

 

Terence Tao dimostrò nel 2017 che la congettura vale se le velocità sono comprese tra 1 e 1.2n.

 

Nel 1971 Cusick dimostrò che la congettura può essere riformulata in termini di ostacoli. Supponiamo che un cacciatore si trovi nell’origine di un sistema di riferimento in uno spazio a n dimensioni, e che in ogni punto di tale spazio che abbia tutte le coordinate uguali a un intero più 1 / 2 sia il centro di un ostacolo ipercubico di spigolo 1 – 2 / n; se il cacciatore spara in una direzione non parallela a uno degli assi, colpisce un ostacolo.

In termini geometrici, una retta passante per l’origine e non parallela a uno degli assi, interseca uno degli ostacoli.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.