Attenzione: problema che blocca la crescita!

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
bern-1-16-4-13
Messaggi: 78
Iscritto il: 23 mag 2015, 18:27

Attenzione: problema che blocca la crescita!

Messaggio da bern-1-16-4-13 »

Sia $c>2$ un numero reale. Consideriamo una sequenza di reali non negativi $\left\{a_n\right\}_{n\ge 1}$ tale da soddisfare le seguenti ipotesi:
$i.\ \ $ $\forall\ \ m,n\in\mathbb{Z}^+$ vale che $$a_{m+n}\le 2a_m+2a_n$$
$ii.\ \ $ $\forall\ \ k\in\mathbb{N}$ vale che $$a_{2^k}\le\frac{1}{\left(k+1\right)^c}$$

Dimostrare che $\left\{a_n\right\}$ è boundata superiormente.
bern-1-16-4-13
Messaggi: 78
Iscritto il: 23 mag 2015, 18:27

Re: Attenzione: problema che blocca la crescita!

Messaggio da bern-1-16-4-13 »

Nessuno?
Non era mia intenzione spaventarvi così tanto con quel titolo :roll:
nuoveolimpiadi1999
Messaggi: 124
Iscritto il: 31 mar 2015, 13:30

Re: Attenzione: problema che blocca la crescita!

Messaggio da nuoveolimpiadi1999 »

Per curiosità da dove viene il problema?
bern-1-16-4-13
Messaggi: 78
Iscritto il: 23 mag 2015, 18:27

Re: Attenzione: problema che blocca la crescita!

Messaggio da bern-1-16-4-13 »

E' un A5 IMO shortlist 2007
Ciuffo
Messaggi: 14
Iscritto il: 18 ago 2014, 22:13

Re: Attenzione: problema che blocca la crescita!

Messaggio da Ciuffo »

Un problema molto bello e istruttivo, circa un IMO2, consiglio di provarlo a tutti.. metto una traccia di
soluzione
Testo nascosto:
Inanzitutto il caso pessimo è quando l'indice è 1111...1 in binario
Testo nascosto:
Dovete usare tante volte la (i) per arrivare a degli indici tutte potenze di due, altrimenti non avrete mai un minore uguale di
Testo nascosto:
Ovviamente dovete 'spezzarlo' bene, non nel modo ovvio... a seconda di come lo fate ottenete dei pesi diversi davanti alle cose del tipo k^-c
Testo nascosto:
Come mai è c>2 e non c>=2?
Testo nascosto:
Volete scegliere dei pesi in modo furbo in modo che la cosa converga... usando il fatto che 1/n^a converge per a > 1
Testo nascosto:
Vi piacerebbe che i pesi crescessero come cx, dove x è l'indice e c costante, ma non si può
Testo nascosto:
Si fa con c x^k, con k = 1+epsilon
Testo nascosto:
Si fa per k = 1 + 1/j, per j opportuno, che potete far crescere quanto volete
Testo nascosto:
Equivalente a: partite con una lavagna con scritto 1, ad ogni mossa cancellate un numero e scrivete due volte il sio doppio. Volete che i numeri dopo un po' valgano x^k, asintoticamente
Testo nascosto:
1 -> 22 -> 4444 -> 88888888 non funziona (fa x^2), però è molto meglio di 1 -> 22 -> 244 -> 2488...
Testo nascosto:
Vi conviene 'trasformare' ad ogni passaggio quasi tutti i numeri che avete scritto.. questo è l'ultimo hint leggero, il prossimo uccide il problema, quindi pensate prima di aprire
Testo nascosto:
4444 -> 4888888 -> 4 16..16 -> 4 16 16 16 32...32, dove a ogni due mosse trasformate 1/4 dei numeri fa x^4/3
Testo nascosto:
Come sopra, a ogni h mosse trasformate uno ogni j numeri con j e h grandi, e l'esponente tende a 1. Ne prendete uno più piccolo di c-1, e vi rimane costante per 1/k^a, con a>1
bern-1-16-4-13
Messaggi: 78
Iscritto il: 23 mag 2015, 18:27

Re: Attenzione: problema che blocca la crescita!

Messaggio da bern-1-16-4-13 »

Ok ottimo, mi fa piacere ti sia piaciuto :D
Un altro modo forse un po' meno sofisticato per effettuare la divisione, che però funziona lo stesso, è il seguente:
Testo nascosto:
immaginiamoci la nostra stringa binaria arbitrariamente lunga $111111...$ che rappresenta un numero capovolto, cioè la cifra delle unità è quella più a sinistra. Effettuiamo i primi spezzamenti scegliendo $t$ intero tale che $c>2+\frac{1}{t}$ e tagliando appena dopo la $2^{0t}$-esima posizione, poi appena dopo la $2^{1t}$-esima posizione della nuova stringa (cioè della stringa dove abbiamo tolto le parti tagliate in precedenza), poi appena dopo la $2^{2t}$-esima della nuova stringa, e così via. Quindi in questo modo avremo ottenuto rispettivamente spezzoni di lunghezza $2^{0t},2^{1t},2^{2t}...$
Infine su ognuno di questi effettuiamo l'algoritmo che hai mostrato tu nel tuo decimo hint, cioè dividiamo ripetutamente a metà ogni spezzone fino a raggiungere la situazione in cui abbiamo tutti spezzoni di lunghezza $1$.
Quindi alla fine i coefficienti saranno nell'ordine da sinistra verso destra $$2,\underbrace{2^{t+2}}_{\times2^t},\underbrace{2^{2t+3}}_{\times2^{2t}},\underbrace{2^{3t+4}}_{\times2^{3t}},...$$
e questo ci piace perché ci porta facilmente a dire che il peso assegnato all'$i$-esimo indice sarà sempre minore o uguale di $di^{1+\frac{1}{t}}$ con $d$ opportuna costante.
Rispondi