Fregi e medaglioni di De Bruijn

Fregi e medaglioni di De Bruijn con Mathcad

Carlo Elce www.matematicamente.it

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 sequenza in un array bidimensionale 2 x N di passi nel percorso, in modo che ogni colonna rappresenti un movimento.

Impostiamo prima i necessari intervalli di variazione, impostando il numero

N 1000

n 1 .. N

k 1 .. 2

S floor rnd 2

S 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 N 1 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, p e q, dove

p q

Assumiamo che p e q 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 schermata.

n p n

I passi dipendono dalla seguente funzione di n, che comunica se n volte l'en esimo numero triangolare cade nella prima o nella seconda metà della classe di resti modulo 2 q.

.

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, poiché in un array monodimensionale si può così memorizzare l'intera sequenza.

Il passo en esimo è dato da:

1 i

δ δ δ δ

. . . .