Scegliere elementi distanti
Siano $n$, $k$ e $j$ interi, con $n$ e $k$ positivi, $j$ non negativo.
In quanti modi posso scegliere $k$ elementi dall'insieme degli interi compresi tra $1$ e $n$ (inclusi) in modo tale che la differenza tra due elementi qualsiasi che ho scelto sia sempre almeno $j$?
In quanti modi posso scegliere $k$ elementi dall'insieme degli interi compresi tra $1$ e $n$ (inclusi) in modo tale che la differenza tra due elementi qualsiasi che ho scelto sia sempre almeno $j$?
Risposte
Qualcosa mi sfugge: cos'è $j$? Se, come sembra, è un errore di digitazione per $k$, la risposta mi sembra un po' troppo ovvia. Inoltre è sottinteso che anche questi numeri siano interi? E i due elementi scelti devono essere diversi fra loro?
Uhm, ho cambiato un po' il testo, spero ora sia più chiaro.
In ogni caso, perché se $j=k$ la risposta ti sembra ovvia?
In ogni caso, perché se $j=k$ la risposta ti sembra ovvia?
Il mio ragionamento si basava su un'interpretazione del testo completamente diversa da quella che tu intendevi dargli; inutile sprecarci tempo.
Mi pare di capire che ora si intenda che $j$ è un numero prefissato e la risposta vada data al variare di $j$.
Supponiamo però che sia $j=1$: tutti gli elementi dell'insieme dato distano fra loro di almeno 1: si deve intendere che $k=100$ e che c'è una sola risposta? Oppure che $k$ può assumere qualsiasi valore fra 2 e 100 e che la risposta è la somma di tutte le combinazioni possibili?
E, già che ci siamo, si può accettare $k=1$, che non permette di calcolare differenze?
Mi pare di capire che ora si intenda che $j$ è un numero prefissato e la risposta vada data al variare di $j$.
Supponiamo però che sia $j=1$: tutti gli elementi dell'insieme dato distano fra loro di almeno 1: si deve intendere che $k=100$ e che c'è una sola risposta? Oppure che $k$ può assumere qualsiasi valore fra 2 e 100 e che la risposta è la somma di tutte le combinazioni possibili?
E, già che ci siamo, si può accettare $k=1$, che non permette di calcolare differenze?
"giammaria":
Mi pare di capire che ora si intenda che $ j $ è un numero prefissato e la risposta vada data al variare di $ j $.
Supponiamo però che sia $ j=1 $: tutti gli elementi dell'insieme dato distano fra loro di almeno 1: si deve intendere che $ k=100 $ e che c'è una sola risposta? Oppure che $ k $ può assumere qualsiasi valore fra 2 e 100 e che la risposta è la somma di tutte le combinazioni possibili?
E, già che ci siamo, si può accettare $ k=1 $, che non permette di calcolare differenze?
Credo di aver capito che nel momento in cui esegui il conteggio sia $n$, sia $k$ sia $j$ sono prefissati. Ma chiaramente a priori possono variare tutti e $3$ xD Cioè è una funzione del tipo $f(n,k,j) \rightarrow$ risultato
Con $j=1$ va bene qualunque scelta e il risultato è \(\binom{n}{k}\) visto che si tratta semplicemente di prendere $k$ elementi a caso da un insieme di $n$ elementi. E volendo penso che va bene pure $j=0$ con cui uno stesso elemento può pure essere preso più volte ottenendo le combinazioni con ripetizione \(\binom{n+k-1}{k}\)
(Interessante notare come sia combinazioni semplici, sia combinazioni con ripetizione sono solo un sottocaso di questo problema
)Con $k=1$ puoi prendere un solo elemento qualsiasi quindi il risultato è $n$.
Volendo con $k=0$ credo che il risultato sia sempre $1$.
Nel caso generale dovrebbe esserci una soluzione bella e veloce che però ho trovato solo dopo aver già calcolato il risultato per ricorrenza
Ok, steph ha capito quello che intendevo: bisogna dire, al variare di $n$, $k$, $j$ quanto vale la quantità che ho chiesto.
Poi confermo che con $k=1$ si può prendere qualsiasi elemento e la risposta sarebbe $n$ (come è stato detto).
Infine con $j=0$ si può scegliere più volte anche lo stesso elemento.
Spero ora che sia chiaro tutto.
Poi confermo che con $k=1$ si può prendere qualsiasi elemento e la risposta sarebbe $n$ (come è stato detto).
Infine con $j=0$ si può scegliere più volte anche lo stesso elemento.
Spero ora che sia chiaro tutto.
Il caso \(\displaystyle j=0 \) l'ha gia fatto Steph ed è \(\displaystyle \binom{n+k-1}{k} \)
Anche quello \(\displaystyle j=1 \)
D'ora in poi \(\displaystyle j \ge 2 \). Consideriamo una fila di posti al cinema lunga \(\displaystyle n \) (ormai è un metodo standard ), ai lati di questa fila (a destra e a sinistra) posizioniamo altre due file lunghe \(\displaystyle j \) con i posti più esterni riservati ai registi.
In pratica una cosa di questo tipo:
\( R _ _ ... _ _ _ _ _ _ ...._ _ _ _ _ _ ... _ _ R \),dove gli R sono i registi, la fila centrale è lunga n, le laterali j (registi compresi)
Dobbiamo assegnare un posto a \(\displaystyle k \) spettatori, di conseguenza rimarranno \(\displaystyle 2(j-1)+n-k \) posti liberi, si sa che prendendo una coppia qualsiasi di esseri umani, essi devono avere almeno \(\displaystyle j-1 \) posti liberi tra di loro, dunque gli spettatori potranno essere posizionati solo nella fila da n posti e il numero di sequenza di posti vuoti sara \(\displaystyle k+1 \). Arrivati a questo punto possiamo vedere il problema come "in quanti modi possiamo ottenere il numero \(\displaystyle 2(j-1)+n-k \) come somma di \(\displaystyle k+1 \) interi maggiori o uguali di \(\displaystyle j-1 \)?"
Cioè \(\displaystyle x_1+x_2+...x_{k+1}=2(j-1)+n-k \) con \(\displaystyle x_i \ge j-1 \).
Qui uso una "tecnica" classica: sottraggo ad ogni \(\displaystyle x_i \) j-1 cosi da ottenere \(\displaystyle x_1+x_2+...x_{k+1}=2(j-1)+n-k-(k+1)(j-1)=(1-k)(j-1)+n-k \) con \(\displaystyle x_i \ge 0 \) (in pratica nel problema originario tolgo in blocco \(\displaystyle j-1 \) posti da ogni sequenza di posti liberi, e lo posso fare, visto che noi andiamo a contare il numero di posti in piu a j-1 per ogni sequenza).
Quindi in quanti modi posso partizionare il numero \(\displaystyle (1-k)(j-1)+n-k \) come somma ordinta di \(\displaystyle k+1 \) numeri naturali?
\(\displaystyle \binom{(1-k)(j-1)+n-k+ k}{k}=\binom{(1-k)(j-1)+n}{k} \)
Spero di non essermi perso qualcosa.
Anche quello \(\displaystyle j=1 \)
D'ora in poi \(\displaystyle j \ge 2 \). Consideriamo una fila di posti al cinema lunga \(\displaystyle n \) (ormai è un metodo standard
), ai lati di questa fila (a destra e a sinistra) posizioniamo altre due file lunghe \(\displaystyle j \) con i posti più esterni riservati ai registi.In pratica una cosa di questo tipo:
\( R _ _ ... _ _ _ _ _ _ ...._ _ _ _ _ _ ... _ _ R \),dove gli R sono i registi, la fila centrale è lunga n, le laterali j (registi compresi)
Dobbiamo assegnare un posto a \(\displaystyle k \) spettatori, di conseguenza rimarranno \(\displaystyle 2(j-1)+n-k \) posti liberi, si sa che prendendo una coppia qualsiasi di esseri umani, essi devono avere almeno \(\displaystyle j-1 \) posti liberi tra di loro, dunque gli spettatori potranno essere posizionati solo nella fila da n posti e il numero di sequenza di posti vuoti sara \(\displaystyle k+1 \). Arrivati a questo punto possiamo vedere il problema come "in quanti modi possiamo ottenere il numero \(\displaystyle 2(j-1)+n-k \) come somma di \(\displaystyle k+1 \) interi maggiori o uguali di \(\displaystyle j-1 \)?"
Cioè \(\displaystyle x_1+x_2+...x_{k+1}=2(j-1)+n-k \) con \(\displaystyle x_i \ge j-1 \).
Qui uso una "tecnica" classica: sottraggo ad ogni \(\displaystyle x_i \) j-1 cosi da ottenere \(\displaystyle x_1+x_2+...x_{k+1}=2(j-1)+n-k-(k+1)(j-1)=(1-k)(j-1)+n-k \) con \(\displaystyle x_i \ge 0 \) (in pratica nel problema originario tolgo in blocco \(\displaystyle j-1 \) posti da ogni sequenza di posti liberi, e lo posso fare, visto che noi andiamo a contare il numero di posti in piu a j-1 per ogni sequenza).
Quindi in quanti modi posso partizionare il numero \(\displaystyle (1-k)(j-1)+n-k \) come somma ordinta di \(\displaystyle k+1 \) numeri naturali?
\(\displaystyle \binom{(1-k)(j-1)+n-k+ k}{k}=\binom{(1-k)(j-1)+n}{k} \)
Spero di non essermi perso qualcosa.
Mi viene lo stesso risultato xD Però non mi pare di aver visto altre volte il cinema coi registi bell'approccio xD
(edit: Ma ora che ci penso anche senza tirare in ballo i registi, si trattava di trovare i modi in cui ottenere una certa somma dove ogni addendo è maggiore di $j-1$ tranne due, quindi senza quella premessa riconosco di averlo visto altre volte xD )
Io avevo pensato di fare una trasformazione del tipo:
-prendo una configurazione valida
-il numero più a sinistra rimane dov'è, quello che lo segue a destra viene traslato verso sinistra di $j-1$ posizioni, quello che sta ancora più a destra viene traslato a sinistra di $2(j-1)$ posizioni... e così via finchè quello più a destra viene traslato a sinistra di $(k-1)(j-1)$ posizioni.
- Si nota che adesso non ci possono essere due numeri che occupano la stessa posizione e che l'ordine in cui compaiono gli elementi da sinistra verso destra rimane invariato (quello che prima era più a sinistra resta più a sinistra e così via...)
- Questa trasformazione è iniettiva, cioè partendo da due configurazioni diverse si ottengono nuove configurazioni diverse, proprio perchè se fossero uguali allora gli elementi occupavano ordinatamente le stesse posizioni anche in partenza.
- Gli elementi vengono confinati tutti entro l'intervallo da $1$ a $n-(k-1)(j-1)$ e per ogni scelta di $k$ elementi a caso in quell'intervallo corrisponde una configurazione valida che genera quella scelta. Basta applicare il processo inverso, traslandoli verso destra con lo stesso criterio di prima e si ottiene una configurazione valida.
- Quindi la trasformazione è suriettiva
- Quindi prendere $k$ elementi con distanza almeno $j$ nell'intervallo da $1$ a $n$ equivale a prendere $k$ elementi a caso nell'intervallo da $1$ a $n-(k-1)(j-1)$.
- Quindi il risultato è \(\displaystyle \binom{n-(k-1)(j-1)}{k}\)
In alternativa...
si può notare che $f(n,k,j) = f(n-1,k,j) + f(n-j,k-1,j)$ e sviluppando un po' una tabella si nota che sono più o meno le diagonali del triangolo di tartaglia traslate.......... rovinandosi completamente il problema
bell'approccio xD(edit: Ma ora che ci penso anche senza tirare in ballo i registi, si trattava di trovare i modi in cui ottenere una certa somma dove ogni addendo è maggiore di $j-1$ tranne due, quindi senza quella premessa riconosco di averlo visto altre volte xD )
Io avevo pensato di fare una trasformazione del tipo:
-prendo una configurazione valida
-il numero più a sinistra rimane dov'è, quello che lo segue a destra viene traslato verso sinistra di $j-1$ posizioni, quello che sta ancora più a destra viene traslato a sinistra di $2(j-1)$ posizioni... e così via finchè quello più a destra viene traslato a sinistra di $(k-1)(j-1)$ posizioni.
- Si nota che adesso non ci possono essere due numeri che occupano la stessa posizione e che l'ordine in cui compaiono gli elementi da sinistra verso destra rimane invariato (quello che prima era più a sinistra resta più a sinistra e così via...)
- Questa trasformazione è iniettiva, cioè partendo da due configurazioni diverse si ottengono nuove configurazioni diverse, proprio perchè se fossero uguali allora gli elementi occupavano ordinatamente le stesse posizioni anche in partenza.
- Gli elementi vengono confinati tutti entro l'intervallo da $1$ a $n-(k-1)(j-1)$ e per ogni scelta di $k$ elementi a caso in quell'intervallo corrisponde una configurazione valida che genera quella scelta. Basta applicare il processo inverso, traslandoli verso destra con lo stesso criterio di prima e si ottiene una configurazione valida.
- Quindi la trasformazione è suriettiva
- Quindi prendere $k$ elementi con distanza almeno $j$ nell'intervallo da $1$ a $n$ equivale a prendere $k$ elementi a caso nell'intervallo da $1$ a $n-(k-1)(j-1)$.
- Quindi il risultato è \(\displaystyle \binom{n-(k-1)(j-1)}{k}\)
In alternativa...
si può notare che $f(n,k,j) = f(n-1,k,j) + f(n-j,k-1,j)$ e sviluppando un po' una tabella si nota che sono più o meno le diagonali del triangolo di tartaglia traslate.......... rovinandosi completamente il problema
Bravi entrambi
Io avevo fatto così:
Dobbiamo scoprire in quanti modi si scelgono $x_1, x_2, ..., x_k$ tali che:
$$1 \le x_1 < x_2 - (j-1) < ... < x_i - (i-1)\cdot(j-1) < ... < x_k - (k-1)(j-1) \le n - (k-1)(j-1)$$
Definendo $y_i = x_i - (i-1)(j-1)$ si riscrive come:
$$1 \le y_1 < y_2 < ... < y_k \le n - (k-1)(j-1)$$
E poi considerando che c'è biiezione
scelta di $x_i$ validi = scelta di $y_i$ distinti tra $1$ e $n - (k-1)(j-1)$
si finisce.
Io avevo fatto così:
Dobbiamo scoprire in quanti modi si scelgono $x_1, x_2, ..., x_k$ tali che:
$$1 \le x_1 < x_2 - (j-1) < ... < x_i - (i-1)\cdot(j-1) < ... < x_k - (k-1)(j-1) \le n - (k-1)(j-1)$$
Definendo $y_i = x_i - (i-1)(j-1)$ si riscrive come:
$$1 \le y_1 < y_2 < ... < y_k \le n - (k-1)(j-1)$$
E poi considerando che c'è biiezione
scelta di $x_i$ validi = scelta di $y_i$ distinti tra $1$ e $n - (k-1)(j-1)$
si finisce.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo