Otto celebrità

[Claudio]

Si incontrano a un party. Accade che ogni celebrità stringe la mano
esattamente ad altre due. Un ammiratore tiene una lista di tutte le
coppie (non ordinate) di celebrità che si sono strette la mano.
Se l'ordine non conta, quante diverse liste sono possibili?

---
Questa e-mail è stata controllata per individuare virus con Avast antivirus.
https://www.avast.com/antivirus

[Kiuhnm Mnhuik]

On Thursday, December 31, 2015 at 7:03:05 PM UTC+1, Claudio wrote:
> Si incontrano a un party. Accade che ogni celebrità stringe la mano
> esattamente ad altre due. Un ammiratore tiene una lista di tutte le
> coppie (non ordinate) di celebrità che si sono strette la mano.
> Se l'ordine non conta, quante diverse liste sono possibili?

7!/2 + C(8,4)/2 (3!/2)^2 + C(8,3) 4!/2 = 3507

L'idea è che le persone possono formare:
1) un ciclo da 8
2) due cicli da 4
3) un ciclo da 5 e uno da 3

[Claudio]

Avevo pensato anch'io a risolverlo in questo modo, ma avevo sbagliato i
conti; il risultato giusto è quello che hai trovato tu.
Ho forse capito l'errore.
Vediamo se riesco a spiegare i procedimenti, come proverei a spiegarli
in classe:

Ciclo da 8 persone:
Il numero di sostituzioni D8,8 è 8!
Tuttavia l'insieme di queste sostituzioni si deve partizionare: ci sono
8 sostituzioni equivalenti: quindi 8!/8=7!
Questo numero rappresenta anche i modi in cui 8 persone posso sedersi
attorno ad un tavolo rotondo.
Poi si osserva che 7! comprende coppie di configurazioni equivalenti che
si ottengono percorrendo la catena in senso orario e senso antiorario. A
livello delle strette di mano è rilevante solo la presenza dei due
vicini della catena: quindi il numero è 7!/2 (mentre per il tavolo
rotondo sono due configurazioni distinte: B alla destra di A e C alla
sinistra di A e viceversa permutando B e C)

Ciclo da 4 persone:
Il numero di sottoinsiemi di 4 elementi ottenibili da un insieme di 8 è
C(8,4), numero delle combinazioni di 8 elementi di classe 4; siccome le
persone sono 8 l'altro insieme di 4 elementi è individuato;
considero una catena:
A-B
| |
C-D
prendendo A fisso ottengo altre configurazioni andando a scegliere i
primi vicini di A da un insieme di 3 elementi (B-C-D); ottengo C(3,2)=3
per la prima catena di 4 elementi e C(3,2) per la seconda catena di 4
elementi, quindi

C(8,4)*C(3,2)^2

Ciclo da 5 persone
Il numero di sottoinsiemi di 5 elementi è C(8,5)=C(8,3); il restante
insieme di 3 elementi è individuato e le strette di mano sono fisse in
questo caso. Considerando un elemento A della catena di 5 persone posso
permutare le restanti 4 persone in 4! modi possibili; Al solito si
osserva che 4! comprende coppie di configurazioni equivalenti che si
ottengono percorrendo la catena in senso orario e senso antiorario.
Quindi C(8,3) * 4!/2

Oppure:
Considerando un elemento A della catena di 5 persone i vicini di A
possono essere scelti in C(4,2) modi: numero di sottoinsiemi di 2
elementi ottenibili da un insieme di 4; le altre due persone della
catena di 5 possono scambiarsi originando altre 2 configurazioni; quindi:

C(8,3) * C(4,2) * 2

Grazie
Claudio

[Kiuhnm Mnhuik]

On Friday, January 1, 2016 at 9:56:08 AM UTC+1, Claudio wrote:
> Avevo pensato anch'io a risolverlo in questo modo, ma avevo sbagliato i
> conti; il risultato giusto è quello che hai trovato tu.
> Ho forse capito l'errore.
> Vediamo se riesco a spiegare i procedimenti, come proverei a spiegarli
> in classe:
>
> Ciclo da 8 persone:
> Il numero di sostituzioni D8,8 è 8!
> Tuttavia l'insieme di queste sostituzioni si deve partizionare: ci sono
> 8 sostituzioni equivalenti: quindi 8!/8=7!
> Questo numero rappresenta anche i modi in cui 8 persone posso sedersi
> attorno ad un tavolo rotondo.
> Poi si osserva che 7! comprende coppie di configurazioni equivalenti che
> si ottengono percorrendo la catena in senso orario e senso antiorario. A
> livello delle strette di mano è rilevante solo la presenza dei due
> vicini della catena: quindi il numero è 7!/2 (mentre per il tavolo
> rotondo sono due configurazioni distinte: B alla destra di A e C alla
> sinistra di A e viceversa permutando B e C)

Altro modo: si scelgono in C(7,2) modi due persone P2,P3 a cui P1 stringe la mano; si sceglie una persona per P2 in 5 modi e una per P3 in 4 modi e così via fino a completamento ciclo. Si ottiene C(7,2) 5! = 7!/2.
In generale si ha (n-1)!/2, n>2.

> Ciclo da 4 persone:
> Il numero di sottoinsiemi di 4 elementi ottenibili da un insieme di 8 è
> C(8,4), numero delle combinazioni di 8 elementi di classe 4; siccome le
> persone sono 8 l'altro insieme di 4 elementi è individuato;
> considero una catena:
> A-B
> | |
> C-D
> prendendo A fisso ottengo altre configurazioni andando a scegliere i
> primi vicini di A da un insieme di 3 elementi (B-C-D); ottengo C(3,2)=3
> per la prima catena di 4 elementi e C(3,2) per la seconda catena di 4
> elementi, quindi
>
> C(8,4)*C(3,2)^2

E' C(8,4)/2 perché devi calcolare le bipartizioni. In altre parole, scegliere P1,P2,P3,P4 per il primo gruppo è uguale a scegliere P5,P6,P7,P8, quindi devi dividere per 2.

[Claudio]

Il 01/01/2016 14:17, Kiuhnm Mnhuik ha scritto:

>
> E' C(8,4)/2 perché devi calcolare le bipartizioni. In altre parole,
> scegliere P1,P2,P3,P4 per il primo gruppo è uguale a scegliere
> P5,P6,P7,P8, quindi devi dividere per 2.
>

Ho capito: Il numero di sottoinsiemi di 4 elementi ottenibile da uno di
8 è il doppio di quelli necessari:
A-B-C-D mi individua anche E-F-G-H

ma in C(8,4) mi individua anche E-F-G-H come sottoinsieme che è già
individuato come insieme differenza

Ok, grazie