Skip to content

Stringhe e stuoie

3 giugno 2013

Come sarà il mondo dopodomani? Interrogarsi sul futuro può essere un esercizio tutt’altro che ozioso, specie se rielaboriamo in prima persona dati provenienti da fonti attendibili per stabilire strategie da seguire. Specie se accettiamo il fatto che una previsione non può essere certa, ma è legata ad una probabilità più o meno precisamente stimabile di successo.

Altre volte sono invece solo chiacchiere da bar. Come i pensieri di Marta, in viaggio per lavoro a Madrid, che mentre scarabocchia un foglio pensa a quando e se verrà meno l’ubiquità della carta stampata. Sarà così, non sarà così, chissà. Riga di traverso, riga di sbieco, rettangolino.

Riguardando gli appunti, Marta è colpita da alcuni disegni ai margini. Una certa unità rettangolare presenta un ugual numero di imboccature in entrata dall’alto e di sbocchi in uscita in basso. Internamente, delle vie di comunicazione collegano ogni entrata ad una sola uscita. Questi legami possono intrecciarsi, ma ogni singola linea può incrociarne al più altre due e una linea non può incrociare le stesse due linee di un’altra. Sembrano delle stringhe messe un po’ a caso in uno stivale.

Il numero di configurazioni possibili è un sottoinsieme delle classiche permutazioni non vincolate. Quante linee ci sono, al minimo, perché queste configurazioni siano meno di \frac{1}{32} delle permutazioni non vincolate?

Se lasciamo per un secondo da parte il secondo vincolo, possiamo usare una notazione compatta, per esempio n!^k per far disgustare i più, che rappresenti il numero di permutazioni di n oggetti dove k sia la massima distanza che l’oggetto i-esimo possa avere dalla posizione i. Così n!^0 ammette l’unica permutazione con gli oggetti ordinati, mentre n!^{n-1} non impone di fatto alcun vincolo. Per ogni n vale che
1 = n!^0 \leq n!^1 \leq \ldots \leq n!^{n-1} = n!

E tutto ad un tratto, il Giappone! Chi pratica judo dovrebbe già conoscere la parola tatami, per tutti gli altri basti sapere che è questo il nome di una unità di pavimentazione tradizionale giapponese, stuoia rettangolare di dimensioni 2\times 1, che ricopre appunto palestre ma non solo. Se la stanza di casa ha dimensioni 3\times 3, posso usare 4 stuoie alle quali aggiungerne necessariamente una di dimensione 1\times 1.

Che guadagno c’è a parlare di tatami invece che di domini e monomini? Il guadagno sta nel fatto che una disposizione di stuoie prevede il concetto di buon auspicio (inglese: auspicious tatami tiling, per il giapponese aspetto il suggerimento dei lettori). Sono favorevoli quelle disposizioni dove in nessun punto si incontrano quattro stuoie.

Che legame c’è allora con le stringhe di cui sopra? Molto stretto. Consideriamo le possibili disposizioni favorevoli di tatami in una stanza 2\times n e contemporaneamente un rettangolo con n+1 stringhe. Queste n+1 stringhe hanno n spazi intermedi, e si può vedere che ad ogni modo di intrecciare le stringhe corrisponde un modo di disporre le stuoie e viceversa.

Ciò significa che i due problemi hanno la stessa forma, sono isomorfi. Contare le stringhe o contare le stuoie è allora la stessa cosa, anche se a priori non sembra esserci troppa affinità tra i due problemi. Cosa succede se facciamo cadere il secondo vincolo e guardiamo n!^2 o n!^3? Cosa succede se consideriamo stanze 3\times n, o introduciamo stuoie di 3\times 1 o se imponiamo altri vincoli sulle stringhe? Buon divertimento, e se trovate qualcosa di interessante fatemi sapere.

Stringhe e stuoie


Sia \lbrace 1, \ldots, n\rbrace un insieme di n oggetti. Il rapporto tra le permutazioni che vincolano ogni elemento i alle posizioni j con |i-j| \leq 2, escludendo però il pattern abcd \rightarrow cdab, e le permutazioni non vincolate è inferiore a 2^{-5}. Quanto è n al minimo?

Annunci
2 commenti leave one →
  1. 3 giugno 2013 6:34 pm

    Ho modificato il minimo indispensabile il testo per rimediare ad una piccola ma fatale svista. Jean

Trackbacks

  1. Il piccolo di Fermat, googol divisibili per 7 e 360 palline colorate | Con le mele | e con le pere

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: