Fregi e medaglioni di De Bruijn

Carlo Elce www.matematicamente.it

Fregi e medaglioni di De Bruijn con Mathcad

Un percorso nel piano può essere descritto da una sequenza di zero e di uno usando il seguente codice:

00 sinistra

10 destra

01 giù

11 su

Usando questo schema, possiamo memorizzare un insieme di movimenti nel piano e provare a

collegare i punti in modo da ottenere interessanti figure. Possiamo anche generare strutture casuali o

provare a organizzare i movimenti in strutture ripetitive, come quella sopra rappresentata.

Illustreremo queste possibilità prima con una sequenza casuale. Per semplicità, organizzeremo la

n

, in modo che ogni colonna rappresenti un movimento.

sequenza in un array bidimensionale 2 x N di passi nel percorso:

Impostiamo prima i necessari intervalli di variazione, impostando il numero

N 1000

n 1 .. N

k 1 .. 2

S floor rnd 2

k , n

Scegliamo ora un punto iniziale, e generiamo iterativamente i passi:

0

start 0

< >

1 start

walk .

2 S 1 0

< > < > 1 , n

n 1 n if S 0 , ,

walk walk .

2 , n 2 S 1

0 1 , n

Carlo Elce www.matematicamente.it

N 1

Ora rappresentiamo il percorso, che è un cammino casuale su un reticolo di interi (abbiamo

punti):

m 1 .. N 1

20

10

walk 0

2 , m 10

20 10 0 10 20 30

walk

1 , m

Ovviamente gli assi coordinati x e y devono essere impostati con la stessa scala affinché le forme

elementari dei percorsi appaiano quadrate.

Il matematico N. G. de Bruijn scoprì che la sequenza di 0-1 generata da una particolare classe di

congruenze aritmetiche produce strutture molto belle a vedersi che sono fregi (una struttura ripetuta

lungo un asse) o medaglioni chiusi. Generiamo alcune delle figure di De Bruijn con Mathcad. .

1 p 2 q.

p q <

Le figure di De Bruijn sono determinate dal rapporto di due interi positivi, e , dove

p q

Assumiamo che e siano primi tra loro. I loro valori li assumeremo in basso vicino al grafico, in

modo che sia possibile, usando Mathcad, cambiare i dati in ingresso e vedere le figure nella stessa

n p n

schermata. I passi dipendono dalla seguente funzione di , che comunica se volte l'en esimo numero

2 q

triangolare cade nella prima o nella seconda metà della classe di resti modulo .

.

n n 1

δ .

.

n if mod p , 2 q < q , 1 , 1

2

De Bruijn memorizzò il suo percorso come una sequenza di numeri complessi, e ciò è conveniente,

n

poiché in un array monodimensionale si può così memorizzare l'intera sequenza. Il passo en esimo è

dato da:

1 i

δ δ δ δ

. . . .