Edit: ho modificato e aggiunto che devono essere positivi (quel + al pedice della Q vuol dire questo)Dato l'insieme $ \displaystyle (a_1,a_2,\dots, a_m)\in\mathbb{Q}_{+}^m $ tale che:
$ \displaystyle \sum_{i=1}^ma_i=1 $
Trovare il minimo e il massimo della funzione $ f:\mathbb{N}\to\mathbb{Z} $ così definita:
$ \displaystyle f(n)=n-\sum_{i=1}^m\lfloor a_i\cdot n\rfloor $
min/MAX di una funzione con parti intere (cesefake 4 es 4 )
min/MAX di una funzione con parti intere (cesefake 4 es 4 )
Premetto che potrebbe essere gia stato postato anni addietro... ho provato a cercarlo ma sono evidentemente negato perchè o mi escono 0 risultati o me ne escono 1400... perciò ho lasciato stare, in ogni caso se è stato postato mettete un link al vecchio...
Ultima modifica di dario2994 il 25 ott 2009, 15:18, modificato 1 volta in totale.
EDIT:Questa è la soluzione ad un problema diverso,infatti io per distrazione ho considerato il prodotto degli a_i uguale a 1, e non la somma (ormai la tengo perchè cancellarla tutta non avrebbe senso)
Escludiamo il caso m=1 perchè la funzione diventa costantemente nulla. Idea base della soluzione: esiste almeno un a_i>1 oppure tutti gli a_i sono uguali a 1.
Troviamo il minimo della funzione:
Tralasciando il caso in cui tutti gli a_i sono uguali a 1 (è banale vedere che la funzione diverge a $ -\infty $), chiamo a_m il maggiore degli a_i (ovviamente a_m è maggiore di 1). Ho che
$ f(n)\le n-[a_mn]=[n(1-a_m)] $. Ma $ n(1-a_m) $ diverge a $ -\infty $ e quindi cosi succede anche alla sua parte intera, e si conclude col teorema dei carabinieri.
Troviamo ora il massimo:
Con una tecnica simile a quella di prima si dimostra che la funzione è (debolmente) decrescente, per cui il minimo si ha per n=1 ed è $ \displaystyle 1-\sum_{i=1}^m[a_i] $
Può andare o c'è qualche errore?
Escludiamo il caso m=1 perchè la funzione diventa costantemente nulla. Idea base della soluzione: esiste almeno un a_i>1 oppure tutti gli a_i sono uguali a 1.
Troviamo il minimo della funzione:
Tralasciando il caso in cui tutti gli a_i sono uguali a 1 (è banale vedere che la funzione diverge a $ -\infty $), chiamo a_m il maggiore degli a_i (ovviamente a_m è maggiore di 1). Ho che
$ f(n)\le n-[a_mn]=[n(1-a_m)] $. Ma $ n(1-a_m) $ diverge a $ -\infty $ e quindi cosi succede anche alla sua parte intera, e si conclude col teorema dei carabinieri.
Troviamo ora il massimo:
Con una tecnica simile a quella di prima si dimostra che la funzione è (debolmente) decrescente, per cui il minimo si ha per n=1 ed è $ \displaystyle 1-\sum_{i=1}^m[a_i] $
Può andare o c'è qualche errore?
Ultima modifica di Maioc92 il 25 ott 2009, 18:14, modificato 2 volte in totale.
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
ehm.... io li avevo considerati positivi nella mia soluzionedario2994 ha scritto:Ops... toppato un piccolo particolare scusa davvero:
Gli $ a_i $ sono positivi xD
Si quel simbolo nella sommatoria è la parte intera
(2 errori si compensano 
)Comunque se la mia soluzione è giusta (e può benissimo essere sbagliata) a cosa serve l'ipotesi di razionalità??
EDIT: il teorema dei carabinieri non è nulla di trascendentale in realtà. Applicato in questo caso dice che date due successioni $ a_n,b_n $ tali che $ a_n\le b_n $ per ogni n (ovvero la successione a_n è minorante della successione b_n), se b_n diverge a $ -\infty $ allora succede la stessa cosa ad a_n (in pratica è la formalizzazione di una cosa intuitiva)
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
dario2994 ha scritto:uhm... la tua dimostrazione parte gia col piede sbagliato xD
DiciMa guarda che la somma fa 1... non il prodotto.Idea base della soluzione: esiste almeno un $ a_i>1 $ oppure tutti gli $ a_i $ sono uguali a 1.
Chissà cosa avevo per la testa...è meglio se per oggi mi ritiro
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
Inizio io con il minimo: siano $ a_i:=b_ic_i^{-1} $ per qualche $ (b_i,c_i) \in \mathbb{N}_0^2 $ tali che $ \text{gcd}(b_i,c_i)=1 $, per ogni $ i \in \mathbb{Z} \cap [1,m] $. Allora, dato che $ x \ge \lfloor x \rfloor $ con uguaglianza se e solo se $ x \in \mathbb{Z} $ allora $ f(n) \ge 0 $ con uguaglianza se e solo se $ \text{lcm}(c_1,c_2,\ldots,c_m) \mid n $.
The only goal of science is the honor of the human spirit.
Anche il massimo si risolve allo stesso modo. Dato che $ \lfloor nb_ic_i^{-1} \rfloor $ è costante per ogni $ n \in \mathbb{Z} \cap [kc_i,(k+1)c_i) $ per qualche $ k \in \mathbb{Z} $ è chiaro che se $ f(n) $ assume massimo allora $ n $ sarà della forma $ t\text{lcm}(c_1,\ldots,c_m)-1 $ per qualche $ t \in \mathbb{N} $. Ma $ \displaystyle f(t\text{lcm}(c_1,\ldots,c_m)-1)=t\text{lcm}(c_1,\ldots,c_m)-1-\sum{\left \lfloor b_i(t\text{lcm}(c_1,\ldots,c_m)-1)c_i^{-1} \right \rfloor} $ $ =\displaystyle t\text{lcm}(c_1,\ldots,c_m)-1+m-\sum{b_it\text{lcm}(c_1,\ldots,c_m)c_i^{-1} \right \rfloor} $ $ =\displaystyle m-1+t\text{lcm}(c_1,\ldots,c_m)\left(1-\sum{b_ic_i^{-1}}\right)=m-1 $. []
Per cui abbiamo mostrato anche che $ f(\cdot) $ assume minimo se e solo se $ \text{lcm}(c_1,\ldots,c_m) \mid n $ e assume massimo se e solo se $ \text{lcm}(c_1,\ldots,c_m) \mid n+1 $.
Per cui abbiamo mostrato anche che $ f(\cdot) $ assume minimo se e solo se $ \text{lcm}(c_1,\ldots,c_m) \mid n $ e assume massimo se e solo se $ \text{lcm}(c_1,\ldots,c_m) \mid n+1 $.
The only goal of science is the honor of the human spirit.
Tutto giusto tranne questo pezzo (che dice cose vere... ma non ho capito come le hai dimostrate xD ):
Poi l'implicazione per cui allora quello è il massimo non l'ho capita...
Non capisco prima di tutto cosa è costante... e al variare di cosa xD E poi c'è una parentesi quadra di mezzo xDDato che $ \displaystyle \lfloor nb_ic_i^{-1} \rfloor $ è costante per ogni $ \displaystyle n \in \mathbb{Z} \cap [kc_i,(k+1)c_i) $ per qualche $ \displaystyle k \in \mathbb{Z} $ è chiaro che se $ \displaystyle f(n) $ assume massimo allora $ \displaystyle n $ sarà della forma $ \displaystyle t\text{lcm}(c_1,\ldots,c_m)-1 $ per qualche $ \displaystyle t \in \mathbb{N} $
Poi l'implicazione per cui allora quello è il massimo non l'ho capita...
Buh di parentesi quadre in più non ne vedo, comunque.. se hai una frazione positiva della forma a/b non intera con gcd(a,b)=1 allora sei d'accordo che [ka/b] rimane costante per ogni b-1<k<2b ? Significa che se vogliamo massimizzare k-[ka/b] in un generico intervallo di interi k in [tb,tb-1], è sufficiente prendere k il più grande possibile visto che quella parte intera rimane costante. E se questo deve valere per più frazioni contemporaneamente il più piccolo b da scegliere è il minimo comune multiplo di tutte le frazioni. Spero sia più chiaro adesso..
The only goal of science is the honor of the human spirit.
Chiarissimo :)
Comunque la parentesi quadra di troppo c'è xD
La mia dimostrazione del minimo è identica, per il massimo invece no... ho dimostrato prima che:
$ f(n)<m\ \ \forall n\in\mathbb{N} $
E poi ho mostrato un esempio di massimo quando:
$ n=\prod b_i $
Con $ \displaystyle b_i $ i denominatori dei razionali.
L'idea è la stessa solo che io non avevo notato che in effetti il massimo deve essere per forza nella forma che hai mostrato :)
Comunque la parentesi quadra di troppo c'è xD
La mia dimostrazione del minimo è identica, per il massimo invece no... ho dimostrato prima che:
$ f(n)<m\ \ \forall n\in\mathbb{N} $
E poi ho mostrato un esempio di massimo quando:
$ n=\prod b_i $
Con $ \displaystyle b_i $ i denominatori dei razionali.
L'idea è la stessa solo che io non avevo notato che in effetti il massimo deve essere per forza nella forma che hai mostrato :)
