Disuguaglianza cinese

[psion_metacreativo]

Premetto che la soluzione da me trovata del seguente esercizio non utilizza alcuna delle tecniche sulle disuguaglianze perchè sono piuttosto incapace a riguardo, dunque ogni soluzione che utilizzerà tali tecniche sarà perticolarmente apprezzata dal sottoscritto nella convinzione che sicuramente esiste una soluzione molto più efficente ed elegante della mia brute force. Anyway:

Provare che per ogni $ 2n $-upla di numeri reali: $ a_{1},a_{2},\ldots,a_{n},b_{1},b_{2},\ldots,b_{n}\ \ (n\geq 3) $ che soddisfa le seguenti tre condizioni:
$ \displaystyle 1)\sum^{n}_{i=1}a_{i}=\sum^{n}_{i=1}b_{i} $
$ \displaystyle2)0<a_{1}=a_{2}\ \ \:\ e \ \ \ \ a_{i}+a_{i+1}=a_{i+2}\ \ \forall i=1,2,\ldots,n-2 $
$ \displaystyle3)0<b_{1}\leq b_{2}\ \ \ \ e \ \ \ \ \ b_{i}+b_{i+1}=b_{i+2}\ \ \forall i=1,2,\ldots,n-2 $

Vale la disuguaglianza:
$ \displaystyle a_{n-1}+a_{n}\leq b_{n-1}+b_{n} $

-Traduzione di un problema cinese 1995-(credo gara nazionale ma non ci scommetterei)

[HumanTorch]

Allora, prima di tutto ci togliamo davanti il caso $ b_1=b_2 $: in tal caso $ a_i=b_i \forall i \in [0;n] $ e vale l'uguaglianza.

Sia quindi ora $ b_2>b_1 $: per la serie degli $ a_i $ ogni termine si può scrivere come $ F_i\cdot a_1 $ dove $ F_i $ è l' $ i $-esimo termine della serie di Fibonacci (con $ F_1=F_2=1 $). Il primo membro diviene quindi $ F_{n+1}\cdot a_1 $.

Analizziamo la seconda serie (quella dei termini $ b_i $ per intenderci): anche in questo caso definiamo $ b_i $ come $ F_{i-1}\cdot b_1+F_i\cdot b_2 $. Il secondo membro diviene $ F_n\cdot b_1+F_{n+1}\cdot b_2>F_{n+2}\cdot b_1 $

Affinchè le due $ n $-uple abbiano stessa media (ovvero stessa somma), dovrà essere $ a_1>b_1 $ e $ a_2>b_2 $, e $ a_j\geq b_j $, con $ 1<j<n $, quindi $ b_n>a_n $, ovvero $ F_{n-1}\cdot b_1+F_n\cdot b_2>F_n\cdot a_1 $.
La funzione in questione è strettamente crescente e la serie $ b_n $ cresce più rapidamente di $ a_n $, quindi la tesi è dimostrata. Per chi preferisca Binet e il limite per due coefficenti consecutivi di Fibonacci $ \varphi $..

Non so se è prettamente "inequalities solving", ma sono certo che è preferibile lavorare sulle medie e sulle somme parziali dei primi $ k $ termini, quindi fatevi avanti

[psion_metacreativo]

Affinchè le due $ n $-uple abbiano stessa media (ovvero stessa somma), dovrà essere $ a_1>b_1 $ e $ a_2>b_2 $, e $ a_j\geq b_j $, con $ 1<j<n $, quindi $ b_n>a_n $, ovvero $ F_{n-1}\cdot b_1+F_n\cdot b_2>F_n\cdot a_1 $.
La funzione in questione è strettamente crescente e la serie $ b_n $ cresce più rapidamente di $ a_n $, quindi la tesi è dimostrata. Per chi preferisca Binet e il limite per due coefficenti consecutivi di Fibonacci $ \varphi $..

Potresti essere più preciso per favore? Non ho capito nulla di questo paragrafo, grazie.

[HumanTorch]

Ok, ci riprovo, se Dio m'assiste ..

Sarà: $ a_n=F_n\cdot a_1 $
$ b_n=F_{n-2}\cdot b_1+F_{n-1}\cdot b_2 $

Se $ a_1<b_1 $ e $ a_2<b_2 $, e ovvio che sarà anche vero che $ a_i=F_n\cdot a_1<F_i\cdot b_2<b_i=F_{i-2}\cdot b_1+F_{i-1}\cdot b_2 $, questo $ \forall i \in [0;n] $, quindi la somma dei termini $ a_i $ dovrà essere minore della somma dei termini $ b_i $, il che contraddice le ipotesi.
Tuttavia, dovra anche essere $ a_n<b_n $: la funzione $ b_n=F_{n-2}\cdot b_1+F_{n-1}\cdot b_2 $, difatti, cresce più rapidamente della funzione $ a_n=F_n\cdot a_1 $, e se fosse anche $ a_n>b_n $, avremmo che $ \sum^n_{i=1} a_i>\sum^n_{i=1} b_i $. Ma se $ a_n<b_n $, $ F_n\cdot a_1<b_n=F_{n-2}\cdot b_1+F_{n-1}\cdot b_2 $; sempre perchè la funzione relativa ai termini $ b_1 $ cresce più rapidamente rispetto a quella con i termini $ a_i $ , la tesi è dimostrata

EDIT: Corretto, don't worry, a tutto c'è rimedio..

[psion_metacreativo]

Sarà: $ a_n=F_n\cdot a_1 $
$ b_n=F_{n-1}\cdot b_1+F_n\cdot b_2 $

Mi spiace ma è $ b_n=F_{n-1}\cdot b_2+F_{n-2}\cdot b_1 $

Se $ a_1<b_1 $ e $ a_2<b_2 $,

Perchè supponi queste due disuguaglianze? Per esempio la prima è falsa, e la seconda non è motivata da alcunchè. In generale per quel che mi riguarda la difficoltà principale di questo problema è stata determinare un confronto tra i termini delle due serie...

Mi sono fermato qui a leggere coscientemente la tua soluzione, anche se ho continuato a guardare il resto e in generale mi sembra che sfrutti il fatto che una data funzione "cresce più rapidamente" di un'altra. Sebbene tali osservazioni risultino utili a volte è difficile dimostrarle e mi sembra che nel tuo caso non sia sufficientemente motivata.

[HumanTorch]

Le due disuguaglianze si suppongono per assurdo, e la loro falsità è proprio dimostrata nel post.
Il fatto che la funzione per i $ b_i $ cresce più rapidamente che per gli $ a_i $ è dovuta al fatto che $ b_i=F_{n-1}\cdot b_2+f_{n-2}\cdot b_1 $ che è sempre maggiore di $ F_{n-1}\cdot b_1+f_{n-2}\cdot b_1=F_n\cdot b_1 $ che ricorre allo stesso modo di $ F_n\cdot a_1 $. Quindi se ad un certo punto si dovrà avere $ b_j>a_j $ e ciò varrà anche per $ b_k e a_k $, con $ j<k<n $. Ma, ripeto, forse è meglio usare Binet e il limite $ \varphi $ per termini consecutivi per $ n $ tendente a $ \infty $

[psion_metacreativo]

Alla luce di quanto hai scritto nel tuo ultimo post rileggo la tua dimostrazione.

Se $ a_1<b_1 $ e $ a_2<b_2 $, e ovvio che sarà anche vero che $ a_i=F_n\cdot a_1<F_i\cdot b_2<b_i=F_{i-2}\cdot b_1+F_{i-1}\cdot b_2 $, questo $ \forall i \in [0;n] $, quindi la somma dei termini $ a_i $ dovrà essere minore della somma dei termini $ b_i $, il che contraddice le ipotesi.

1) qui hai dimostrato che deve essere $ a_1\geq b_1 $ o $ a_2\geq b_2 $.

la funzione $ b_n=F_{n-2}\cdot b_1+F_{n-1}\cdot b_2 $, difatti, cresce più rapidamente della funzione $ a_n=F_n\cdot a_1 $, e se fosse anche $ a_n>b_n $, avremmo che $ \sum^n_{i=1} a_i>\sum^n_{i=1} b_i $. Ma se $ a_n<b_n $, $ F_n\cdot a_1<b_n=F_{n-2}\cdot b_1+F_{n-1}\cdot b_2 $; sempre perchè la funzione relativa ai termini $ b_1 $ cresce più rapidamente rispetto a quella con i termini $ a_i $

2)qui più o meno chiaramente hai dimostrato che deve essere $ a_n<b_n $

Come fai a concludere la tesi da 1) e 2)?

[HumanTorch]

Sfruttando le relazioni con la serie di Fibonacci e le proprietà della funzione, per il fatto che una serie cresce più velocemente dell'altra:
$ a_n<b_n $ ovvero
$ F_n\cdot a_1<F_{n-2}\cdot b_1+F_{n-1}\cdot b_2 $.
Il primo membro cresce più lentamente del secondo nel passare da $ n $ a $ n+1 $, quindi $ F_{n+1}\cdot a_1<F_{n-1}\cdot b_1+F_n\cdot b_2 $, ovvero $ a_{n-1}+a_{n}\leq b_{n-1}+b_{n} $

[psion_metacreativo]

Forse non ho spiegato chiaramente cosa non capisco della tua soluzione: siamo d'accordo che hai dimostrato che almeno uno dei primi due termini degli $ a_i $ è maggiore di almeno uno dei primi due termini dei $ b_i $. Poi hai ragionato e dimostrato che i $ b_i $ crescono più velocemente degli $ a_i $ dunque affinchè le due serie abbiano somma uguale prima o poi ci deve essere lo "scatto" e i $ b_i $ devono superare gli $ a_i $ da un certo punto in poi. Il nocciolo della questione è proprio questo: cosa ti garantisce che lo scatto avvenga prima dell'indice $ n-1 $ cosìcché tu possa concludere la tesi? In altre parole cosa ti garantisce che non succede che$ \forall i=1,\ldots,n-1\ \ a_i\geq b_i $ e $ a_n\leq b_n $ ?

[HumanTorch]

E' questo il punto.. anche se il "raggiungimento-superamento" avviene solo con l'ultima coppia $ (a_n;b_n) $, questo avverrà anche per $ (a_{n+1};b_{n+1}) $, ovvero $ F_{n+1}\cdot a_1<F_{n-1}\cdot b_1+F_n\cdot b_2 $, ed essendo $ F_k=F_{k-1}+F_{k-2} $, si ha $ (F_{n-1}+F_n)\cdot a_1<(F_{n-3}+F_{n-2})\cdot b_1+(F_{n-2}+F_{n-1})\cdot b_2 $
$ \rightarrow a_{n-1}+a_n<b_{n-1}+b_n $, indipendentemente dal $ a_{n-1}<b_{n-1} $ o viceversa..all right?

[psion_metacreativo]

ok, scusa ma sono duro a capire, dopo cena posto un rilancio alla questione.

[HumanTorch]

ok, scusa ma sono duro a capire, dopo cena posto un rilancio alla questione.

Don't worry, man, sono io un frescone nello spiegare..

[psion_metacreativo]

Ok Human rilancio alla questione:

Per ogni $ 2n $-upla che rispetti le condizioni iniziali calcolare $ a_3 $ conoscendo $ b_1 $ e $ b_2 $.

P.S. Precedentemente avevo proposto un altro rilancio al problema originale però mi sono reso conto che concettualmete ha la stessa difficoltà di questo che mi sembra più carino.
P.P.S Il vecchio rilancio recitava così: Sia data una $ 2n $-upla che rispetti le 3 condizioni del problema iniziale con l'ipotesi aggiuntiva che $ n\geq2005 $, $ b_1=1 $, $ b_2=2 $. Stabilire il $ \min (n) $ tale che $ a_{2005}>b_{2005} $.

[psion_metacreativo]

up!