Vicini litigiosi
Vicini litigiosi
Ci sono 16 case; in quanti modi posso sistemare 4 vicini in modo che ogni vicino è distante dall'altro di almeno due case? Due sistemazioni che occupano le stesse case (ma variano i vicini che occupano quelle case) sono da considerarsi uguali.
Re: Vicini litigiosi
Sia $C_{l,n}$ il numero di modi di sistemare $l$ persone in $n$ case in modo che essi abbiano una distabza di almeno $2$ fra loro.
Chiaramente $C_{1,n}=n$.
Osserviamo che $C_{l,n}=C_{l,n-1}+C_{l-1,n-3}$, infatti nel mettere $l$ persone in $n$ case con quelle condizioni, abbiamo i casi in cui l'ultima è vuota che sono $C_{l,n-1}$, i casi in cui l'ultima è piena allora devo mettere altri $ l-1$, ma la casa $ n-1 $ e $ n-2 $ per le condizioni devono essere vuote... ne deriva la ricorsione.
$C_{2,n}=C_{2,n-1}+\max(0,n-3)$. Da cui facilmente
$C_{2,n}=1+2+...+(n-3)$ (esso è zero se tale quantità dovesse essere negativa).
$C_{3,n}=C_{3,n-1}+\binom{n-5}{2}$ con la convenzione che il binomiale è zero se il numero sotto è maggiore di quello di sopra (convenzione da applicare a tutti i binomiali anche nel resto della soluzione).
Quindi per n maggiori o uguali a 7:
$C_{3,n}=\sum_{i=7}^{n}\binom{i-5}{2}=\binom{2}{2}+...+\binom{n-5}{2}=\binom{n-4}{3}$
Se n minore di 7 allora $C_{3,n}=0$
Qui abbiamo usato una nota identità tra binomiali (se non la conosci te la linko: https://en.m.wikipedia.org/wiki/Hockey-stick_identity)
In modo analogo
$C_{4,n}=C_{4,n-1}+C_{3,n-3}=C_{4,n-1}+ \binom{n-7}{3}$
Per n maggiori uguali a 10:
$C_{4,n}=\sum_{i=10}^{n}\binom{i-7}{3}= \binom{3}{3}+...+\binom{n-7}{3}=\binom{n-6}{4}$, qui si usa la stessa identità di prima...
Quindi $C_{4,16}=\binom{10}{4}=210$. Che è ciò che cercavamo.
In generale $C_{l,n}=\binom{n-2(l-1)}{l}$, si può dimostrare per induzione su $ l$
Fammi sapere se ci sono cose poco chiare o errori
Chiaramente $C_{1,n}=n$.
Osserviamo che $C_{l,n}=C_{l,n-1}+C_{l-1,n-3}$, infatti nel mettere $l$ persone in $n$ case con quelle condizioni, abbiamo i casi in cui l'ultima è vuota che sono $C_{l,n-1}$, i casi in cui l'ultima è piena allora devo mettere altri $ l-1$, ma la casa $ n-1 $ e $ n-2 $ per le condizioni devono essere vuote... ne deriva la ricorsione.
$C_{2,n}=C_{2,n-1}+\max(0,n-3)$. Da cui facilmente
$C_{2,n}=1+2+...+(n-3)$ (esso è zero se tale quantità dovesse essere negativa).
$C_{3,n}=C_{3,n-1}+\binom{n-5}{2}$ con la convenzione che il binomiale è zero se il numero sotto è maggiore di quello di sopra (convenzione da applicare a tutti i binomiali anche nel resto della soluzione).
Quindi per n maggiori o uguali a 7:
$C_{3,n}=\sum_{i=7}^{n}\binom{i-5}{2}=\binom{2}{2}+...+\binom{n-5}{2}=\binom{n-4}{3}$
Se n minore di 7 allora $C_{3,n}=0$
Qui abbiamo usato una nota identità tra binomiali (se non la conosci te la linko: https://en.m.wikipedia.org/wiki/Hockey-stick_identity)
In modo analogo
$C_{4,n}=C_{4,n-1}+C_{3,n-3}=C_{4,n-1}+ \binom{n-7}{3}$
Per n maggiori uguali a 10:
$C_{4,n}=\sum_{i=10}^{n}\binom{i-7}{3}= \binom{3}{3}+...+\binom{n-7}{3}=\binom{n-6}{4}$, qui si usa la stessa identità di prima...
Quindi $C_{4,16}=\binom{10}{4}=210$. Che è ciò che cercavamo.
In generale $C_{l,n}=\binom{n-2(l-1)}{l}$, si può dimostrare per induzione su $ l$
Fammi sapere se ci sono cose poco chiare o errori
Re: Vicini litigiosi
Tutto chiaro, ma ho ancora un dubbio; il problema si può ricondurre a quanti numeri [math] tali che sia [math] e [math] sono tali che la loro somma sia 12, ossia quanti numeri [math] tutti [math] sono tali che la loro somma sia 6. La risposta è [math], ossia effettivamente [math]. Ma questi non dovrebbero essere i modi in cui si contano più volte anche sistemazioni uguali? Se le contassimo una sola volta, la risposta dovrebbe essere 22, che è visivamente sbagliata, eppure non riesco a capire il perché non si debba fare
Re: Vicini litigiosi
Ciao, se mi dici come hai dedotto ciò, magari posso aiutarti.
Edit: ho capito come lo hai ricavato... poi ti spiego
Re: Vicini litigiosi
Ok, ecco la spiegazione (in grassetto la parte che credo ti interessi di più):
Ordiniamo le case da sinistra verso destra. Chiaramente due configurazioni sono uguali se e solo se le case occupate sono le stesse (eventualmente anche da persone diverse). Siano $a,e$ il numero di case consecutive lasciate vuote da sinistra e da destra rispettivamente. Siano $b,c,d$ le distanze tra la casa 1 e 2, 2 e 3, 3 e 4. Chiaramente per le condizioni del testo $b,c,d \geq 2$ e $a,e \geq 0$, $a+b+c+d+e=12$. Ora una configurazione è determinata in modo biunivoco da $ a,b,c,d,e$. Infatti se qualcuno di questi numeri fosse diverso le case occupate sarebbero diverse... in particolare ad esempio una permutazione che non è un identità di una soluzione, porta a una soluzione diversa... quindi non c'è motivo di dividere il risultato per qualcosa. Quindi basta contare queste cinquine... e si arriva alla soluzione $\binom{10}{4}$.
Ordiniamo le case da sinistra verso destra. Chiaramente due configurazioni sono uguali se e solo se le case occupate sono le stesse (eventualmente anche da persone diverse). Siano $a,e$ il numero di case consecutive lasciate vuote da sinistra e da destra rispettivamente. Siano $b,c,d$ le distanze tra la casa 1 e 2, 2 e 3, 3 e 4. Chiaramente per le condizioni del testo $b,c,d \geq 2$ e $a,e \geq 0$, $a+b+c+d+e=12$. Ora una configurazione è determinata in modo biunivoco da $ a,b,c,d,e$. Infatti se qualcuno di questi numeri fosse diverso le case occupate sarebbero diverse... in particolare ad esempio una permutazione che non è un identità di una soluzione, porta a una soluzione diversa... quindi non c'è motivo di dividere il risultato per qualcosa. Quindi basta contare queste cinquine... e si arriva alla soluzione $\binom{10}{4}$.
Re: Vicini litigiosi
Ah certo, mi era sfuggito il fatto che permutando si arrivava a soluzioni diverse... grazie mille!
-
- Messaggi: 5
- Iscritto il: 03 apr 2024, 22:51
Re: Vicini litigiosi
Questo link spiega la formula: https://people.dm.unipi.it/lombardo/Tea ... izioni.pdfThoma(sinθ) ha scritto: ↑07 apr 2024, 20:53Perdonate l'ignoranza, come si contano le cinquine in questione in maniera veloce? Ovvero, come arriviamo al coefficiente binomiale 10 su 4?
Se le hai ci sono anche nelle schede del Gobbino.
Comunque ci si riconduce alle combinazioni con ripetizioni...
Prova a vedere, se hai dubbi fammi sapere
-
- Messaggi: 5
- Iscritto il: 03 apr 2024, 22:51
-
- Messaggi: 5
- Iscritto il: 03 apr 2024, 22:51
Re: Vicini litigiosi
Re: Vicini litigiosi
Prego, sì sono quelle le schede del Gobbino.