Regolo Circolare Perfetto

Cosa è un regolo circolare perfetto?.

Alla sezione varie, nel problema "laboratorio di lingue", si parla dell'utilizzo del regolo circolare perfetto (RCP), uno strano aggeggio, introdotto da Dario in un altro thread, che per il momento non sono riuscito a reperire.

Ed ecco la descrizione fornita da Dario:

Queste serie di numeri tali che le differenze di ciascuna coppia siano tutte differenti sono state oggetto di molti studi.
Regoli perfetti non circolari, sono noti come grafi graziosi, ne ha parlato anche Gardner.
Vedi

http://members.aol.com/golomb20/

http://www.ee.duke.edu/~wrankin/golomb/golomb.html

Gli RCP sono la stessa cosa, considerando la serie di numeri chiusi ad anello.
Un es. con 4 termini è 0,1,3,9. Le differenze di questi numeri, a coppie coprono tutto il range da 1 a 12.
Allora mettiamo i numeri da 0 a 12 distribuiti su una circonferenza in modo regolare:

        0
    12      1
  11         2
 10           3
   9         4
    8       5
      7   6 

Costruisco un quadrilatero unendo 0,1,3,9,0
Vediamo che i punti 0 ed 1 distano 1 unita' d'arco da una parte e 12 unità dall'altra.
Se elenchiamo tutte le distanze dei punti 0,1,3,9 presi a coppie abbiamo

Punti  Distanze
0,1     1,12
0,3     3,10
0,9     9, 4
1,3     2,11
1,9     8, 5
3,9     6, 7

Come abbiamo detto tutte le distanze da 1 a 12 sono presenti una sola volta.
Cosa ci serve tutto questo?
Se ad es. come nel problema appena proposto, ho 13 persone, che devo fare incontrare 4 alla volta per 13 volte in modo che ciascuno incontri tutti gli altri, il nostro RCP ci da subito la risposta.
(nota: il riferimento è a un problema che sarà prossimamente inserito in questo sito)

Basta far ruotare il quadrilatero all'interno del cerchio di una tacca alla volta per 12 volte, i vertici intercettano le varie quadruple:

 0, 1, 3, 9
 1, 2, 4,10
 2, 3, 5,11
 ..........
12, 0, 2, 8

Proprio per la caratteristica del RCP, nessuna coppia sarà presente 2 volte.
Nell'occasione ricordata da Paolo riuscimmo a costruire un RCP con 10 termini

10RCP = 0,1,3,9,27,49,56,61,77,81.
Le differenze a due a due sono tutti i naturali da 1 a 90.

Ecco un esempio di RCP con 4 termini (0,1,3,9) in una circonferenza suddivisa in 13 archi:

Ruotando il disco blu di una tacca per volta, le sue 4 tacche indicano, sul disco giallo. quaterne sempre differenti, e nessuna coppia sarà presente in due quaterne.

Ulteriori approfondimenti, ancora indicati da Dario:

Richard Guy in "Unsolved Problem in Number Theory" dedica un paio di pagine a questo argomento col titolo di Modular Difference Sets, per noi RCP.
Ecco cosa dice:
Singer ha dimostrato che un RCP puo' esistere solo se N (il numeri di archi del nostro cerchio) e' della forma k^2+k+1, e che esiste sempre se k e' un primo o una potenza di un primo. D'altro canto non si conoscono soluzioni con k che non sia una potenza di un primo ed e' stato congetturato che non ne esistano.

Poi riporta 8 RCP con N da 3 a 91.

vedere la tabella in fondo a questa pagina, estesa fino a N=307
notare che il valore T in tabella, che indica il numero di tacche del disco rotante nel nostro RCP, corrisponde al k della formula di Singer incrementato di una unità:
T = k+1

Piu' interessante il capitolo di T. O'Beine in Puzzles and Paradoxes.
Innanzi tutto se si ha una soluzione per un dato N e' possibile ricavarne altre differenti, con questo stratagemma.

Prendiamo ad es. N= 13  (0,1,3,9)

               x
               0    x
          12       1
       11             2
    
     10                 3 x
      
       9              4
     x    8        5
             7  6    

            
Ora procedo in senso orario contando r archi unitari come fossero 1, ricordando quando incontro le x; e' evidente che dovro' fare r giri.
Con r=1 faro' i miei 13 passi 0,1,2,3.....12,0 incontrando le x in 0,1,3,9 come gia' visto.
Con r=2 faro' i 13 passi  0,2,4,6,8,10,12,1,3,5,7,9,11,0 incontrando le x in 0,7,8,11
producendo una nuova soluzione.
Se provo con r=3 mi ritrovo con 0,1,3,9 una soluzione gia' vista. In questo caso difatti esistono solo 2 soluzioni.

Per ricavare tutte le possibili soluzioni per un dato N, occorre provere con tutti gli r, da 1 a N-1.

Ma come fare per avere la soluzione madre? Qui e' un po' piu' macchinoso.
Vediamo.
Indicando, come ha fatto Paolo, con T il numero di termini presenti in un RCP, ci saranno T(T-1)/2 coppie, e, considerato che ogni coppia genera due distanze, potremo coprire tutto il range di
N = T^2-T unita'.

Questo puo' essere sempre fatto  quando T-1 e' un primo o una potenza di un primo.
O'Beirne dice che per T-1 = potenza di un primo, esistono procedure troppo complesse per essere descritte nel suo libro,
ma se T-1 ed N sono entrambi primi, c'e' un metodo abbastanza semplice.

Mettiamo allora T = p+1,
senza perdere di generalita' proviamo con p=5, T=6
sappiamo gia' che N=31.
Possiamo vedere che N = p^2+p+1.

Noi dovremo esaminare tutte le espressioni
x^3-Ax-1
per differenti valori di A da 1 a p-1: se per alcuni x scelti fra 1 e p-1, l'espressione e' multiplo di p, allora verra' eliminato il corrispondente valore di A.
2^3-2-1 = 5       per  A=1
3^3-2*3-1 = 20    per  A=2

Nel nostro esempio per p=5, si elimina A=1 e A=2. Restano buoni i valori
A=3 e A=4.
Proviamo con A=3:

Incominciamo a scrivere una stringa di cifre che inizia con 001, poi aggiungeremo altre cifre in questo modo ricorrente:

dette 
S_1,  S_2 ..... S_n        le cifre della stringa
      
S_1=0,    S_2=0,    S_3=1
l'ennesima cifra e'  
S_n = A*S_(n-2) + S_(n-3)

La quarta cifra sara' 3 volte la seconda + la prima: la stringa diventa 0010.
La quinta cifra sara' 3volte la terza + la seconda: la stringa diventa 00103
Procedendo in questo modo si produce la stringa periodica di 31 cifre
0010314132042203244411242404421
Gli zeri stanno in posizione 0,1,3,10,14,26, e provando con A=4 in posizione 0,1,3,8,12,18....

Bingo!

PS. col metodo descritto si trova che per  N= 7,13,21,31,57,73,91 esistono rispettivamente 1,2,1,5,6,4,6 RCP differenti.

Ecco un tabella con diversi possibili RCP di T termini (T tacche nell'elemento mobile) opportunamente posizionati in circonferenze suddivise in N archi (N tacche nell'elemento fisso, numerate da 0 ad N-1).

Le distanze tra due termini, misurate sulla circonferenza, nei due sensi, coprono tutto il range da 1 ad N-1.

N-1 = T * (T-1)

Per ulteriori approfondimenti, Silvio ci segnala il sito

http://mathworld.wolfram.com/PerfectDifferenceSet.html

hanno un'ottima bibliografia.

indice varie

home