Corso Prime: Pb. 9.2

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
D.S.R.
Messaggi: 17
Iscritto il: 13 ott 2015, 01:49
Località: MI
Contatta:

Corso Prime: Pb. 9.2

Messaggio da D.S.R. » 25 ott 2015, 16:26

Salve, sto sbattendo la testa contro il seguente problema.
"In quanti modi diversi 6 persona possono sedersi attorno ad una tavola rotonda con 8 posti (non numerati)?
N.B. due configurazioni sono considerate la stessa se si possono ottenere con una rotazione.
Soluzione tentata
Mettere 6 persone in 8 posti è come posizionare 8 persone in 8 posti, solo che 2 sono fantasmi e sono come una nona persona ripetuta due volte, perché indistinguibili.
L'insieme S dei modi di posizionare è quindi:
\[
S=\frac{8!}{2!}.
\]
Ora qui arriva la parte in cui le cose si incasinano.
Individuo 5 classi:
  • Fantasmi a distanza 0: sono 6! e vanno divisi per 4.
  • Fantasmi a distanza 1: sono 6! e vanno divisi per 4.
  • Fantasmi a distanza 2: sono 6! e vanno divisi per 4.
  • Fantasmi a distanza 3: sono 6! e vanno divisi per 2.
  • Fantasmi a distanza 4: sono 6! e vanno divisi per 4.
Non so bene da dove ho tirato fuori sti affari, ma 4 e 2 sono il numero di casi diversi ottenibili con rotazioni. Ho dei dubbi sulla distanza 3.
Questo approccio mi sa tanto di sbagliato. Ho quindi poi tirato fuori somme e calcoli strani che non vale la pena di trascrivere. Quale è il modo giusto di approcciare questo tipo di problemi, in generale? Come ragionare, appunto, in generale?
Grazie in anticipo.
Ultima modifica di D.S.R. il 25 ott 2015, 22:52, modificato 1 volta in totale.
[math]

Luca Nalon
Messaggi: 20
Iscritto il: 03 lug 2015, 16:15

Re: Corso Prime: Pb. 9.2

Messaggio da Luca Nalon » 25 ott 2015, 17:04

In genere per fare conteggi devi cercare di trovare una corrispondenza biunivoca tra gli oggetti che vuoi contare e gli oggetti che sai contare bene (anagrammi, permutazioni, combinazioni...). A volte distinguere in casi come hai fatto tu è utile per semplificarsi il problema ed evitare di sbagliare trovando corrispondenze inesistenti, ma in questo caso sono superflue. Dopo $ S=8!/2! $ eri sulla buona strada.

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: Corso Prime: Pb. 9.2

Messaggio da Enigmatico » 25 ott 2015, 17:10

Allora, quando hai questi problemi devi ragionare così:
Ci sono $n$ posti e $m$ persone. Assegna ad ogni modo di sedersi una stringa di $n$ elementi con $n-m$ elementi uguali. Puoi, ora, calcolare i diversi modi di sedersi ($S$) considerando distinti quelli che differiscano per rotazione permutando gli elementi della stringa; $S=\frac{n!}{(n-m)!}$.
Però, il problema di chiede di calcolare i modi di sedersi a tavola a meno di rotazioni. Ora, se ci sono $n$ posti (e quindi $n$ punti di riferimento sul tavolo circolare) quante rotazioni puoi distinguere per disposizione? $n$. Pertanto, la soluzione cercata è $S^{*}=\frac{S}{n}=\frac{(n-1)!}{(n-m)!}$.

Avatar utente
D.S.R.
Messaggi: 17
Iscritto il: 13 ott 2015, 01:49
Località: MI
Contatta:

Re: Corso Prime: Pb. 9.2

Messaggio da D.S.R. » 25 ott 2015, 22:51

Grazie mille ragazzi.
Gobbino usa sempre un approccio che dall'insieme distingue il numero di oggetti per "classe" ed il numero totale diviso il numero di oggetti per classe è dunque la soluzione. Qui non era possibile, perché le classi non sono tutte uguali e quindi non posso dividere l'intero insieme $S$ per uno stesso numero.
Ho dunque tentato di enumerare a mano i "tipi" di classe, ma non ha funzionato.
Veniamo all'intervento di Luca, sembra che fosse possibile un approccio "per classe".
@Luca grazie per il tuo intervento. Capisco che trovare questa corrispondenza biunivoca è utile. La tua soluzione potrebbe andare nella direzione di tradurre in lettere? Potremmo trasformare il numero di posti in una "parola" con due spazi disponibili:
\[
\text{A B C D E F}\: \square\:\square
\]
E trovare i modi di di "rigirare" quelle 8 lettere (contiamo i box come lettere perché cambieranno di posizione e avranno significato) all'interno di quegli otto spazi. Vediamo...
\[
\text{Permutazioni tot.}=\frac{8!}{2!}.
\]
Ora ragioniamo un po'...dal momento che conta la posizione "relativa", allora facendo una "rotazione" cioè spostando ogni lettera di un posto a destra (l'ultima lettera andrà al primo posto) otteniamo il numero di permutazioni per ogni classe. Buttiamo un occhio:
\[
8\text{ permutazioni}
\begin{cases}
\text{A B C D E F}\:\square\:\square \\
\square\:\text{A B C D E F}\:\square \\
\square\:\square\:\text{A B C D E F} \\
\text{F}\:\square\:\square\:\text{A B C D E}\\
\text{E F}\:\square\:\square\:\text{A B C D}\\
\text{D E F}\:\square\:\square\:\text{A B C }\\
\text{C D E F}\:\square\:\square\:\text{A B}\\
\text{B C D E F}\:\square\:\square\:\text{A}\\
\end{cases}
\]
Dividiamo dunque le nostre permutazioni totali per il numero di permutazioni di ogni classe. Il numero di classi è in corrispondenza biunivoca con quello che stiamo cercando, è quello che stiamo cercando!
Procediamo:
\[
\text{Soluzione}=\frac{8!}{8\cdot2!}=2520.
\]
@Enigmatico grazie mille.
La tua soluzione è la stessa, non passa dall'enumerazione di ogni caso per capire quante permutazioni ha ogni classe...dice direttamente che questo numero è uguale al numero di punti di riferimento. Tutto ha ora senso, le pippe mentali sulla permutazione non ne avevano e complicavano.
Avrei dovuto passare direttamente al dividere per 8, senza perdermi in enumerazione di casi che "sarebbero simmetrici" anche perché le rotazioni non erano di $90°$, come stavo andando a vedere, e soprattutto perché i due "fantasmi" sono già stati presi come uguali dividendo per $2!$ l'$S$ di partenza.
Inoltre questo approccio definisce il caso generale. Molto comoda:
\[
S^{\ast}=\frac{S}{n}=\frac{(n-1)!}{(n-m)!}.
\]
---------------------
Era molto più semplice di quanto sembrasse!
[math]

Rispondi