Newsgroup: it.hobby.enigmi
Titolo: laboratorio di lingue

 e' quella che "chiude il cerchio", 
Scusate, ma ultimamente sono un po' incasinato e non mi riesce di
seguire questo bel tema, per mancanza di tempo. Difatti con la fretta ho
fatto un po' di casino. Il metodo e' interessante, ma effettivamente la
serie di distanze deve essere scelta con molta attenzione. In generale
devo perdere k numeri tali che  le somme parziali di numeri adiacenti
presi 1,2,3,...,k alla volta siano tutte differenti e considerarli
ciclicamente. La stringa che avevo dato contiene un paio di errori.
Verificando per k=10 trovo:
1,2,4,5,8,10,14,21,25,47 che dovrebbe andare bene. Con questi "passi" si
ottengono con 137 persone, 137 gruppi da 10 senza ripetizione di coppie.
Partendo da qui, pero' non mi riesce di vedere un modo per ridurre le
persone ed ottenere 40 sequenze. Si potrebbe pensare di permettere circa
meta' di soluzioni valide facendo girare solo di un semicerchio con
un'ottantina di persone, ma quali sono i valori che lo permettono ?
Col metodo simile a quello adottato da Paolo, invece mi sembra si possa
fare meglio. Devo scappare al lavoro. Vi lancio l'idea se potete
verificare. Ci sentiamo stasera.
Metto 81 persone in una matrice 9*9 ottenendo 36 nonuple. 9 verticali, 9
orizzontali, 9+9 per le due serie di diagonali spezzate. Queste stanno
tutte il
linea retta (le diagonali vanno viste come se il 9*9 avesse tante copie
traslate che saturano il piano) vedi sotto. Aggiungo la persone
82,83,84,85
rispettivamente per ciascuno di questi 4 insiemi ottenendo 36 decine con
85 persone. Per le 4 mancanti devo cercare, sperando che esista, un
insieme di 9 persone disallineato, in pratica una soluzione delle 9
regine non sotto attacco, e che non lo siano neppure sulle diagonali
"spezzate" se c'e' e non ha simmetrie, prendo i 4 insiemi di 9 persone
ottenute per rotazioni di 90 gradi di tale sol. ed aggiungo a queste una
86 persona.
Chi vuole verificare ??
Devo andare. Ciao :)dario
PS es. di cosa intendo per diagonali spezzate. Nel 4*4 qui sotto:
A B C D
E F G H
I L M N
O P Q R
Le 4 diagonali \ sono DELQ,CHIP,BGNO,AFMR
Le 4 diagonali / sono APMH,EBQN,IFCR,OLGD

 Chi vuole verificare ??
Nisba. Non solo nessuna delle soluzioni del 9 regine classico rispetta i
vincoli, ma non credo si possano piazzare neanche 8 regine nella scacchiera
9X9 in maniera legale. Ho controllato tutte le soluzioni del 9 regine
classico, escludendo una regina alla volta, ma non ho trovato soluzioni
valide. Invece 7 si piazzano facilmente anche a mano.
In qesto caso nelle ultime 4 giornate ci sarebbero 3 postazioni da occupare.
Se trovo 4 sol. con le 7 regine completamente differenti allora con 6 nuove
persone (ABCDEF, cosi' disposte: ABC, ADE, CDF, BEF) completo le decine.
Eccole qui:
00 13 26 32 47 51 64,85 86 87
01 15 20 36 43 57 62,85 88 89
02 16 21 37 45 53 60,87 88 90
03 15 27 31 44 56 68,86 89 90
ed ecco le altre 36
00 01 02 03 04 05 06 07 08,81
09 10 11 12 13 14 15 16 17,81
18 19 20 21 22 23 24 25 26,81
27 28 29 30 31 32 33 34 35,81
36 37 38 39 40 41 42 43 44,81
45 46 47 48 49 50 51 52 53,81
54 55 56 57 58 59 60 61 62,81
63 64 65 66 67 68 69 70 71,81
72 73 74 75 76 77 78 79 80,81
---
00 11 22 33 44 55 66 77 88,82
01 12 23 34 45 56 67 78 89,82
02 13 24 35 46 57 68 79 90,82
03 14 25 36 47 58 69 80 91,82
04 15 26 37 48 59 70 81 92,82
05 16 27 38 49 60 71 82 93,82
06 17 28 39 50 61 72 83 94,82
07 18 29 40 51 62 73 84 95,82
08 19 30 41 52 63 74 85 96,82
---
00 10 20 30 40 50 60 70 80,83
01 11 21 31 41 51 61 71 72,83
02 12 22 32 42 52 62 63 73,83
03 13 23 33 43 53 54 64 74,83
04 14 24 34 44 45 55 65 75,83
05 15 25 35 36 46 56 66 76,83
06 16 26 27 37 47 57 67 77,83
07 17 18 28 38 48 58 68 78,83
08 09 19 29 39 49 59 69 79,83
---
00 73 65 57 49 41 33 25 17,84
09 01 74 66 58 50 42 34 26,84
18 10 02 75 67 59 51 43 35,84
27 19 11 03 76 68 60 52 44,84
36 28 20 12 04 77 69 61 53,84
45 37 29 21 13 05 78 70 62,84
54 46 38 30 22 14 06 79 71,84
63 55 47 39 31 23 15 07 80,84
72 64 56 48 40 32 24 16 08,84
81+4+6=91 persone in totale.
Chi riesce a fare meglio?
Ciao, Silv:o)

ho pasticciato col secondo blocco da 9, ecco quello corretto
00 09 18 27 36 45 54 63 72,82
01 10 19 28 37 46 55 64 73,82
02 11 20 29 38 47 56 65 74,82
03 12 21 30 39 48 57 66 75,82
04 13 22 31 40 49 58 67 76,82
05 14 23 32 41 50 59 68 77,82
06 15 24 33 42 51 60 69 78,82
07 16 25 34 43 52 61 70 79,82
08 17 26 35 44 53 62 71 80,82
Ciao, Silv:o)

 Chi riesce a fare meglio?
Io.
L'86 compare solo in due righe, quindi incontra solo 18 persone. Se trovo un
numero che non incontra mai nessuno di loro, posso rimpiazzare l'86: salvo
errori e' il 79. I due 86 si possono allora sostituire con dei 79.
e siamo a quota 90.
Ciao, Silv:o)

persone ed ottenere 40 sequenze.
Utilizzando il tuo RCQP (regolo circolare quasi perfetto), ho costruito la
matrice 10*137, con 137 persone.
La prima riga e'
0 1 3 7 12 20 30 44 65 90
e cosi' via, incrementando di 1mod137, per finire con l'ultima riga:
136 0 2 6 11 19 29 43 64 89
poi ho eliminato tutte le righe che contenevano i numeri:
136, 135, 134, 132, 131, 130, 123, 115, 111,
88, 45, 23, 22, 21, 18, 15, 9 ,3, 2, 1, 0
in totale ho eliminato 97 righe e 21 persone, rimanendo con
40 righe e 116 persone.
Non credo che per questa via si possa migliorare di molto, forse, scegliendo
meglio i numeri da eliminare, si potrebbe riuscire a togliere al max una o
due persone in piu'.
Credo che convenga continuare la ricerca del RCP, e partire dalla matrica
10*91.
A quel punto penso che si potrebbe riuscire ad eliminare all'incirca
10+9+8+7+6+6+5=51 righe e 7 persone, rimanendo con 40 righe e 84 persone.
ciao
paolo

 03 15 27 31 44 56 68,86 89 90
Il 15 e l'89 creano problemi.
Ieri sera ho fatto il tuo medesimo ragionamento. E' sufficiente trovare
una sola soluzione per 7 e ripeterla 4 volte per rotazioni di 90 gradi.
Ho trovato (iniziando dall'1):
1,17,22,36,56,69,75 che per rotazioni diventa:
4,11,35,48,63,70,73
9,12,19,34,47,71,78
7,13,26,46,60,65,81.
Si potrebbe raccattare un'altra decina scegliendo dalla matrice 6
studenti che non si sono ancora incontrati ed integrarli con
81,82,83,84.
Ho trovato un po' di materiale riguardante RCP, regoli lineari ecc..
vado a mangiare poi metto giu'.
A dopo.
:)dario

Per il soggetto che stiamo trattando ho trovato 2 riferimenti veramente
interessanti.
Il primo: PUZZLES AND PARADOXES di O'Beirne Dover 1965.
Ci sono un paio di pagine sul "Race-Tracks" praticamente il ns. RCP.
Ricordando che con n punti si ottiene un cerchio di N = n^2-n+1 unita',
i punti salienti sono:
RCP esistono sicuramente quando n-1 e' un primo o una potenza di un
primo.
Per gli altri casi resta insoluto, ma e' stato provato che non ne
esistono con n<1600.
Dice che il metodo per generarli e' troppo complesso per essere
riportato li', ma c'e' un caso felicemente semplice, quando n-1 ed N
sono entrambi primi.
Prendiamo come es. n=6, n-1=p=5  N=31.
Diamo innanzitutto valori per x e per A che vanno da 1 a p-1, allora se
nell'espressione
x^3-Ax-1 per certi A, alcuni valori di x danno multipli di p, quegli A
vanno scartati. 
Nel nostro caso ad es per n=2 A=1 si ha 2^3-2-1=5. Percio' A=1 va
scartato.
Provando i vari casi restano validi A=3 e A=4 che daranno 2 distinte
soluzioni. Cominciamo con A=3.
A questo punto si crea una stringa di numeri semplicemente partendo con
0,0,1 proseguendo verso destra. Per trovare il prossimo termine si
moltiplica il penultimo per A e si somma il terzultimo tutto mod p.
0*3+0=0 diventa 0,0,1,0.  Ancora 1*3+0=3. 0,0,1,0,3..... Continuiamo
cosi' fino ad incontrare un'altra coppia di zeri, a quel punto i termini
si ripetono ciclicamente, si ottiene:
0 0 1 0 3 1 4 1 3 2 0 4 2 2 0 3 2 4 4 4 1 1 2 4 2 4 0 4 4 2 1
Gli zeri sono in posizione 0,1,3,10,14,26 e gli intervalli in ordine
ciclico sono (1,2,7,4,12,5) un RCP !!!
A proposito Paolo come hai trovato le 4+2 soluzioni ???
---------------------------------------------------------
Il secondo: Wheels,Life and Other Mathematical Amusements di M. Gardner
Freeman 1983.
Parla dei Grafi Graziosi di S. Golomb. Disegnamo un quadrato con le due
diagonali. Etichettiamo i 4 vertici con 0,1,4,6 ora se numeriamo
ciascuna linea con il valore della differenza dei rispettivi vertici,
otteniamo 1,2,3,4,5,6 tutte le distanze possibili sono ottenute; ecco un
Grafo Grazioso . Si puo' notare che se i valori dei 4 vertici li riporto
su un righello la proprieta' delle distanze relative non cambia.
Chiamiamolo RLP Regolo Lineare Perfetto. Quando n>4 si trovano solo
Regoli lineari non perfetti, tutte le distanze sono differenti, ma non
sono tutte quelle possibili. Sappiamo che questo va benissimo per il
nostro problema.
Dice che non ci sono metodi semplici per generarli e riporta i risultati
migliori trovati al calcolatore da un certo W.Mixon per n<12. Per 10
distanze da' 1,3,9,15,5,14,7,10,6,2 che non potendo essere considerate
ad anello, non ci servono.
 Mi e' venuta un'idea...  per 9 distanze da': 1,5,4,13,3,8,7,12,2  cerco
un decimo numero tra i valori ancora disponibili il piu' basso
ammissibile e' 36 ... provo anche ciclicamente...perfetto !!
Mettendo i nostri 91 studenti tutti per mano in girotondo, con 10
paletti ficcati nel terreno alle distanze dette, davanti ad altrettanti
studenti, ad ogni passo del girotondo i paletti indicheranno una
possibile decina. 91 in tutto. 
ciao :)dario

Dai risultati del post precedente, ho schiumato le 91 lezioni togliendo
gli studenti in eccedenza.
Ecco le 40 rimaste con 84 studenti come previsto da Paolo.
01 02 07 11 24 27 35 42 54 56
02 03 08 12 25 28 36 43 55 57
03 04 09 13 26 29 37 44 56 58
04 05 10 14 27 30 38 45 57 59
05 06 11 15 28 31 39 46 58 60
06 07 12 16 29 32 40 47 59 61
07 08 13 17 30 33 41 48 60 62
08 09 14 18 31 34 42 49 61 63
09 10 15 19 32 35 43 50 62 64
10 11 16 20 33 36 44 51 63 65
11 12 17 21 34 37 45 52 64 66
12 13 18 22 35 38 46 53 65 67
13 14 19 23 36 39 47 54 66 68
14 15 20 24 37 40 48 55 67 69
15 16 21 25 38 41 49 56 68 70
16 17 22 26 39 42 50 57 69 71
17 18 23 27 40 43 51 58 70 72
18 19 24 28 41 44 52 59 71 73
19 20 25 29 42 45 53 60 72 74
20 21 26 30 43 46 54 61 73 75
21 22 27 31 44 47 55 62 74 76
22 23 28 32 45 48 56 63 75 77
23 24 29 33 46 49 57 64 76 78
24 25 30 34 47 50 58 65 77 79
25 26 31 35 48 51 59 66 78 80
26 27 32 36 49 52 60 67 79 81
27 28 33 37 50 53 61 68 80 82
28 29 34 38 51 54 62 69 81 83
29 30 35 39 52 55 63 70 82 84
39 40 45 49 62 65 73 80 01 03 
40 41 46 50 63 66 74 81 02 04
41 42 47 51 64 67 75 82 03 05
42 43 48 52 65 68 76 83 04 06
43 44 49 53 66 69 77 84 05 07
69 70 75 79 01 04 12 19 31 33
70 71 76 80 02 05 13 20 32 34
71 72 77 81 03 06 14 21 33 35
72 73 78 82 04 07 15 22 34 36
73 74 79 83 05 08 16 23 35 37
74 75 80 84 06 09 17 24 36 38
:)dario

ciao :)dario
ciao
paolo

ammissibile e' 36 ... provo anche ciclicamente...perfetto !!
Bingooooo! ecco il nostro RCP a 10 tacche.
Bellissimo tema, con notevoli diramazioni: e dire che l'avevo proposto
avendo in mente niente piu di una formuletta di calcolo combinatorio!
Se ne sentiva la mancanza, dopo un periodo di stallo (a parte le
crittografie).
Ciao, Silv:o)

>A proposito Paolo come hai trovato le 4+2 soluzioni ???
che, con la tua diventano 5+2
1,2,7,4,12,5
1,2,5,4,6,13
1,3,2,7,8,10
1,3,6,2,5,14
1,7,3,2,4,14
1,14,6,2,5,3
1,14,4,2,3,7
Il bello e' che nel mio tabulato era presente anche la tua stringa
(1,2,7,4,12,5), che poi, quando sono andato a spuntare i casi possibili, mi
e' sfuggita.
--------------------
Ecco il metodo che ho usato:
Procedo per fasi successive, inizialmente una distanza e' nota (1) e 5
incognite;
lo indico con la stringa 1xxxxx
dopo la stringa scrivo tra parentisi il numero che dovro' aggiungere nella
fase seguente, cioe' il piu' piccolo numero non ottenibile come somma di
quelli gia' indicati (in questo caso e' 2)
Nella fase successiva riporto tutte le possibili stringhe ottenute
sostituendo una delle x con il numero indicato in precedenza, e sempre tra
parentisi, il prossimo numero da aggiungere.
Nella penultima fase, quando restano solo 2 incognite, posso aggiungere tra
parentisi 2 valori, quello calcolato come visto sopra e quello necessario
per portare il totale della striga a 31.
Durante lo sviluppo controllo se ogni stringa, parziale o completa, debba
essere esclusa, e quindi non svilupata nel seguito.
I motivi di esclusione, che indico tra i segni <>, possono essere;
_con i valori gia' scritti posso ottenere la stessa somma in due modi
diversi;
_nella penultima fase, il primo dei due valori da aggiungere e' maggiore o
uguale al secondo.
Ecco il tabulato; sarebbe meglio rappresentabile con un albero, ma penso che
sia comprensibile anche cosi'.
Mi fermo alla penultima fase, e' gia' abbastanza lungo...
Spero che non ci siano troppi errori di trascrizione:
________________________________
Prima fase
1 x x x x x   (2)
________________________________
Seconda fase
1 2 x x x x   (4)
1 x 2 x x x   (3)
1 x x 2 x x   (3)
________________________________
Terza fase
1 2 4 x x x   (5)
1 2 x 4 x x   (5)
1 2 x x 4 x   (5)
1 2 x x x 4   (6)
1 3 2 x x x   (7)
1 x 2 3 x x   (4)
1 x 2 x 3 x   (4)
1 x 2 x x 3   (5)
1 3 x 2 x x   (5)
1 x 3 2 x x   (4)
1 x x 2 3 x   (4)
1 x x 2 x 3   (5)
________________________________
Quarta fase
1 2 4 5 x x   (8,11)
1 2 4 x 5 x   (8,11)
1 2 4 x x 5   <2+4=1+5>
1 2 5 4 x x   (6,13)
1 2 x 4 5 x   (6,13)
1 2 x 4 x 5   (7,12)
1 2 5 x 4 x   (6,13)
1 2 x 5 4 x   (6,13)
1 2 x x 4 x   (7,12)
1 2 6 x x 4   <10,8>
1 2 x 6 x 4   (8,10)
1 2 x x 6 4   (8,10)
1 3 2 7 x x   (8,10)
1 3 2 x 7 x   (8,10)
1 3 2 x x 7   <9,9>
1 4 2 3 x x   <1+4=2+3>
1 x 2 3 4 x   (6,15)
1 x 2 3 x 4   <4+1=2+3>
1 4 2 x 3 x   (8,13)
1 x 2 4 3 x   (5,16)
1 x 2 x 3 4   (6,15)
1 5 2 x x 3   <10,10>
1 x 2 5 x 3   (6,14)
1 x 2 x 5 3   (6,14)
1 3 5 2 x x   (6,14)
1 3 x 2 5 x   (6,14)
1 3 x 2 x 5   (7,13)
1 4 3 2 x x   <1+4=3+2>
1 x 3 2 4 x   (7,14)
1 x 3 2 x 4   <3+2=4+1>
1 4 x 2 3 x   <1+4=2+3>
1 x 4 2 3 x   (7,14)
1 x x 2 3 4   <4+1=2+3>
1 5 x 2 x 3   (7,13)
1 x 5 2 x 3   (6,14)
1 x x 2 5 3   (6,14)
________________________________
Sesta fase
Considerato che nella quinta sono rimaste 26 stringhe buone, nella sesta
saranno 52 stringhe da esaminare:
1 2 4 5 8 11   <2+4+5=11>
1 2 4 5 11 8   <4+5=8+1>
........
1 2 5 4 6 13   OK
........
1 2 7 4 12 5   OK (questa mi era sfuggita)
1 2 12 4 7 5   <7+5=12>
........
ecc. ecc. ecc.
ciao
paolo

Ciao, Silv:o)
ciao
paolo

 Se ne sentiva la mancanza, dopo un periodo di stallo 
Vero. Visto le molte applicazioni, non vorrei abbandonarlo. In un tuo
post precedente facevi notare l'attinenza con i riduttori. Da un po' di
tempo leggiamo messaggi con richieste di metodi per generarli. anche su
questo NG. Non molto tempo fa ho tentato un approccio con un'idea che
poteva avere sviluppi. Ho ritrovato il msg. spedito ad un altro NG
rimasto senza risposte. Lo ripropongo qui col titolo "Riduttori"
:) dario

Silvio wrote:


PS. ho gia' spedito questo ed il seguente parecchie ore fa. Mi
perdonerete se arrivera' doppio.