Permutazioni
Sia $n$ un intero positivo. Determinare quante sono le permutazioni $(a_1,a_2,...,a_n)$ dell'insieme ${1,2,..,n}$ con la seguente proprietà:
$2(a_1+a_2+...+a_k)$ è multiplo di $k$ per ogni $k=1,2,..,n$
$2(a_1+a_2+...+a_k)$ è multiplo di $k$ per ogni $k=1,2,..,n$
Risposte
... Magari si può cominciare da $n$ piccoli.. Per $n=1$ o $n=2$ o $n=3$ c'è qualche problema?
Sarebbe utile che tu spiegassi cosa sono le permutazioni, a parole tue s'intende! 
Dici che serve davvero?
1) Sicuramente farei uno sfondone dietro l'altro se dovessi dare una definizione..
2) E' difficile che uno che non sa cos'è una permutazione, leggendo la definizione su questo thread, poi sia subito in grado di risolverlo.. Voglio dire.. non è un problema che chiede di fare $n!$ e amen, e comunque non è nemmeno un problema di combinatoria, penso che sia più questione di aritmetica e resti.
Posso mettere alcuni casi piccoli.
Ad esempio con $n=3$ si ha l'insieme ${1,2,3}$. Ora le permutazioni di questo insieme possono essere:
$(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$, $(3,2,1)$.
Si nota che in questo caso ai fini del problema vanno bene tutte e $6$.
Infatti con $n=3$, $k$ varierà da $1$ a $3$.
Con $k=1$ si ha che $1$ deve dividere $2 \cdot a_1$ cosa che chiaramente è sempre vera.
Con $k=2$ si ha che $2$ deve dividere $2\cdot(a_1+a_2)$. Che è sempre vero...
Con $k=3$ si ha che $3$ deve dividere $2\cdot(a_1+a_2+a_3)$. A prescindere dall'ordine in cui sono messi quella somma vale $1+2+3=6$ e quindi è sempre vero.
In sostanza con $n=3$ le permutazioni che soddisfano sono $6$, cioè tutte quelle possibili.
Ora il problema arriva dopo. Infatti con $n=4$ se noi prendiamo questa permutazione: $(1,2,4,3)$.
Si ha che $3$ deve dividere $2\cdot (1+2+4)$ ma ciò non avviene. Quindi quella permutazione non va bene. Quante sono nel caso $n=4$ le permutazioni che vanno bene?
1) Sicuramente farei uno sfondone dietro l'altro se dovessi dare una definizione..
2) E' difficile che uno che non sa cos'è una permutazione, leggendo la definizione su questo thread, poi sia subito in grado di risolverlo.. Voglio dire.. non è un problema che chiede di fare $n!$ e amen, e comunque non è nemmeno un problema di combinatoria, penso che sia più questione di aritmetica e resti.
Posso mettere alcuni casi piccoli.
Ad esempio con $n=3$ si ha l'insieme ${1,2,3}$. Ora le permutazioni di questo insieme possono essere:
$(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$, $(3,2,1)$.
Si nota che in questo caso ai fini del problema vanno bene tutte e $6$.
Infatti con $n=3$, $k$ varierà da $1$ a $3$.
Con $k=1$ si ha che $1$ deve dividere $2 \cdot a_1$ cosa che chiaramente è sempre vera.
Con $k=2$ si ha che $2$ deve dividere $2\cdot(a_1+a_2)$. Che è sempre vero...
Con $k=3$ si ha che $3$ deve dividere $2\cdot(a_1+a_2+a_3)$. A prescindere dall'ordine in cui sono messi quella somma vale $1+2+3=6$ e quindi è sempre vero.
In sostanza con $n=3$ le permutazioni che soddisfano sono $6$, cioè tutte quelle possibili.
Ora il problema arriva dopo. Infatti con $n=4$ se noi prendiamo questa permutazione: $(1,2,4,3)$.
Si ha che $3$ deve dividere $2\cdot (1+2+4)$ ma ciò non avviene. Quindi quella permutazione non va bene. Quante sono nel caso $n=4$ le permutazioni che vanno bene?
Se continui così tra poco citerai il libro di Passmann: Permutation Groups...
Considerato un insieme di \(n\) elementi \(S=\{a_1;...;a_n\}\)(1) distinti(2); una permutazione (semplice) di \(S\) è un modo per ordinare per gli elementi di \(S\), ad esempio posso considerare le permutazioni \((a_1;...;a_n)\) e \((a_n;...;a_1)\) oppure \((a_2;a_1;...;a_n)\)(3).
Non è difficile dimostrare che le permutazioni di \(S\) sono: \[n!=n\cdot(n-1)\cdot...\cdot2\cdot1\]
scritto ciò, mi auspico che il problema posto da xXstephXx sia completamente comprensibile anche agli studenti delle scuole medie.
§§§
(1) Per chi lo può capire, un tale insieme \(S\) può essere anche composto da infiniti elementi, ad esempio l'insieme dei numeri naturali \(\mathbb{N}\).
(2) Si può anche considerare l'insieme \(\{C;A;S;A\}\) che ha \(4\) elementi ma non tutti diversi.
(3) Ciò spiega le notazioni di xXStephXx nel post precedente.
Considerato un insieme di \(n\) elementi \(S=\{a_1;...;a_n\}\)(1) distinti(2); una permutazione (semplice) di \(S\) è un modo per ordinare per gli elementi di \(S\), ad esempio posso considerare le permutazioni \((a_1;...;a_n)\) e \((a_n;...;a_1)\) oppure \((a_2;a_1;...;a_n)\)(3).
Non è difficile dimostrare che le permutazioni di \(S\) sono: \[n!=n\cdot(n-1)\cdot...\cdot2\cdot1\]
scritto ciò, mi auspico che il problema posto da xXstephXx sia completamente comprensibile anche agli studenti delle scuole medie.
§§§
(1) Per chi lo può capire, un tale insieme \(S\) può essere anche composto da infiniti elementi, ad esempio l'insieme dei numeri naturali \(\mathbb{N}\).
(2) Si può anche considerare l'insieme \(\{C;A;S;A\}\) che ha \(4\) elementi ma non tutti diversi.
(3) Ciò spiega le notazioni di xXStephXx nel post precedente.
"j18eos":
mi auspico che il problema posto da xXstephXx sia completamente comprensibile anche agli studenti delle scuole medie.
No vabbè aspetta... E' chiaro che non è comprensibile ad uno studente delle medie!! Suvvia cosa pretendevi?
Nè tantomeno uno studente delle medie può avere speranze di risolverlo! Così come anche uno studente delle superiori che non ha mai fatto problemi di questo tipo non lo può risolvere..
In teoria rispetto ad altri problemi postati in questa sezione potrebbe dare qualche difficoltà in più, però si può sempre tentare.
Ad esempio continuando il post precedente.. Nel caso $n=4$ non tutte le permutazioni vanno bene, quindi con un po' di tentativi quante sono quelle che vanno bene?
Una volta fatto a mano il caso $n=4$ e il caso $n=5$ si dovrebbe capire qual è il meccanismo per generalizzare.
A volte funziona l'idea d'usare inizialmente la "forza bruta" per farsi un'idea di partenza sulle possibili soluzioni generali d'un problema,
per poi trovar modo di rendere elegante ed esaustiva la verifica di quella soluzione intravista
(ammesso che essa sia stata intuita bene,ovvio):
questo percorso è tipico di certe dimostrazioni per induzione,
quando non si conosce la "forma chiusa" di quanto si vuol dimostrare..
Ma a tutto c'è un limite
(a parte che alle funzioni non regolari in un dato intorno ):
si ha infatti $5!=120$!!!
Detto che i punti esclamativi che chiudono l'uguaglianza precedente sono tre (3) per non richiamare l'uso del semifattoriale
,
attenzionerei piuttosto la strategia per "costruire",ai nostri scopi,
opportune quaterne sulla base delle terne da cui,piazzando nella giusta posizione il 4,esse nascono:
poi verificherei se la stessa idea funziona,con gli ovvi accorgimenti,passando da $n=4$ a $n=5$,
ed a quel punto inizierei a sospettare che è alquanto naturale tanto generalizzare la soluzione delle evenienze specifiche al caso di $n$ qualunque(la "forma chiusa" di cui sopra..)
quanto verificare per induzione che quella congettura può esser esser "promossa" a soluzione generale del problema dato..
Saluti dal web.
per poi trovar modo di rendere elegante ed esaustiva la verifica di quella soluzione intravista
(ammesso che essa sia stata intuita bene,ovvio):
questo percorso è tipico di certe dimostrazioni per induzione,
quando non si conosce la "forma chiusa" di quanto si vuol dimostrare..
Ma a tutto c'è un limite
(a parte che alle funzioni non regolari in un dato intorno
):si ha infatti $5!=120$!!!
Detto che i punti esclamativi che chiudono l'uguaglianza precedente sono tre (3) per non richiamare l'uso del semifattoriale
,attenzionerei piuttosto la strategia per "costruire",ai nostri scopi,
opportune quaterne sulla base delle terne da cui,piazzando nella giusta posizione il 4,esse nascono:
poi verificherei se la stessa idea funziona,con gli ovvi accorgimenti,passando da $n=4$ a $n=5$,
ed a quel punto inizierei a sospettare che è alquanto naturale tanto generalizzare la soluzione delle evenienze specifiche al caso di $n$ qualunque(la "forma chiusa" di cui sopra..)
quanto verificare per induzione che quella congettura può esser esser "promossa" a soluzione generale del problema dato..
Saluti dal web.
Secondo me a questo punto fai prima a mettere la soluzione completa e diretta così almeno quelli che non vogliono spoilerarsi troppo si fermano al messaggio di sopra.. quelli che invece vogliono la soluzione leggeranno il messaggio successivo a questo.
Insomma sperando di evitare strafalcioni,l'idea sarebbe questa:
-k dispari: bisogna contare le k_uple nei primi n interi consecutivi tali che la somma dei k elementi è divisibile per k.
-k pari:supponiamo che $y$ sia il massimo esponente di 2 che compare nella fattorizzazione di $k$,e poniamo $k=2^y\cdot w$,e da qui contiamo le k_uple tali che la somma dei k elementi è divisibile per $2^{y-1}\cdot w$.
Qui farebbero comodo gli hint...
-k dispari: bisogna contare le k_uple nei primi n interi consecutivi tali che la somma dei k elementi è divisibile per k.
-k pari:supponiamo che $y$ sia il massimo esponente di 2 che compare nella fattorizzazione di $k$,e poniamo $k=2^y\cdot w$,e da qui contiamo le k_uple tali che la somma dei k elementi è divisibile per $2^{y-1}\cdot w$.
Qui farebbero comodo gli hint...
Siccome ogni giorno FreddyKruger mi chiede su fb di mettere gli hint metto qualche hint xD
Dunque se non ricordo male... (ormai è passato un po' di tempo...) supposto che con i numeri da 1 a n sappiamo quante sono le permutazioni... se noi prendiamo i numeri da 1 a n+1 abbiamo che l'ultimo elemento della permutazione deve essere per forza 1 oppure n+1 (chissà perchè?...).. Se fissiamo n+1 alla fine abbiamo che i restanti numeri possono essere permutati con lo stesso numero di permutazioni del caso precedente.. Se invece mettiamo 1 alla fine.... (forse è la stessa cosa... dimostrare anche questo).
metto qualche hint xDDunque se non ricordo male... (ormai è passato un po' di tempo...) supposto che con i numeri da 1 a n sappiamo quante sono le permutazioni... se noi prendiamo i numeri da 1 a n+1 abbiamo che l'ultimo elemento della permutazione deve essere per forza 1 oppure n+1 (chissà perchè?...).. Se fissiamo n+1 alla fine abbiamo che i restanti numeri possono essere permutati con lo stesso numero di permutazioni del caso precedente.. Se invece mettiamo 1 alla fine.... (forse è la stessa cosa... dimostrare anche questo).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo