nella disposizione a 8 punti, mi sembra che ci si possa "spingere" a 7,21

Si Delfo, anche 7,22...

Lo sai che non so fare i conti; e vado solo a occhio....

Eh, eh, anch'io prima ero andato ad occhio, ma poi con un programmino di calcolo ho trovato un centesimo e rotti in più di 7,21; anzi, allungando i decimali, sembrerebbe che il risultato, fatto trovare al pc per via empirica, sia $7,\overline {2}$.

Complimenti a tutti per i contributi dati, trovo anch'io interessante le simulazioni con la darwin machine,chissà se all'aumentare del numero dei punti,essa sia sempre in grado di riportare lo schema più efficiente,mi domando se ci siano disposizioni per così dire irregolari, che non presentino simmetrie, schemi che la logica farebbe fatica a scovare.

Del resto pure risulta interessante analizzare il variare degli schemi con il variare delle proporzioni del rettangolo, ad esempio per quali rettangoli 1xn lo schema trovato da Enrico e Pasquale risulta il migliore?

In effetti se il rettangolo degenera in un quadrato 1x1, la disposizione ottimale delle biglie risulta quello della figura qui riportata,ove la separazione massima dei minimi vale circa 0.5359 (sperando di non avere sbagliato!)

Si, dici bene: $4-2\sqrt{3}$

Faccio un passettino indietro considerando la disposizione di $n$ punti nel rettangolo $2\/\times\/1$.
Mi sembra abbastanza intuitivo che i punti debbano essere disposti con un certo grado di simmetria. In particolare, se osserviamo i punti scorrendo per esempio da destra a sinistra e dal basso all’alto notiamo che alcuni di essi sono adiacenti per fasce verticali e orizzontali: ebbene, questi punti “adiacenti” devono essere tra loro equidistanti; in qualche modo, la “densità” dei punti nel rettangolo deve essere costante. Infatti, una di tali distanze può essere più grande solo se un’altra è ad essa inferiore.
Ora, per numeri “piccoli” di punti la distanza minima è maggiore di $1$, le due metà del rettangolo devono contenere lo stesso numero di punti quindi, se i punti sono in numero dispari, uno di essi deve cadere sull’asse verticale del rettangolo stesso: la disposizione deve essere simmetrica rispetto a tale asse. Se i punti sono in numero pari, viceversa, la distribuzione deve avere una simmetria centrale.
I numeri “piccoli” sono da $1$ a $6$



Non è difficile calcolare le distanze minime: per esempio, per il meno ovvio ($5$ punti), basta osservare che i due angoli evidenziati devono essere uguali



e quindi di $15^{\circ }$ per cui $r\/=\/\sec 15^{\circ }\/=\/\sqrt{6}\/-\/\sqrt{2}\/=\/1,0352\ldots$
Le distanze sono

$\begin{array}{|c|c|C+25} \hline n & r_{\script n} \\ \hline 1 & \\ 2 & \sqrt{5} \\ 3 & \sqrt{2} \\ 4 & \sqrt{13}/3 \\ 5 & \sqrt{6}\/-\/\sqrt{2} \\ 6 & 1 \\ \hline \end{array}$

Il discorso si fa più complicato per $n\/ >\/ 6$ ($r\/ <\/ 1$). Supponiamo di modificare lo schema a sei punti per far spazio al settimo punto: spingiamo i punti verso sinistra e avviciniamo i punti sul lato sinistro del rettangolo per guadagnare qualcosa



Per calcolare $r$ ricorriamo a Pitagora: la proiezione del segmento in basso a sinistra sul lato lungo del rettangolo vale

$p_{\script 1}\left(r\right)\/=\/\sqrt{r^{\script 2}\/-\/\left(\frac{1-r}2\right)^{\script 2}}\/=\/\frac12\sqrt{3r^{\script 2}\/+\/2r\/-\/1}$

la proiezione del segmento in basso a destra sul lato lungo del rettangolo vale

$p_{\script 2}\left(r\right)\/=\/\sqrt{r^{\script 2}\/-\/\left(\frac 12\right)^{\script 2}}\/=\/\frac12\sqrt{4r^{\script 2}\/-\/1}$

Il valore cercato è una delle radici dell’equazione $p_{\script 1}\left(r\right)\/+\/r\/+\/p_{\script 2}\left(r\right)\/=\/2$: dopo “alcuni passaggi di facile algebra” otteniamo

$r\/=\/\frac{4\left(\sqrt{295}-10\right)}{39}\/=\/0,7359\ldots$

Riflettiamo un attimo! Deve essere $p_{\script 1}\left(r\right)\/\leq\/r$ per cui possiamo migliorare un poco con lo schema seguente



che ha equazione $2p_{\script 1}\left(r\right)\/+\/p_{\script 2}\left(r\right)\/=\/2$, la cui radice è $r\/=\/0,7392\dots$.
Ma non abbiamo riflettuto abbastanza, infatti $p_{\script 2}\left(r\right)\/\leq\/p_{\script 1}\left(r\right)$ e quest’ultimo schema (quello proposto da Delfo)



costituisce un ulteriore miglioramento: la sua equazione è $p_{\script 1}\left(r\right)\/+\/2p_{\script 2}\left(r\right)\/=\/2$, la cui radice è $r\/=\/0,7882\dots$
Un altro schema a $7$ punti può essere ottenuto se immaginiamo di spezzare lo schema a $6$ come se fosse un uovo, sostituendo con due punti il punto in basso al centro e allontanandoli fino ad ottenere un triangolo equilatero



Per calcolare $r$ osserviamo che tutti gli angoli sono di $30^{\circ }$, $60^{\circ }$ e $90^{\circ}$ e quindi $r\/=\/\sqrt{3}\/-\/1\/=\/0,7320\dots$, un valore inferiore a quelli di tutti gli schemi precedenti (nota bene che questo schema tassella il piano).



Passiamo ora allo schema con $8$ punti: partendo da una disposizione regolare per fasce verticali (nella quale la distanza minima è $2/3$) avviciniamo tra loro i quattro punti centrali



l’equazione di questo schema è $2p_{\script 1}\left(r\right)\/+\/r\/=\/2$, la cui radice è $r\/=\/\frac{\sqrt{19}-3}2\/=\/0,6794\dots$; primo miglioramento



di equazione $3p_{\script 1}\left(r\right)\/=\/2$, la cui radice è $r\/=\/\frac{2\sqrt{21}-3}9\/=\/0,6850\dots$; per il secondo miglioramento rovesciamo la disposizione dei punti superiori (ottenendo lo schema proposto da Gianfranco)



per il quale è necessario introdurre una nuova proiezione sul lato lungo: $p_{\script 3}\left(r\right)\/=\/\sqrt{r^{\script 2}-\left(1-r\right)^{\script 2}}\/=\/\sqrt{2r-1}$. L’equazione è $3p_{\script 3}\left(r\right)\/=\/2$, la cui radice è $r\/=\/\frac{13}{18}\/=\/0,7222\dots$.
La diagonale minore dei rombi



ha una lunghezza pari a $\sqrt{\left(2r\/-\/1\right)^{\script 2}\/+\/p_{\script 3}^{\script 2}\left(r\right)}\/=\/\sqrt{4r^{\script 2}\/-\/2r}$: dobbiamo verificare che sia non minore del lato

$\sqrt{4r^{\script 2}\/-\/2r}\/\geq\/r\qquad\Longrightarrow\qquad r\/\geq\/2/3$

c.v.d.
Lo schema con gli $8$ punti disposti su tre linee orizzontali



di equazione $4p_{\script 2}\left(r\right)\/=\/2$, la cui radice è $r\/=\/\frac{\sqrt{2}}2\/=\/0,7071\dots$, non è conveniente ma torna utile per introdurre uno schema a $9$ punti



di equazione è $5p_{\script 2}\left(r\right)\/=\/2$, la cui radice è $r\/=\/\frac{\sqrt{41}}{10}\/=\/0,6403\dots$; l’altro schema a cui riesco a pensare è derivato dallo schema a $7$ punti



ma esso è peggiore dato che la sua equazione è $2p_{\script 1}\left(r\right)\/+\/2p_{\script 2}\left(r\right)\/=\/2$, la cui radice è $r\/=\/0,6351\dots$
Ormai sappiamo cosa aspettarci dal caso con $10$ punti



equazione $p_{\script 1}\left(r\right)\/+\/4p_{\script 2}\left(r\right)\/=\/2$, radice $r\/=\/0,6129\dots$



equazione $6p_{\script 2}\left(r\right)\/=\/2$, radice $r\/=\/\sqrt{13}/6\/=\/0,6009\dots$
Lo schema a rombi, equazione $4p_{\script 3}\left(r\right)\/=\/2$,



ha dei rombi il cui lato vale $5/8\/<\/2/3$ e quindi la diagonale è più corta: $\sqrt{5}/4$. Troppo corta!
Gli schemi a $11$ punti



equazione $6p_{\script 2}\left(r\right)\/=\/2$, radice $r\/=\/\sqrt{13}/6\/=\/0,6009\dots$ (come il secondo schema a $10$)



equazione $p_{\script 1}\left(r\right)\/+\/5p_{\script 2}\left(r\right)\/=\/2$, radice $r\/=\/0,5790\dots$, ci fanno preoccupare per la distanza tra i punti sulla stessa linea orizzontale ma è infine con $12$ punti che ciò avviene



equazione $7p_{\script 2}\left(r\right)\/=\/2$, radice $r\/=\/\sqrt{65}/14\/=\/0,5758\dots$ e distanza orizzontale $4/7\/=\/0,5714\dots$. Ma, niente paura! Rimediamo subito



spaziando orizzontalmente tra loro i punti quel tanto che serve con una nuova proiezione (stavolta sul lato corto): $p_{\script 4}\left(r\right)\/=\/\sqrt{r^{\script 2}\/-\/\left(2\/-\/3r \right)^{\script 2}}$; equazione $2p_{\script 4}\left(r\right)\/=\/1$, radice $r\/=\/\left(6\/-\/\sqrt{2}\right)/8\/=\/0,5732\dots$ (siamo sicuri che le diagonali dei rombi sono più lunghe perché, spostando i punti orizzontalmente, abbiamo accorciato uno dei due tratti obliqui e allungato l’altro).
Credo che basti così (per ora)

Panurgo!

il tuo post è un vero e proprio articolo da rivista matematica.
Leggendolo mi sono persino commosso. Mi sono chiesto: ma io, assieme a tutti coloro che danno pochi contributi al Forum, sono degno di ricevere tanta grazia?

Ti ringrazio moltissimo, a nome di tutti, e prometto che cercherò di perfezionare una Macchina di Darwin per questo tipo di problema.
Appena possibile vi darò notizie.

Un problema imprtante, come ho già detto, è l'estrazione di numeri veramente casuali.
Forse si potrebbero estrarre da qualche fenomeno naturale come il rumore dell'acqua che scorre disordinatamente. Forse con un microfono o un altro tipo di sensore collegato al computer...

Ciao
Gianfranco

40 anni fa, forse di più, avevo un libro che definire incredibile è limitato.
Era pubblicato dalla Ciba, multinazionale chimica; e riportava in centinaia e centinaia di pagine "tutte" le misure e i dati e le formule di cui potrebbe aver bisogno, e moltissime di cui nessuno avrà mai avuto bisogno. dalle statistiche di peso e altezza dei bambini del madagascar, alla composizione dello sperma di cammello (letterale!), dai valori medi di glicemia dei pellerossa del Nevada, alle percentuali di votanti alle elezioni in Uganda....
E c'erano una decina di pagine *beep* *beep* di "numeri casuali" , allineati in gruppi di cinque file, divisi in gruppi di cinque colonne.
Ricordo che, non fidandomi della "casualità", sottoposi alcune pagine ad alcuni test inventati da me (quanto tempo avevo da perdere!!).
Dopo aver calcolato le presenze delle 10 cifre tra le prime mille; registrando la variabilità per gruppi di 100. ripetei poi il calcolo su altri mille cifre, prendendo però una riga sì e una no; poi aolo la prima di ogni gruppetto di 5x5; e in tanti altri modi "alternativi". Ne ottenni una serie di dati che mi convinsero che si trattava di numeri "buoni"
Peccato non aver conservato libro e calcoli!

Ho provato a implementare una rozza “darwin machine” in R: partendo da $n$ punti ne genero altri $n$ a loro vicini (la distanza varia casualmente in modo esponenziale, i valori più grandi meno probabili); a questo punto li considero fratelli e calcolo quale set di punti (un fratello di ogni coppia) mi dà la distanza minima maggiore; i fratelli che nascono fuori dal rettangolo vengono riflessi all’interno.
La principale difficoltà sta nel fatto che il calcolo della distanza minima tra $n$ punti è un processo che va con $n^{\script 2}$ e vi sono $2^{\script n}$ possibili set: un algoritmo esponenziale diventa molto lento già per valori di $n$ modesti.
L’ho fatto girare un po’ ed ho osservato che: a) le distanze tra punti “adiacenti” tendono a divenire uguali cosicchè si formano delle simmetrie “locali”; b) una volta raggiunto un massimo locale diventa difficile passare ad altra configurazione.
Per esempio, con $n\/=\/5$, oltre allo schema massimo,



ho trovato due massimi relativi:



con $r\/=\/1,0075\ldots$ e



con $r\/=\/\frac{10-4\sqrt{3}}3\/=\/1,0239\ldots$.
Vi prego di notare che questo schema ha solo simmetrie locali e non ha alcuna delle simmetrie del rettangolo.
Caro Gianfranco, com’è fatto l’algoritmo che usi tu? Se me lo spieghi proverò a scriverlo con R: si tratta di un pacchetto statistico che produce ottimi numeri “casuali” e che consente la manipolazione di quantità di dati piuttosto elevate...

Pan, quando approfondisci non ci sono paragoni.

Riporto di seguito un esempio di Machine condizionata, che ho utilizzato su 5 punti.
Nella routine ho imposto risultati con max 4 cifre decimali, per una migliore visibilità; inoltre ho imposto un punto ed il suo simmetrico per risparmiare tempo (dopo un po' di studio ci si accorge che le simmetrie vengono fuori); infine ho imposto la stampa di risultati che superino il valore di 0,9 come massimo cercato (comunque è un esempio).
La routine è scritta in Decimal con tutti i limiti del random, la velocità di esecuzione, ecc.
Il programma lavora sempre e lo si stoppa quando si vuole, se si ritiene, oppure lo si rilancia più volte, se si intoppa su un risultato.
Una volta trovato un disegno convincente, si può impostare una nuova Machine, o lavorare a mano.
La routine individua punti a caso e la distanza minore nell'ambito di ogni disegno che si determina; quindi confronta il risultato con i precedenti e memorizza quello più alto, lo stampa e stampa i punti che lo hanno determinato (ascissa e ordinata di ogni punto sono contigui)


DIM x(5)
DIM y(5)
DIM v(5)
DIM w(5)
DIM z(10)
LET mas=0.9
RANDOMIZE
LET x(1)=0
LET y(1)=0
LET x(2)=2
LET y(2)=0
DO
FOR m=3 TO 5
LET x(m)=INT(RND*20000)/10000
LET y(m)=INT(RND*10000)/10000
NEXT M
LET cont=0
FOR m=1 TO 4
FOR n=m+1 TO 5
LET cont=cont+1
LET z(cont)=SQR((x(m)-x(n))^2+(y(m)-y(n))^2)
NEXT N
NEXT M
LET mi=z(1)
FOR m=2 TO 10
IF z(m)<mi THEN LET mi=z(m)
NEXT M
IF mi>mas THEN
LET mas=mi
PRINT mas
FOR m=1 TO 5
LET v(m)=x(m)
LET w(m)=y(m)
PRINT v(m);w(m);" ";
NEXT M
PRINT
PRINT
END IF
LOOP
END

Tutto molto bello

Grazie, Guido, anche per la segnalazione di R

Pasquale, a proposito di Decimal BASIC, ti ho scritto un mp da qualche giorno,
riesci mica a dargli un'occhiata? Grazie

Un abbraccio a tutti!

Un'analisi veramente dettagliata e scrupolosa, davvero complimenti Guido, ho fatto pure io un pò di prove su qualche disposizione,trovando qualche singolarità curiosa, riprendendo ad esempio le disposizioni per i 9 punti,riproponendo quello che hai scritto,relativamente allo schema più efficente ove la disposizione a rombi batte quella bipentagonale 0.64 a 0.635, le 2 misure sono pericolosamente vicine,tanto che per un rettangolo 2.097x1 esse sono performanti in maniera uguale, portando la misura minima a 0.6526 per entrambe, questo rettangolo dunque rappresenta una singolarità notevole, presentando 2 formazioni differenti geometricamente ma con la stessa efficacia risolutiva.
Per un rettangolo 2.1x1 la struttura bipentagonale passa già in vantaggio 0.6532 contro 0.6530 (circa)
La ricerca di rettangoli singolari potrebbe essere un altro campo d'indagine interessante,non è facile capire quale sia lo schema più adatto ogni volta, potrebbe esserci qualche misteriosa relazione fra le strutture di minima separazione e le proporzioni del rettangolo?
Nel frattempo grazie a tutti per i notevoli contributi diramati.

Bye David

Giocando un po’ con la “darwin machine” si evidenziano alcune cose interessanti. Come il fatto che effettivamente le distanze tendono a diventare uguali: ciò è dovuto al fatto che i miei mutanti sopravvivono solo se la distanza minima aumenta, cioè se la mutazione è positiva (con una mutazione neutra la distanza minima non diminuisce). L’effetto che si ottiene è che la distanza minima aumenta ad ogni mutazione mentre le altre distanza possono sia aumentare sia diminuire; non è difficile capire come questo porti le varie distanze (tra punti “adiacenti”) a diventare sempre più simili. E se le distanze sono uguali vi possono essere parecchi schemi “abbastanza buoni” (massimi relativi) dai quali l’evoluzione, che notoriamente non tende al miglioramento, non si discosta. Come, per esempio, questo schema a sette punti


con $r\/=\/\frac{4\left(4+\sqrt{3}-\sqrt{13+8\sqrt{3}}\right)}3\/=\/0,7329\ldots$ che ho appena trovato (il valore migliore per sette punti è $0,7882$)

P.S.: per amor di precisione il tuo rettangolo equivalente ha le proporzioni $\frac56\sqrt{\frac12+\sqrt{34}}\/\times\/1\/=\/2,0967\ldots\/\times\/1$ con $r\/=\/\frac{2+\sqrt{34}}{12}\/=\/0,6525\ldots$

Ciao a tutti,
questa discussione, partita da un ambito di geometria combinatoria sta trasferendosi nell'informatica: forse è giusto così.
Ho lavorato un po' alla mia Macchina di Darwin (MD) e vi comunico alcune riflessioni, oltre a postare il programma.
All'inizio la MD era simile a quella di (bravo!) Pasquale.
Ma era troppo lenta.
Per accelerarla, dovevo ridurre A MANO (cambiando il programma e le variabili) gli intervalli di variabilità dei punti.
Ho cercato di automatizzare questo processo, senza per altro rendere più intelligente la macchina.
Praticamente, la nuova MD, ogni tot miglioramenti del sistema, riduce di un certo fattore l'area del piano in cui può stare ogni singolo punto.
L'evoluzione è così notevolmente accelerata.
L'output grafico mostra, oltre ai punti trovati in un certo istante, anche i loro intervalli (dx,dy) di possibili posizioni per il futuro.

Attenzione: ho scoperto che è meglio lasciar sconfinare detti intervalli anche fuori del rettangolo, salvo poi portare sui lati i punti che cadono fuori.
Un'altra analogia con il programma di Panurgo e che il programma si può incanalare verso una configurazione buona ma non ottima senza poter tornare più indietro.

Panurgo: intuitivamente la tua MD mi piace, ma... potresti spiegare meglio il discorso dei fratelli?

Panurgo ha scritto:...il calcolo della distanza minima tra n punti è un processo che va con n^2 e vi sono 2^n possibili set...

a) lo so che la differenza è poca ma mi sembra che il calcolo della distanza minima tra n punti varia con n(n-1)/2 e inoltre, quando hai un record (minimo) già stabilito, puoi uscire dal ciclo appena trovi un valore al di sopra di tale record.
b) non ho capito da dove vengono i 2^n set.

David apre ulteriori prospettive proponendo di vedere che cosa succede quando si cambiano i lati del rettangolo...

Gianfranco

5 agosto 2011 - Attenzione: Programma cancellato perché sostituito con un altro migliore nel prossimo post!