Newsgroup: it.hobby.enigmi
Titolo: Permutazioni sincronizzate

Sistemare le 24 permutazioni delle cifre 1,2,3,4 incolonnate una sotto
l'altra in modo che non ci siano 2 numeri uguali adiacenti verticalmente
(uno sull'altro).
In generale per quali n, le n! permutazioni possono essere incolonnate
in questo modo ?
:) dario

 in questo modo ?
Non ne sono del tutto sicuro, dovrei verificare se la proprieta' (b) e'
valida per qualunque n.
Se cosi' fosse, il metodo dovrebbe funzionare comunque per n->infinito.
Infatti basterebbe scrivere il primo gruppo, con le righe disposte in un
ordine qualsiasi;
poi aggiungere via via gli altri gruppi, disponendo ogni volta come prima
riga quella *compatibile* con l'ultima del gruppo precedente.
ciao
paolo

 valida per qualunque n.
Ho fatto qualche verifica e la cosa non e' cosi' semplice.
Ho trovato:
_ per n pari (non ho la dimostrazione, ma per ora e' solo una congettura)
sembra che presi comunque due gruppi, ciascuna stringa del primo risulti
compatibile con ALMENO una stringa del secondo; in questo caso sarebbe
comunque possibile agganciare i gruppi in successione
_per n dispari NO; per esempio non sono compatibili le stringhe appartenenti
ai gruppi generati da [12345] ed [13524] (stringhe in cui le differenze tra
due termini consecutivi sono costanti, a meno di 5)
Comunque la condizione che avevo ipotizzato era sufficiente, ma non
necessaria, quindi non e' detto che con n dispari non sia possibile.
La cosa richiede ulteriori approfondimenti.
ciao
paolo

Ciao a tutti, provo il rientro, sapendo
che in termini di tempo mi costera' caro.
Vi ritrovo con piacere e rinnovo i complimenti
a Paolo per il sito.
Bando alle ciance.
Anche se in ritardo, ma l'ho letto solo ieri, ecco
la mia soluzione. Chiamo permutazione semplice di una
combinazione una qualunque combinazione che si ottiene
dalla originale spostando i suoi termini ciclicamente
ossia senza scambi di posizioni.
Parto da un esempio con 5 elementi.
Come gia' fatto notare da Paolo, tutti gli
elementi appartenenti ad una permutazione semplice sono
tra di loro compatibili.
12345
51234
45123
34512
23451
Quindi possiamo considerare solo la prima riga, che chiamiamo
generatrice, ce ne sono 24 nel coso di n=5.
Ora dobbiamo vedere quante di queste generatrici sono tra di loro
incompatibili.
Ce ne sono 6 gruppi disgiunti, 4 alla volta incompatibili fra di loro, per
cui
per n=5 soluzione esiste (e non poche), in quanto basta fare in modo
che 2 generatrici incompatibili tra loro non siano in ordine ma
intervallate.
Per vedere questo vediamo di costruire una funzione stato che ci restituisca
un valore uguale per tutte le permutazioni.
Lo stato sara' costituito da 3 cifre in questo modo. La prima indica la
distanza
della cifra 1 dalla cifra 2 della combinazione. La seconda la distanza di 2
da 3.
La terza la distanza di 3 da 4. Non serve altro.
La combinazione
12345 = 111
13254 = 243
e cosi' via.
In questo modo abbiamo proprio 24 combinazioni, in quanto al primo posto
posso avere 4 numeri al secondo 3 e al terzo 2.
Infatti consideriamo la combinazione 1xy (ossia 12zzz), x non puo' valere 4,
e y non puo' valere ne 3 ne 5-x in quanto posizioni gia' occupate.
Si puo' vedere che il gruppo 111
e' incompatibile con le generatrici
222
333 che e' proprio l'esempio fatto da Paolo = 13524
444
Cio' che segue dovrebbe valere per n dispari e primo. Non cambia
la conclusione finale.
In generale presa una generatrice a caso, xyz essa è incompatibile con
kx mod n ky mod n kz mod n per ogni k tra 1 e n-1.
Esempio
124 incompatibile con
243 in questo caso k = 2 (2=2*1,4=2*2,3=4*2 mod 5)
In generale quindi per ogni n si hanno (n-1)! generatrici raggruppabili
in gruppi di n-1 elementi incompatibili tra di loro.
Per cui soluzione esiste sempre.
Almeno secondo me e quanti riesco a convincere con questa dimostrazione :-)
Ciao
Andrea
P.S. potrei come al solito aver scritto un mucchio di stupidate!
--
Posted from [212.17.205.1] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG