Sia data una sequenza finita di reali positivi. Denotiamo come $ k $-prodotto il prodotto di $ k $ numeri appartenenti alla sequenza consecutivi.
Sappiamo che nella nostra sequenza vale che ogni $ p $-prodotto è minore di 1, e che ogni $ q $-prodotto è maggiore di 1 (con $ p $,$ q $ ovviamente interi positivi). Quanti termini può avere al più la sequenza?
34.Prodotti consecutivi
34.Prodotti consecutivi
"We' Inge!"
LTE4LYF
LTE4LYF
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: 34.Prodotti consecutivi
CASO BASE: \(d=(p,q)=1\)
Parte distruttiva: poniamo per assurdo \(n \geq p+q-1\). Costruiamo una tabella in cui nella prima riga ci sono \(a_1, \ldots a_p\), nella seconda \(a_2, \ldots, a_{p+1}\), ..., nell'ultima \(a_q, \ldots, a_{p+q-1}\). I prodotti sulle righe sono tutti minori di 1, i prodotti sulle colonne sono maggiori di 1 \(\rightarrow\) il prodotto di tutti gli elementi è contemporaneamente maggiore e minore di 1, assurdo.
Parte costruttiva: \(n \leq p+q-2\) va bene. Voglio che la mia serie abbia 2 requisiti:
1. Non-potenza. Voglio scegliere il primo \(p\) prodotto e il primo \(q\) prodotto in modo che rispettino le ipotesi. Per farlo mi serve che la successione non sia costante, altrimenti il primo \(p\) prodotto e il primo \(q\) prodotto sarebbero potenze di uno stesso numero, e dunque entrambi minori o maggiori di 1.
2. Periodicità. Voglio una successione periodica di periodo \(p\) e periodo \(q\), in modo che i \(p\) (o \(q\) ) prodotti siano tutti uguali tra loro.
Una serie del genere esiste per il teorema di Wilf-Fine.
CASO GENERALE: \(d>1\), dove \(d=(p,q)\).
Parte distruttiva: poniamo per assurdo \(n > p+q-d-1\). Sia \(a_k\) il prodotto dei numeri da \(a_{dk+1}\) a \(a_{dk+(d-1)}\). Abbiamo \(\left \lfloor n/d \right \rfloor\) termini. Applichiamo il caso base a \(\left \lfloor n/d \right \rfloor, p/d, q/d\) e otteniamo che è assurdo \(\left \lfloor n/d \right \rfloor \geq p/d + q/d -1\), ossia \(n \geq d \left \lfloor n/d \right \rfloor \geq p+q-d\). Perciò deve essere \(n \leq p+q-d-1\).
Parte costruttiva: \(n = p+q-d-1\) va bene. Questa è un po' più dura, ma ci proviamo, per completezza
Come prima, la mia serie deve avere due requisiti:
1. Non-potenza. Voglio scegliere il primo \(q\) prodotto e il primo \(p\) prodotto in modo che rispettino le ipotesi. Per farlo, essi non devono essere potenze di uno stesso numero. Ma allora i \(d\) prodotti non devono essere tutti uguali, altrimenti i \(p\) e \(q\) prodotti sarebbero potenze di un \(d\) prodotto, dunque entrmabi maggiori o minori di 1. Perciò la serie non deve essere periodica di periodo \(d\).
2. Periodicità. Voglio che la serie sia periodica di periodo \(p\) e di periodo \(q\), in modo che i \(p\) e \(q\) prodotti siano tutti uguali tra loro.
Wilf-Fine generalizzato:
Esiste una successione periodica \(a_1, \ldots, a_n\) di periodo \(p\) e di periodo \(q\) non periodica di periodo \(d\) se e solo se \(n \leq p+q-d-1\).
Assumiamo per assurdo \(n \geq p+q-d\).
Costruiamo un "grafo della periodicità" (orientato) in questo modo: ogni vertice rappresenta un termine della sequenza, \(a_i\) è collegato a \(a_{p+i}\), e \(a_{q+i}\) è collegato ad \(a_i\) (attenzione ai versi degli archi). L'essere collegati indica l'essere uguali. Allora il grafo è un 1-digrafo regolare (ogni vertice ha un arco che entra e uno che esce), i quali sono fatti da cicli disgiunti. E' semplice dimostrare che il "grafo della periodicità" ha \(d=(p,q)\) cicli disgiunti: \(a_i\) è connesso solo ai termini della forma \(a_{i+dk}\) (aggiungendo e togliendo \(p,q\) la congruenza modulo \(d\) si conserva), e a tutti termini della forma \(a_{i+dk}\) solo se \(n \geq p+q-d\) (semplici considerazioni sul teorema di bezout e simili). Perciò il numero di componenti connesse è esattamente \(d\), il numero di classi di resto \(\pmod{d}\). Ma allora la successione è \(d\) periodica! Per sbarazzarmi della periodicità devo levare \(d+1\) vertici: i primi \(d\) vengono cancellati uno da ogni ciclo (stiamo togliendo i termini finali, che appartengono tutti a classi diverse \(\pmod{d}\) ), ma tutte le componenti rimangono connesse; l'ultimo vertice sottratto dà il colpo di grazia e abbiamo vinto, perchè una componente connessa si spezza \(\Rightarrow\) la serie non è periodica di periodo \(d\) .
Parte distruttiva: poniamo per assurdo \(n \geq p+q-1\). Costruiamo una tabella in cui nella prima riga ci sono \(a_1, \ldots a_p\), nella seconda \(a_2, \ldots, a_{p+1}\), ..., nell'ultima \(a_q, \ldots, a_{p+q-1}\). I prodotti sulle righe sono tutti minori di 1, i prodotti sulle colonne sono maggiori di 1 \(\rightarrow\) il prodotto di tutti gli elementi è contemporaneamente maggiore e minore di 1, assurdo.
Parte costruttiva: \(n \leq p+q-2\) va bene. Voglio che la mia serie abbia 2 requisiti:
1. Non-potenza. Voglio scegliere il primo \(p\) prodotto e il primo \(q\) prodotto in modo che rispettino le ipotesi. Per farlo mi serve che la successione non sia costante, altrimenti il primo \(p\) prodotto e il primo \(q\) prodotto sarebbero potenze di uno stesso numero, e dunque entrambi minori o maggiori di 1.
2. Periodicità. Voglio una successione periodica di periodo \(p\) e periodo \(q\), in modo che i \(p\) (o \(q\) ) prodotti siano tutti uguali tra loro.
Una serie del genere esiste per il teorema di Wilf-Fine.
CASO GENERALE: \(d>1\), dove \(d=(p,q)\).
Parte distruttiva: poniamo per assurdo \(n > p+q-d-1\). Sia \(a_k\) il prodotto dei numeri da \(a_{dk+1}\) a \(a_{dk+(d-1)}\). Abbiamo \(\left \lfloor n/d \right \rfloor\) termini. Applichiamo il caso base a \(\left \lfloor n/d \right \rfloor, p/d, q/d\) e otteniamo che è assurdo \(\left \lfloor n/d \right \rfloor \geq p/d + q/d -1\), ossia \(n \geq d \left \lfloor n/d \right \rfloor \geq p+q-d\). Perciò deve essere \(n \leq p+q-d-1\).
Parte costruttiva: \(n = p+q-d-1\) va bene. Questa è un po' più dura, ma ci proviamo, per completezza
Come prima, la mia serie deve avere due requisiti:1. Non-potenza. Voglio scegliere il primo \(q\) prodotto e il primo \(p\) prodotto in modo che rispettino le ipotesi. Per farlo, essi non devono essere potenze di uno stesso numero. Ma allora i \(d\) prodotti non devono essere tutti uguali, altrimenti i \(p\) e \(q\) prodotti sarebbero potenze di un \(d\) prodotto, dunque entrmabi maggiori o minori di 1. Perciò la serie non deve essere periodica di periodo \(d\).
2. Periodicità. Voglio che la serie sia periodica di periodo \(p\) e di periodo \(q\), in modo che i \(p\) e \(q\) prodotti siano tutti uguali tra loro.
Wilf-Fine generalizzato:
Esiste una successione periodica \(a_1, \ldots, a_n\) di periodo \(p\) e di periodo \(q\) non periodica di periodo \(d\) se e solo se \(n \leq p+q-d-1\).
Assumiamo per assurdo \(n \geq p+q-d\).
Costruiamo un "grafo della periodicità" (orientato) in questo modo: ogni vertice rappresenta un termine della sequenza, \(a_i\) è collegato a \(a_{p+i}\), e \(a_{q+i}\) è collegato ad \(a_i\) (attenzione ai versi degli archi). L'essere collegati indica l'essere uguali. Allora il grafo è un 1-digrafo regolare (ogni vertice ha un arco che entra e uno che esce), i quali sono fatti da cicli disgiunti. E' semplice dimostrare che il "grafo della periodicità" ha \(d=(p,q)\) cicli disgiunti: \(a_i\) è connesso solo ai termini della forma \(a_{i+dk}\) (aggiungendo e togliendo \(p,q\) la congruenza modulo \(d\) si conserva), e a tutti termini della forma \(a_{i+dk}\) solo se \(n \geq p+q-d\) (semplici considerazioni sul teorema di bezout e simili). Perciò il numero di componenti connesse è esattamente \(d\), il numero di classi di resto \(\pmod{d}\). Ma allora la successione è \(d\) periodica! Per sbarazzarmi della periodicità devo levare \(d+1\) vertici: i primi \(d\) vengono cancellati uno da ogni ciclo (stiamo togliendo i termini finali, che appartengono tutti a classi diverse \(\pmod{d}\) ), ma tutte le componenti rimangono connesse; l'ultimo vertice sottratto dà il colpo di grazia e abbiamo vinto, perchè una componente connessa si spezza \(\Rightarrow\) la serie non è periodica di periodo \(d\) .
Ultima modifica di Gottinger95 il 22 set 2013, 01:01, modificato 4 volte in totale.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: 34.Prodotti consecutivi
Ok, mi pare giusto 
Comunque non intendevo (p,q)=1. Diciamo che non pensavo di essere frainteso: per al più intendevo proprio quel p+q-(p,q)-1, non chiedevo di dimostrare la parte costruttiva. Chiedo scusa se qualcuno ci si è sbattezzato sopra per trovare anche la sequenza effettiva
Comunque non intendevo (p,q)=1. Diciamo che non pensavo di essere frainteso: per al più intendevo proprio quel p+q-(p,q)-1, non chiedevo di dimostrare la parte costruttiva. Chiedo scusa se qualcuno ci si è sbattezzato sopra per trovare anche la sequenza effettiva"We' Inge!"
LTE4LYF
LTE4LYF
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: 34.Prodotti consecutivi
L'ho editata con le parti costruttive e l'ho sistemata un pochino Parto con il prossimo? In caso concedetemi un paio di giorni che ne posto uno carino!
(ne avrei uno carino che sto elaborando ma è un po' difficile e poco appetitoso, quindi ne debbo cercare un altro)
Parto con il prossimo? In caso concedetemi un paio di giorni che ne posto uno carino! (ne avrei uno carino che sto elaborando ma è un po' difficile e poco appetitoso, quindi ne debbo cercare un altro)
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe