Regolo di Golomb
In matematica, un regolo di Golomb, chiamato così da Solomon W. Golomb che fu il primo a descriverlo, è un insieme di tacche poste a posizioni intere su un immaginario regolo, tale che non ci sia alcuna coppia di tacche poste alla stessa distanza. Il numero di tacche nel regolo è il suo ordine, mentre la massima distanza tra due delle sue tacche è la sua lunghezza. Traslazione e riflessione di un regolo di Golomb sono considerate banali: per convenzione, quindi, la tacca più a sinistra è posta a 0 e quella successiva è il minore dei due valori possibili.
Non è affatto richiesto che un regolo di Golomb possa misurare tutte le distanze da 1 alla sua lunghezza: nel caso che lo faccia, viene detto un regolo perfetto. È stato dimostrato che non può esistere un regolo di Golomb perfetto per cinque o più tacche. Un regolo di Golomb si dice ottimale se non esiste nessun regolo di Golomb dello stesso ordine e più corto. È facile creare un regolo di Golomb, ma trovare quelli ottimali è un compito computazionalmente complicato. Distributed.net ha completato la ricerca parallela di massa per i regoli ottimali di ordine 24[1], 25[2], 26[3] e 27[3], confermando i candidati sospetti. Distributed.net sta inoltre cercando, da febbraio 2014, il regolo ottimale di ordine 28.[4]
Un uso pratico dei regoli di Golomb è la progettazione di antenne radio in array di fase, come ad esempio i radiotelescopi. Presso le stazioni base dei cellulari, si possono spesso vedere antenne in una configurazione equivalente al regolo di Golomb [0,1,4,6].
Al momento non è nota la complessità di trovare regoli di Golomb ottimali di lunghezza arbitraria n, ma si pensa che sia un problema NP-difficile.[5]
Regoli di Golomb ottimali noti modifica
La tabella seguente mostra tutti i regoli di Golomb ottimali noti, escludendo quelli equivalenti a meno di riflessione. La tabella è completa fino all'ordine 27 compreso.
| ordine | lunghezza | tacche | data scoperta | scopritore |
|---|---|---|---|---|
| 1 | 0 | 0 | 1952[6] | Wallace Babcock |
| 2 | 1 | 0 1 | 1952[6] | Wallace Babcock |
| 3 | 3 | 0 1 3 | 1952[6] | Wallace Babcock |
| 4 | 6 | 0 1 4 6 | 1952[6] | Wallace Babcock |
| 5 | 11 | 0 1 4 9 11 0 2 7 8 11 |
1967?[7] | John P. Robinson e Arthur J. Bernstein |
| 6 | 17 | 0 1 4 10 12 17 0 1 4 10 15 17 0 1 8 11 13 17 0 1 8 12 14 17 |
1967?[7] | John P. Robinson e Arthur J. Bernstein |
| 7 | 25 | 0 1 4 10 18 23 25 0 1 7 11 20 23 25 0 1 11 16 19 23 25 0 2 3 10 16 21 25 0 2 7 13 21 22 25 |
1967?[7] | John P. Robinson e Arthur J. Bernstein |
| 8 | 34 | 0 1 4 9 15 22 32 34 | 1972[7] | William Mixon |
| 9 | 44 | 0 1 5 12 25 27 35 41 44 | 1972[7] | William Mixon |
| 10 | 55 | 0 1 6 10 23 26 34 41 53 55 | 1972[7] | William Mixon |
| 11 | 72 | 0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72 |
1972[7] | William Mixon |
| 12 | 85 | 0 2 6 24 29 40 43 55 68 75 76 85 | 1979[7] | John P. Robinson |
| 13 | 106 | 0 2 5 25 37 43 59 70 85 89 98 99 106 | 1981[7] | John P. Robinson |
| 14 | 127 | 0 4 6 20 35 52 59 77 78 86 89 99 122 127 | 1985[7] | James B. Shearer |
| 15 | 151 | 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151 | 1985[7] | James B. Shearer |
| 16 | 177 | 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177 | 1986[7] | James B. Shearer |
| 17 | 199 | 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199 | 1993[7] | W. Olin Sibert |
| 18 | 216 | 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216 | 1993[7] | W. Olin Sibert |
| 19 | 246 | 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246 | 1994[7] | Apostolos Dollas, William T. Rankin and David McCracken |
| 20 | 283 | 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283 | 1997?[7] | Mark Garry, David Vanderschel and others (web project) |
| 21 | 333 | 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333 | 8 maggio 1998[8] | Mark Garry, David Vanderschel and others (web project) |
| 22 | 356 | 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 | ~maggio 1999[9] | Mark Garry, David Vanderschel and others (web project) |
| 23 | 372 | 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372 | 8 luglio 1999[10] | Mark Garry, David Vanderschel and others (web project) |
| 24 | 425 | 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425 | 13 ottobre 2004[11] | distributed.net |
| 25 | 480 | 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480 | 25 ottobre 2008[12] | distributed.net |
| 26 | 492 | 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492 | 24 febbraio 2009[13] | distributed.net |
| 27 | 553 | 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 | 19 febbraio 2014[3][14] | distributed.net |
Note modifica
- ^ (EN) OGR-24 Overall project stats, su stats.distributed.net, distributed.net. URL consultato il 1º marzo 2014.
- ^ (EN) OGR-25 Overall project stats, su stats.distributed.net, distributed.net. URL consultato il 1º marzo 2014.
- ^ a b c (EN) OGR-26 Overall project stats, su stats.distributed.net, distributed.net. URL consultato il 1º marzo 2014.
- ^ (EN) Mike Reed, Getting ready for OGR-28!, su distributed.net, 18 febbraio 2014. URL consultato il 1º marzo 2014.
- ^ Modular and Regular Golomb Rulers
- ^ a b c d (EN) mathpuzzle.com, http://mathpuzzle.com/MAA/30-Rulers%20and%20Arrays/mathgames_11_15_04.html.
- ^ a b c d e f g h i j k l m n o p (EN) James B. Shearer, Golomb ruler table, su research.ibm.com, IBM. URL consultato il 26 febbraio 2014.
- ^ (EN) In Search Of The Optimal 20 & 21 Mark Golomb Rulers, su members.aol.com. URL consultato il 26 febbraio 2014 (archiviato dall'url originale il 6 dicembre 1998).
- ^ (EN) Help Find The Optimal 22 Mark Golomb Ruler!, su ogr.virtualave.net, 6 maggio 1999. URL consultato il 26 febbraio 2014 (archiviato dall'url originale il 24 maggio 2000).
- ^ (EN) Help Find The Optimal 23 Mark Golomb Ruler!, su ogr.virtualave.net, 9 luglio 1999. URL consultato il 26 febbraio 2014 (archiviato dall'url originale il 7 agosto 2001).
- ^ (EN) OGR-25 completion announcement, su blogs.distributed.net, distributed.net. URL consultato il 26 febbraio 2014.
- ^ (EN) OGR-24 completion announcement, su blogs.distributed.net, distributed.net. URL consultato il 26 febbraio 2014.
- ^ (EN) OGR-26 completion announcement, su blogs.distributed.net, distributed.net. URL consultato il 26 febbraio 2014.
- ^ (EN) Mike Reed, The OGR-27 project has been completed., su blogs.distributed.net, distributed.net. URL consultato il 26 febbraio 2014.
Bibliografia modifica
- Martin Gardner, Mathematical games, Scientific American, marzo 1972, pagine 108-112
Altri progetti modifica
Wikimedia Commons contiene immagini o altri file su Regolo di Golomb
Collegamenti esterni modifica
- Regoli di Golomb, su base5, su utenti.quipo.it.
- (EN) Pagina di James Shearer dell'IBM, su research.ibm.com.
- (EN) il progetto OGR a distributed.net, su distributed.net.
- (EN) Rulers, Arrays, and Gracefulness, da Math Games, su maa.org. URL consultato il 4 maggio 2019 (archiviato dall'url originale il 6 maggio 2013).
- (EN) elenco di regoli di Golomb di varie lunghezze, su research.ibm.com.
- (EN) generazione di regoli perfetti, su luschny.de.
