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

Un corso di lingue prevede l'utilizzo di un laboratorio, che puo' ospitare
10 persone per volta. Durante il corso il laboratorio viene utilizzato 40
volte, sempre con tutte le postazioni occupate, e mai due studenti si sono
incontrati piu' di una volta in laboratorio. Qual e' il minimo numero di
studenti che permette tutto cio'?
Ciao, Silv:o)

Ciao, Silv:o)
Ho trovato una soluzione con 100 persone; non so se sia vicina al minimo o
molto distante.
Si puo' comunque dimostrare che le persone non possono essere meno di 55.
infatti:
il primo giorno ci sono 10 persone;
il secondo giorno, al max 1 puo' essere scelta tra i presenti del giorno
precedente, quindi almeno 9 saranno nuove;
il terzo giorno ne posso scegliere non piu' di 2 tra i precedenti, e almeno
8 devono essere nuove;
...
il decimo giorno almeno 1 persona sara' nuova;
quindi nei primi 10 giorni devono partecipare almeno
10+9+...+2+1=55 persone.
 ed ecco la mia soluzione con 100 persone:
v
v
v
v
v
v
v
v
v
v
v
numero le persone da 00 a 99;
costruisco 4 matrici 10*10, dove ciascuna riga indica un giorno:
nella prima matrice (prima decade) scrivo i 100 numeri consecutivamente:
nella seconda matrice ripeto la prima colonna tale e quale, e in ogni altra
casella riporto il valore di quella a sinistra incrementato di 11
(sottraendo 100 se supero 99)
la terza e la quarta sono uguali alle prime due, invertendo le righe con le
colonne.
00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
00 11 22 33 44 55 66 77 88 99
10 21 32 43 54 65 76 87 98 09
20 31 42 53 64 75 86 97 08 19
30 41 52 63 74 85 96 07 18 29
40 51 62 73 84 95 06 17 28 39
50 61 72 83 94 05 16 27 38 49
60 71 82 93 04 15 26 37 48 59
70 81 92 03 14 25 36 47 58 69
80 91 02 13 24 35 46 57 68 79
90 01 12 23 34 45 56 67 78 89
00 10 20 30 40 50 60 70 80 90
01 11 21 31 41 51 61 71 81 91
02 12 22 32 42 52 62 72 82 92
03 13 23 33 43 53 63 73 83 93
04 14 24 34 44 54 64 74 84 94
05 15 25 35 45 55 65 75 85 95
06 16 26 36 46 56 66 76 86 96
07 17 27 37 47 57 67 77 87 97
08 18 28 38 48 58 68 78 88 98
09 19 29 39 49 59 69 79 89 99
00 10 20 30 40 50 60 70 80 90
11 21 31 41 51 61 71 81 91 01
22 32 42 52 62 72 82 92 02 12
33 43 53 63 73 83 93 03 13 23
44 54 64 74 84 94 04 14 24 34
55 65 75 85 95 05 15 25 35 45
66 76 86 96 06 16 26 36 46 56
77 87 97 07 17 27 37 47 57 67
88 98 08 18 28 38 48 58 68 78
99 09 19 29 39 49 59 69 79 89
ciao
paolo

Si puo' comunque dimostrare che le persone non possono essere meno di 55.
Il problema io l'ho trovato con la domanda "dimostrare che sono necessarie
piu' di X persone", dove X era piu' alto del tuo 55, e seguiva poi la
dimostrazione (peraltro semplice, dopo averla letta ;) che X persone non
bastano. Non c'era pero' assolutamente nulla di costruttivo, tantomeno un
piano coerente di prenotazioni del laboratorio. Provero' a a costruirne uno
con un numero di allievi il piu' vicino possibile ai teorici X+1, anche se
il fatto che ti sei lasciato un margine cosi' ampio mi fa temere per la
complesita' dell'impresa. Intanto prova a ritoccare il limite teorico.
Ciao, Silv:o)

Ciao, Silv:o)
ciao
paolo


Non so se il procedimento è giusto, io ci provo...
In un gruppo di n persone, nascono n*(n-1)/2 coppie.
Se il numero totale di persone è m, vi sono m*(m-1)/2 coppie possibili
Se si possono prendere q gruppi di n persone da un totale di m tale che non vi
siano coppie ripetute, bisognerà che
(m*(m-1)/2) >= q*(  n*(n-1)/2 )
nel nostro caso m*(m-1)/2 >= 40*(10*9/2)=1800
risolvendo si trova che il numero minimo m (intero) vale 61
Sarà vero? Mah!
--
Gabriele Cannata
g.ca...@bo.nettuno.it

 approfondendo l'analisi, si possa dimostrare almeno per X=79.
Il limite dimostrato nel problema era solo 60! (semplice esclamazione, non
e' un fattoriale :)
Si basava sul fatto che con 60 allievi si possono formare solo C(60,2)=1770
coppie, mentre in 40 sessioni di laboratorio si formano 40*C(10,2)=1800
coppie, per cui ci vogliono almeno 61 allievi (1830 coppie) per avere
qualche speranza di non ripetere nessun accoppiamento.
Vedo che sei andato molto piu' in la', stasera guardo meglio la tua proposta
e ci ragiono su' ...il discorso delle PM mi pare interessante.
Ciao, Silv:o)

 Sarà vero? Mah!
Ottimo. Questo e' quello che il problema originale stabiliva, ma mi pare che
Paolo abbia gia' innalzato il tetto di diverse unita'... staremo a vedere.
Ciao, Silv:o)

 >
L'ho guardato solo adesso.
Questi problemi di set designer sono duri da masticare. Viene in aiuto
il vecchio sistema del disco rotante.
Non ho bene verificato, ma mi sembra si possa agevolmente con 63 persone
organizzare 42 lezioni.
Guardo meglio ed eventualmente posto il metodo.
:) dario

 Guardo meglio ed eventualmente posto il metodo.
Ho guadrato meglio e .... ho detto una cacchiata !. 
Mettiamo attorno ad un cerchio i numeri da 1 a 96, che rappresentano 96
persone. Su un disco di cartoncino, dello stesso diametro del cerchio,
segnamo 10 tacche in corrispondenza dei numeri
1,2,4,8,13,21,31,45,60,76.
Ruotando il cartoncino, diciamo in senso orario per 96 volte, le tacche
individueranno 96 sequenze di 10 numeri ciascuna dove nessuna coppia
sara' ripetuta. Perche'?
Perche' i lati del decagono disegnato sul cartoncino sono scelti in modo
che nessuno sia la somma di k altri adiacenti. Mi spiego meglio.
Le distanze dei numeri scelti ad ogni turno, (lati del decagono)si
generano cosi':
Dai numeri naturali prendo 1, poi 2, (cancello il 3=2+1) il prossimo
numero disponibile e' il 4(cancello 4+2=6 e 4+2+1=7) il prossimo numero
disponibile e' il 5... e cosi' via. In questo modo avro' un decagono coi
lati (considerando come unita' l'arco che divide 2 numeri adiacenti) di
1,2,4,5,8,10,14,15,16,21.  Proprio per come sono scelti i lati del
decagono in qualnque posizione venga ruotato intercetta una decade di
numeri dove non ci possono essere coppie doppie. A questo punto possiamo
generare le 96 sequenze senza costruire l'aggeggio descritto, basta
pensare che ad ogni scatto i numeri si incremantano di 1:
a) 1,2,4, 8,13,21,31,45,60,76
b) 2,3,5, 9,14,22,32,46,61,77
c) 3,4,6,10,15,23,33,47,62,78
d) 4,5,7,11,16,24,34,48,63,79
.......
Per 96 volte, il tutto mod96.
Dato che in questo modo con 96 persone posso organizzare 96 lezioni
invece di 40 come richiesto dal problema, mi pare si possa trovare un
decagono con lati piu' corti e percio' meno persone, ci saranno
inevitabilmente delle sequenze con coppie ripetute che devono essere
eliminate, l'importante che ne restino almeno 40. Ed e' qui che ho preso
il granchio. Mi sembrava di farcela con un decagono con lati piu'
piccoli e 63 persone, ma il numero di coppie presenti 2 volte e' troppo
elevato. Vado avanti con l'indagine.
:)dario

Paolo Licheri dice


Passo dopo passo, porto il limite a X=73, poi a X=80 quindi a X=81
(presenze necessarie 74,81,82).
73) Il fatto e' che il mio calcolo precedente conteneva un errore; infatti
se B non era presente nel primo gruppo, nel secondo e' da considerare come
nuovo; quindi il secondo gruppo dovra' avere almeno 18+1 persone, che
sommate
alle 55 del primo formano 74 persone necessarie.
80) L'organizzatore del laboratorio prepara uno schema delle presenze
(matrice
40*10), scrivendo in ciascuna casella, accanto al nome del partecipante, il
numero di presenze prenotate (importante per stabilire le rette da
pagare:-).
Supponiamo che ci siano 80 persone. Con le 400 presenze risulta una
presenza media PM=400/80=5.
Come prima ipotesi suppongo che ciascuno debba essere presente esattamente 5
volte.
Il primo giorno si incontrano 10 persone; ciascuna di esse, nei giorni
successivi, dovra' essere presente altre 4 volte, e, dal momento che non si
possono piu' incontrare, dovranno impegnare quaranta giorni diversi, contro
i 39 ancora disponibili.
Supponiamo ora che le presenze non siano ripartite uniformemente (per
esempio qualcuno puo' averne 6 e qualcuno 4).
Nel primo caso questi numeri sarebbero tutti 5, ora potremo avere alcuni 4
ed alcuni 6, ecc.
***Ora devo fare un passaggio che non riesco a dimostrare, ma mi sembra
intuitivo e verificabile con alcuni esempi. Qualcuno vorrebbe verificare se
e' giusto?***
In questo caso la situazione risulta peggiorata rispetto alla
distribuzione uniforme, quindi in qualche riga la somma dei numeri (pari a
50 nel primo caso) dovra' essere maggiore di 50.
Notiamo che possiamo scambiare a piacere le righe, senza modificare i
terminidel problema.
Scelto allora come *primo giorno* uno in cui la somma sia non minore di 50,
i dieci presenti dovranno totalizzare ulteriori 40 presenze, e ricadiamo nel
caso precedente.
81)
E' una estensione del caso precedente.
I dieci presenti il primo giorno dovranno totalizzare altre 39 presenze,
quindi in media 3.9+1=4.9
Divido le presenze totali per questo valore
400/4.9=81.6
sarebbero quindi necessarie 81.6, cioe' 82 persone.



Alcune considerazioni alzano già il numero minimo:
Se avessimo 7 persone in totale da raggruppare in gruppi da 3, avremmo 21 / 3 = 7
possibili gruppi senza coppie ripetute. Questi gruppi sono:
124
235
346
457
561
672
713
Intuitivamente: si parte dalle potenze di 2 e si procede incrementando mod 7.
Analogamente con gruppi di 5 , per saturare le coppie mi servono 31 persone
1 2 4 8 16
2 3 5 9 17
.
.
31 1 3 7 15
Fare gruppi di dieci implica aggiungere altre 31 persone:
1 2 4 8 16    32 33 35 39 47
2 3 5 9 17    33 34 36 40 48
.
.
31 1 3 7 15    62 32 34 38 46
(Il secondo contingente è uguale al primosommato di 31)
Sfortunatamente siamo ancora a 31 lezioni invece di 40 e abbiamo già superato di 1
il minimo 61.
Nei gruppi seguenti i numeri 1-62 non possono più essere usati nello stesso gruppo
perchè le coppie possibili tra i numeri 1-62 sono tutte usate. Per convincersi di
ciò, se si è convinti che nelle prime 5 colonne vi sono tutte le coppie (1-31),
basta pensare che ogni numero quando è accoppiato ad x, è accoppiato anche a x+31.
Come formare altri 9 gruppi?
Usando tre serie del tipo 1  2 4 e colmando l'ultima colonna con 1-7 (che non sono
mai stati accoppiati con questi nuovi 63-83):
63 64 66   70 71 73   77 78 80  1
.
.
69 63 65   76 70 72   83 77 79  7
Siamo a 83 persone e a solo 38 gruppi!
Come riempire le ultime due righe? Possiamo usare due coppie del tipo:
8 63
9 64
Ma rimangono 16 "posti" da occupare e non si possono usare i numeri 1-83 perchè
sarebbero già accoppiati.
Non vedo altra soluzione che usare 16 numeri nuovi.
Il che porta il limite a 83+16=99!
Ditemi che sbaglio!
--
Gabriele Cannata
g.ca...@bo.nettuno.it

 se si è convinti che nelle prime 5 colonne vi sono tutte le coppie (1-31)
...
Qui mi pare che ci sia un errore.
Consideriamo 
p.es
. il numero 1:
appare 5 volte, in 5 colonne diverse, ogni volta accoppiato con 4 numeri
diversi;
complessivamente e' accoppiato con 20 numeri, e ci devono essere altri 10
che non l'hanno mai incontrato.
Quindi esistono coppie utilizzabili nei gruppi seguenti
In conclusione, hai costruito una tabella con 99 persone (migliorando la mia
di 100 persone), ma mi pare che non sia ancora dimostrato che questo valore
sia il minimo, anzi che sia dimostrato che si puo' ancora migliorare.
ciao
paolo

 sia il minimo, anzi che sia dimostrato che si puo' ancora migliorare.
Soprattutto mi interesserebbe trovare una soluzione "logica" non di forza bruta,
ad esempio usando un calcolatore.
--
Gabriele Cannata
g.ca...@bo.nettuno.it

 Intuitivamente: si parte dalle potenze di 2 ...
Se guardi il metodo di Dario ti accorgi che fa la stessa cosa del tuo, ma e'
ottimizzato.
Infatti la sequenza 1,2,4,8,16,(32=1) e' tale che ogni cifra non e' mai
somma di una stringa precedente, ed e' facilissima da generare, ma la
sequenza 1,2,4,8,13,(21=1) che suggerisce Dario fa la stessa cosa con meno
numeri (20, che fortunatamente e' la meta' delle lezioni richieste)
Da qui in poi torno al tuo metodo, ovvero raddoppio le colonne, e poi
raddoppio le righe: con 80 numeri me la dovrei cavare.
 1, 2, 4, 8,13 | 21,22,24,28,33
 2, 3, 5, 9,14 | 22,23,25,29,34
.            . : .            .
20, 1, 3, 7,12 | 40,21,23,27,32
---------------+---------------
41,42,44,48,53 | 61,62,64,68,73
42,43,45,49,54 | 62,63,65,69,74
.            . : .            .
60,41,43,47,52 | 80,61,63,67,62
Dato che ho 4 blocchi indipendenti, spero che mischiando un po' le coppie si
possa migliorare...
Ciao, Silv:o)

 .) 54,55,57,61,66,74,84, 2,17,33
La coppia 1,60 (ma anche la 2,61 ecc.) e' presente due volte!!! infatti il
decagono ha due sequenze (5+8+10+14 e 16+21) lunghe 37
Ciao, Silv:o)

 numeri (20, che fortunatamente e' la meta' delle lezioni richieste)
Purtroppo non funziona, anche perche' avrei trovato una copertura miracolosa
(20 numeri generano 190 coppie distinte, con le quali pretendo di coprire 20
gruppi da 5 (10 coppie ciascuna, 200 in totale) senza ripetizioni.
Ciao, Silv:o)

 con la numerazione "ottimizzata" proposta da Dario
Secondo me dovremmo guardare alle "distanze"
in 31 numeri, le coppie possono essere classificate secondo le distanze (es
[1,2] distanza 1, [4,6] distanza 2 ecc.]
Con 31 numeri ci sono 31 coppie a distanza 1, 31 coppie a distanza 2, ecc
per un totale di 15*31=465 coppie.
(Le distanze vanno calcolate modulo 15).
Ora, prendendo come gruppo generatore 0,1,3,7,15 (inizio da 0 invece che da
1 perchè così posso usare il modulo) vedo che le coppie generate sono a
distanza 1,2,3,4,6,7,8,12,14,15 quindi facendo i 31 gruppi saturo tutte le
coppie di tali categorie. Rimangono le coppie a distanza 5,9,10,11,13 che
dovrebbero essere presenti tutte (e sole) due volte in un gruppo di dieci
numeri, il che è chiaramente impossibile (es 11 e 13 implicano un'altra
distanza 2).
Se si riuscisse a trovare una configurazione di distanze tali che dieci sono
in un gruppo e le altre cinque in un altro gruppo allora si dovrebbe
arrivare alla soluzione.
Purtroppo dovrei anche cercare di laurearmi, quindi vi prego, ditemi quante
persone partecipano al corso o la settimana prossima lo chiedo alla
commissione!
--
Gabriele Cannata
g.ca...@bo.nettuno.it

:)dario
ciao
paolo

possa migliorare...
Attenzione, mi sembra che stiamo prendendo un abbaglio, prima Gabriele, poi
ci sono cascato io, poi Silvio.
Se il tuo ragionamento fosse giusto, sarebbe smentita la mia dimostrazione
dell'impossibilita' di 80. Non ci sarebbe niente di strano, ma....
In primo luogo mi pare che due blocchi affiancati non si possano considerare
indipendenti; allora troviamo la coppia 2-22 nelle prime due righe (2-33
nella versione di Gabriele), 1-21 nella prima e nella ventesima, ecc.
Bisognerebbe cercare di ovviare a cio' con spostamenti di righe, ma non sono
sicuro che sia possibile.
In secondo luogo, la mia dimostrazione, adattata a una matrice 5*20,
dimostrerebbe l'impossibilita' di riempirla con 20 persone.
Verifichiamo, sviluppando il primo blocco:
troviamo alcune coppie ripetute, per esempio, tra quelle della prima riga
trovo 13-2 nella decima e 13-4 nella dodicesima. Nella versione di Gabriele,
con il 16, trovo 16-4 nella nona riga e 16-2 nella quindicesima.
Che ne dite?


costruisco 4 matrici 10*10, dove ciascuna riga indica un giorno:
Possibile che nessuno si sia acccorto che la terza e la quarta matrice sono
identiche?
Non riesco a capire ho fatto a non vederlo subito.
Merito una penitenza :-(((
mi asterro' da qualsiasi intervento sul ng, almeno...per due ore :-)))
ciao
paolo


Anch'io ho scritto un emerita...sciocchezza, come tu mi hai giustamente fatto
notare in un tuo post.
Il fatto č che la mia algebra č molto arruginita e questo problema sembra
aggredibile da piů punti di vista.
Ad esempio il post sul regolo circolare l'ho appena letto, eppure stavo
cominciando ad usare una cosa simile.
Effettivamente non lo vedevo come regolo ma come gruppo.
Ma non č che siamo sulla strada sbagliata? Vabbč, il regolo co permette di
effettuare coperture perfette per alcuni n e m, ma se il numero di corsi e di
postazioni non soddisfano certe caratteristiche, gli altri punti vanno colmati
in altre maniere. Forse si dovrebbe fare un puro discorso combinatorio? Mah.
--
Gabriele Cannata
g.ca...@bo.nettuno.it

 >Ho trovato una soluzione con 100 persone...
Avevo appena scorso il tuo post. Ero convinto tu avessi ricavato le 40
lezioni semplicemente prendendo dalla matrice 10*10 i 4 settori:
 a) 10 colonne 
 b) 10 righe 
 c) 10 diagonali spezzate \
 d) 10 diagonali spezzate /
Dove ciascun allievo presenzia 4 lezioni.
Ecco perche' ho provato una 9*9 con 4 allievi jolly che, integrando
ciascuno un intero settore, con 9 presenze alzano la media. Arriviamo
pero' solo a 36, sto guardando per le 4 mancanti come fare, con la
massima economia.
:)dario

 in altre maniere. Forse si dovrebbe fare un puro discorso combinatorio?
Mah.
Effettivamente il problema si presta all'utilizzo di strumenti diversi
(Dario usando un metodo di Paolo e' riuscito a tirare in ballo pure il
problema delle otto regine!), ma solo perche' e' un problema di set
covering, (e nella formulazione piu' ardua, l'ottimizzazione), che credo sia
computazionalmente abbastanza pesante da affrontare (complessita' piu' che
polinomiale?), e quindi la speranza e' quella di trovare qualche buona
euristica, o metodi di ottimizzazione locale, partendo da soluzioni
accettabili.
Per quanto riguarda il discorso combinatorio, credo che gie' per n
abbastanza piccoli i numeri in gioco siano intrattabili, quando cominciamo a
perderci nelle varie disposizioni di combinazioni di...
Tra l'altro il problema mi pare simile al problema noto ai giocatori di
SuperEnalotto e concorsi vari, dei sistemi a garanzia di vincita di
categoria prefissata. Qui e' come se volessimo giocare 40 sistemi da 10
numeri garantendo... al massimo un ambo! Non mi pare una grande giocata, ma
le analogie restano.
Ciao, Silv:o)

:)dario
ciao
paolo


La definizione di determinante di matrice (la definizione, non l'algoritmo
per calcolarlo) tira in ballo tutte le possibili combinazioni di elementi
ognuno preso da una riga diversa.
E' noto che per le matrici 3*3 esiste l'algoritmo di Kramer (quello usato per
risolvere i sistemi) che usa appunto le diagonali.
Non so quanto c'entri, io l'ho buttata lě.
--
Gabriele Cannata
g.ca...@bo.nettuno.it