Regla de Golomb

Regla de Golomb

[0, 1, 4, 6] Regla de Golomb d'orde 4 i llongitut 6. Esta regla és tant òptima com a perfecta.

Eixemple d'una sala de conferències en proporcions d'una regla de Golomb de [0, 2, 7, 8, 11], sent configurable en 10 tamanys diferents.

En matemàtica, una regla de Golomb és una série de marques en posicions sanceres entre sí a lo llarc d'una regla imaginària de tal forma que cap de les marques tenen entre sí distàncies iguals.

La regla de Golomb va ser nomenada pel matemàtic i ingenier nortamericà Solomon W. Golomb (n. 1932) i va ser descoberta independentment per Sidon (1932) i Babcock (1953).

Un dels resultats pràctics de les regles de Golomb és el disseny de ràdio antenes múltiples per desfasament d'ona en configuracions de radiotelescopios.

Existixen dos tipos de regles de Golomb, unes perfectes o òptimes i atres aproximades.

Les perfectes són la [0,1], [0,1,3] i [0,1,4,6] que són els números més curts per a 2, 3 i 4 marques respectivament.

Distributed.net ha realisat una busca massiva en paralel de regles de 24 marques:

[9, 24, 4, 1, 59, 25, 7, 11, 2, 10, 39, 14, 3, 44, 26, 8, 40, 6, 21, 15, 16, 19, 22]

La busca de regles de 28 marques està de moment en desenroll.

Regles de Golomb òptimes conegudes

La següent taula conté totes les regles de Golomb òptimes conegudes, excloent aquelles en marques en l'orde invers. Les primeres quatre són perfectes.

orde	llongitut	marques	descobriment	descobridor
1	0	0
2	1	0 1
3	3	0 1 3
4	6	0 1 4 6
5	11	0 1 4 9 11 0 2 7 8 11 0 3 4 9 11	1967?	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?	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?	John P. Robinson i Arthur J. Bernstein
8	34	0 1 4 9 15 22 32 34	1972	William Mixon
9	44	0 1 5 12 25 27 35 41 44	1972	William Mixon
10	55	0 1 6 10 23 26 34 41 53 55	1972	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	William Mixon
12	85	0 2 6 24 29 40 43 55 68 75 76 85	1979	John P. Robinson
13	106	0 2 5 25 37 43 59 70 85 89 98 99 106	1981	John P. Robinson
14	127	0 4 6 20 35 52 59 77 78 86 89 99 122 127	1985	James B. Shearer
15	151	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151	1985	James B. Shearer
16	177	0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177	1986	James B. Shearer
17	199	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199	1993	W. Olin Sibert
18	216	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216	1993	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	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?	Mark Garry, David Vanderschel i uns atres (proyecte 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 de maig de 1998	Mark Garry, David Vanderschel i uns atres (proyecte 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	1999	Mark Garry, David Vanderschel i uns atres (proyecte 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	1999	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 d'octubre de 2004	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 d'octubre de 2008	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 de febrer de 2009	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 de febrer de 2014	distributed.net
28	585	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 585	23 de novembre de 2022	distributed.net

* La regla òptima podria haver segut conegut abans d'esta data; esta data representa la data en que es va descobrir que era òptima (ya que totes les atres regles es va demostrar que no eren més menudes). Per eixemple, la regla que va resultar ser òptima per a l'orde 26 es va registrar el 10 d'octubre de 2007, pero no es va saber que era òptima fins que totes les atres possibilitats es varen agotar el 24 de febrer de 2009.

Regles de Golomb com a conjunts

Un conjunt de sancers

$A=\{a_1,a_2,\mathrm{...},a_m\}{a}_1<a_2<\mathrm{...}<a_m$

és una Regla de Golomb si i solament si

$\mathrm{\forall }i,j,k,l\in \{1,2,\mathrm{...},m\},a_i-a_j=a_k-a_l⟺i=k\wedge j=l.$

L'orde d'una Regla de Golomb és $m$ i la seua llongitut és $a_m-a_1$. La forma canònica té la forma $a_1=0$ i, si $m>2$, $a_2-a_1<a_m-a_{m-1}$. Qualsevol forma pot conseguir-se per mig de reflexió i translació

Referències

• Martin Gardner, "Mathematical games", Scientific American, March 1972, p. 108-112

Vore també

• Postulats de Golomb