Newsgroup: it.hobby.enigmi
Titolo: ATTORI

Memore del bel problema sui "block design" proposto tempo fa da Silvio
che fece accendere la discussione, provo con quest'altro di cui non
conosco risposte.
In una scuola di teatro ci sono n attori. Quando alcuni attori recitano
sul palco, i restanti fungono da spettatori. 
Quante recite occorrono perche' ciascun attore veda recitare almeno una
volta tutti gli altri ??
E' chiaro che e' sempre possibile in n recite, basta che ci sia un solo
spettatore per volta a turno.
Ho visto pero' che si puo' fare meglio. Ad es. con n=5 e' facile
riuscirci in 4 recite:
Numerando gli attori da 1 a 5
Palco   Platea
345     12
125     34
14      352
23      541
C'e' un metodo generale ?? quali sono i migliori risultati per 2<n<15 ??
:)dario

 :)dario
ciao
paolo

 Mailgate.ORG is maintained online by Dario Centofanti
--
Posted from 
HA-server-a.cs.interbusiness.it
 [151.99.250.31]
via Mailgate.ORG Server - 
http://www.mailgate.org


Ciao Paolo,come dicevo nel messaggio precedente,
senz'altro hai ragione nell'affermare che per
per n=2^k e' possibile in 2*k recite,
infatti R(16) = n/4 + 4 = 8.
Ma non e' il risultato migliore, infatti
R(15) = 15/5 +R(5) = 3 + 4 =7
Quando come in questo caso 15 e' divisibile esattamente per 5 possiamo
aggiungere un
attore senza problemi. chiamiamolo y Per cui R(16) = 7.
Palcoscenico                      Platea
6 7 8 9 10 11 12 13 14 15 y       1 2 3 4 5
1 2 3 4 5  11 12 13 14 15 y       6 7 8 9 10
1 2 3 4 5 6 7 8 9 10      y       11 12 13 14 15
questi sono i 3 quintetti
e ora seguono le 4 combinazioni che fanno si che gli spettatori si vedano
recitare.
3 4 5 8 9 10 13 14 15      1 2 6 7 11 12         y
1 2 5 6 7 10 11 12 15      3 4 8 9 13 14         y
2 3 7 8 12 13              1 4 6 9 11 14 5 10 15 y
1 4 6 9 11 14              2 3 7 8 12 13 5 10 15 y
In totale 7, ovviamente basterebbe indicare gli spettatori in Platea.
Ciao
Andrea


 pero' potrebbe essere una base di partenza.
Ottimo attacco !! (come sempre)
vedremo se ci saranno altri sviluppi.
ciao :)dario

 Ho esaminato un caso particolare: per n=2^k e' possibile in 2*k recite.
Dal tuo intervento e da quello di Andrea si vede chiaramente almeno una
cosa: abbiamo trovato un limite superiore asintotico al numero di
rappresentazioni, ed e' logaritmico rispetto al numero di attori.
Guardiamo la formula di Andrea, R(n)=n/x + R(x)
Credo che per n grandi convenga scegliere x=n/2, per cui
R(2*n)=2+R(n), che concorda in pieno con la tua.
C'e' un modo abbastanza simpatico per convincersi della correttezza della
cosa:
Supponiamo che per n attori maschi servano R(n) rappresentazioni. Se si
portano le mogli, allora basta che ogni moglie faccia esattamente quel che
fa il marito per vedere ed esser vista da tutti i colleghi del marito, e
dalle loro consorti. A questo punto basta organizzare due sole
rappresentazioni aggiuntive in cui i mariti guardano recitare le mogli, e
viceversa, per completare il programma.
Si puo' fare meglio che O(log n)?
Ciao, Silv:o)

 rappresentazioni, ed e' logaritmico rispetto al numero di attori.
Generalizziamo il metodo delle mogli:
Dividiamo gli n attori in a gruppi di b ciascuno.
Con R(a) rappresentazioni facciamo in modo che ogni gruppo veda e sia visto
dagli altri, con altri R(b) spettacoli facciamo in modo che i componenti dei
singoli gruppi si osservino l'un l'altro.
Quindi R(a*b)=R(a)+R(b)
Vi ricorda qualcosa?
Ciao, Silv:o)


Faccio solo notare se fosse R(n) = n/x + x derivando otterremmo cheil miglior
valore di x e' = sqrt(n).
Poiche' R(x) < x, in realta' sospetto che mentre inizialmente il valore
migliore per x sia sqrt(n), per n che tende ad infinito il limite di x sia
n/2.Ciao


 ciao :)dario
Ho trovato un buon metodo per n pari che mi rende alcuni
migliori risultati per n=6 e per n=8.
In particolare si tratta di dividere in due gli attori
per la prima Rappresentazione e di invertire i ruoli di tutti tranne
uno, secondo lo schema seguente :
n=6
   Palco  Platea
1) 123     456
2) 1..     4..
3) .2.     .5.
4) ..3     ..6
In tal modo si ottengono le seguenti (1+n/2) Rappresentazioni :
1) 123    456
2) 156    423
3) 426    153
4) 453    126
Esempio n=8
1) 1234   5678
2) 1678   5234
3) 5278   1634
4) 5638   1274
5) 5674   1238
Credo che per gli esempi indicati siano il massimo risultato,
premesso che il limite minimo e' R(n)=4.
Cmq negli altri casi ottengo valori equivalenti a valori gia
trovati oppure peggiori.
Saluti,
Massimo

 volta tutti gli altri ??
E se provassimo ad invertire il problema?
"Stabilito il numero R di recite, quale e' il max. numero N di attori?"
Inizio con una ulteriore *semplificazione*:
supponiamo che sia richiesto che ciascun attore debba vedere *OR* essere
visto da ciascun altro.
In questo caso il problema dovrebbe essere determinato, con Nmax=2^R
Attribuisco a ciascun attore un numero binario di R cifre, con la
convenzione che nella recita k_ma stanno sul palco gli attori con 0 in k_ma
posizione, e in platea quelli con 1 in k_ma posizione (per esempio, 5
recite, l'attore 11010 sta sul palco per la terza e la quinta recita).
La condizione *semplificata* si traduce con: tutti gli attori devono avere
numeri diversi.
Con i numeri da 0 [00000] a 2^R-1 [11111], presa una qualsiasi coppia di
attori i loro numeri differiscono per *almeno* un bit, quindi esiste almeno
una recita nella quale uno e' in platea ed uno sul palco.
Torniamo alla condizione originale: ciascun attore deve vedere *AND* essere
visto da ciascun altro.
Usando le stesse convenzioni, una prima condizione (necessaria) e':
Per una qualsiasi coppia di attori A,B, i numeri devono differire per almeno
due bit.
ma non basta, deve anche essere:
per almeno un bit sara' A=0, B=1, e per almeno un bit A=1, B=0.
A questo punto, ... non riesco ad andare avanti :-(((
ma, ... chissa', forse con questo approccio qualcuno riesce a trovare
qualcosa
di buono.
ciao a tutti
paolo

 per almeno un bit sara' A=0, B=1, e per almeno un bit A=1, B=0.
Caspita Paolo !
questa tua ultima osservazione e' formidabile.
Se nella stringa appaiono lo stesso numero di segni "1" , la condizione
e' gia' soddisfatta.
Ad es. considero 6 recite. Mi scrivo le C(6,3) = 20
1)  111000
2)  110100
3)  110010
4)  110001
5)  101100
6)  101010
7)  101001
8)  100110
9)  100101
10) 100011
11) 011100
12) 011010
13) 011001
14) 010110
15) 010101
16) 010011
17) 001110
18) 001101
19) 001011
20) 000111
Ora leggendo in verticale, metto l'attore con l'"1" sul palco con lo "0"
in platea (o viceversa):
Recita  Palco
Prima   1,2,3,4,5,6,7,8,9,10
Seconda 1,2,3,4,11,12,13,14,15,16
Terza   1,5,6,7,11,12,13,17,18,19
Quarta  2,5,8,9,11,14,15,17,18,20
Quinta  3,6,8,10,12,14,16,17,19,20
Sesta   4,7,9,10,13,15,16,18,19,20
Che per il principio da te osservato funziona perfettamente, permettendo
l'impiego di 20 attori con sole 6 recite. 
Funziona benissimo anche con un numero di recite dispari. Ad es. con 5, 
prendo lo schema del C(5,2)
e ottengo n=10:
Recita  Palco      Platea 
Prima   1,2,3,4    5,6,7,8,9,10
Seconda 1,5,6,7    2,3,4,8,9,10
Terza   2,5,8,9    1,3,4,6,7,10
Quarta  3,6,8,10   1,2,4,5,8,9
Quinta  4,7,9,10   1,2,3,5,6,8
Generalizzando, per massimizzare n, se R e' pari, prendiamo C(R,R/2) se
e' dispari C(R,R/2-1).
La tabella dovrebbe diventare:
n   R
2   2
3   3
6   4
10  5
20  6
35  7
70  8
126 9..... ecc. 
ciao a tutti :)dario