Regula lui Golomb
În matematică , un conducător Golomb , numit după Solomon W. Golomb, care a fost primul care l-a descris, este un set de crestături plasate în poziții întregi pe un conducător imaginar, astfel încât să nu existe o pereche de crestături plasate la aceeași distanță. Numărul de crestături din riglă este ordinea sa, în timp ce distanța maximă dintre două crestături este lungimea sa. Traducerea și reflectarea unui conducător Golomb sunt considerate banale: prin convenție, prin urmare, crestătura din stânga este setată la 0, iar următoarea este cea mai mică dintre cele două valori posibile.
În niciun caz nu este necesar ca un conducător Golomb să poată măsura toate distanțele de la 1 la lungimea sa: dacă o face, este numit un conducător perfect . S-a dovedit că nu poate exista un conducător Golomb perfect pentru cinci sau mai multe crestături. Se spune că un conducător Golomb este optim dacă nu există un conducător Golomb de același ordin și mai scurt. Este ușor să creați o riglă Golomb, dar găsirea celor optime este o sarcină computerizată complicată. Distributed.net a finalizat căutarea în paralel în masă a regulilor de ordine optime 24 [1] , 25 [2] , 26 [3] și 27 [3] , confirmând candidații suspecți. Distributed.net caută, de asemenea, din februarie 2014, regula pentru ordinea optimă 28. [4]
O utilizare practică a riglelor Golomb este proiectarea antenelor radio în matrici de fază, cum ar fi radiotelescoapele . La stațiile de bază ale telefonului mobil, antenele pot fi adesea văzute într-o configurație echivalentă cu rigla lui Golomb [0,1,4,6].
În acest moment nu se cunoaște complexitatea găsirii regulilor optime Golomb de lungime arbitrară n , dar se crede că este o problemă dificilă pentru NP . [5]
Cunoscute reguli Golomb optime
Tabelul următor prezintă toate regulile Golomb optime cunoscute, excluzându-le pe cele echivalente cu mai puțin decât reflexia. Tabelul este complet până la ordinea 27 inclusiv.
| Ordin | lungime | crestături | data descoperită | descoperitor |
|---|---|---|---|---|
| 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 și 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 și 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 și 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 și 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 și alții (proiect web) |
| 21 | 333 | 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333 | 8 mai 1998 [8] | Mark Garry, David Vanderschel și alții (proiect web) |
| 22 | 356 | 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 | ~ Mai 1999 [9] | Mark Garry, David Vanderschel și alții (proiect web) |
| 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 iulie 1999 [10] | Mark Garry, David Vanderschel și alții (proiect web) |
| 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 octombrie 2004 [11] | distribuite.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 octombrie 2008 [12] | distribuite.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 februarie 2009 [13] | distribuite.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 februarie 2014 [3] [14] | distribuite.net |
Notă
- ^ (EN) OGR-24 Statistici generale ale proiectului , pe stats.distributed.net, distribuite.net . Adus la 1 martie 2014 .
- ^ (RO) OGR-25 Statistici generale ale proiectului , pe stats.distributed.net, distribuite.net . Adus la 1 martie 2014 .
- ^ a b c ( EN ) OGR-26 Statistici generale ale proiectului , pe stats.distributed.net , distribute.net . Adus la 1 martie 2014 .
- ^ (RO) Mike Reed, Pregătindu-mă pentru OGR-28! , pe distribuit.net , 18 februarie 2014. Adus 1 martie 2014 .
- ^ Conducători Golomb modulari și reguli
- ^ 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 rigle table , la research.ibm.com , IBM . Adus la 26 februarie 2014 .
- ^ (RO) În căutarea conducătorilor optimi 20 și 21 Mark Golomb , pe members.aol.com. Adus la 26 februarie 2014 (arhivat din original la 6 decembrie 1998) .
- ^ (RO) Ajutați să găsiți marcatorul optim Golomb 22 Mark! , pe ogr.virtualave.net , 6 mai 1999. Accesat la 26 februarie 2014 (arhivat din original la 24 mai 2000) .
- ^ (RO) Ajutați să găsiți marcajul optim Golomb 23 Mark! , pe ogr.virtualave.net , 9 iulie 1999. Adus la 26 februarie 2014 (arhivat din original la 7 august 2001) .
- ^ (RO) Anunț de finalizare OGR -25 , pe blogs.distributed.net, distribuit.net . Adus la 26 februarie 2014 .
- ^ (EN) Anunț de finalizare OGR -24 , pe blogs.distributed.net, distribuit.net . Adus la 26 februarie 2014 .
- ^ (RO) Anunț de finalizare OGR -26 , pe blogs.distributed.net, distribuit.net . Adus la 26 februarie 2014 .
- ^ (EN) Mike Reed, Proiectul OGR-27 a fost finalizat. , pe blogs.distributed.net , distribuit.net . Adus la 26 februarie 2014 .
Bibliografie
- Martin Gardner , Jocuri matematice , Scientific American , martie 1972, paginile 108-112
linkuri externe
- Regulile lui Golomb , pe baza5 , pe users.quipo.it .
- ( RO ) Pagină de James Shearer de la IBM , la research.ibm.com .
- ( EN ) proiectul OGR la distribuit.net , pe distribuit.net .
- (EN) Rulers, Arrays, and Gracefulness, de la Math Games pe maa.org. Adus la 4 mai 2019 (arhivat din original la 6 mai 2013) .
- (EN) listă a conducătorilor Golomb de diferite lungimi , pe research.ibm.com.
- ( EN ) generarea de reguli perfecte , pe luschny.de .
