Attenzione: problema che blocca la crescita!

[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]

Nessuno?
Non era mia intenzione spaventarvi così tanto con quel titolo

[nuoveolimpiadi1999]

Per curiosità da dove viene il problema?

[bern-1-16-4-13]

E' un A5 IMO shortlist 2007

[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]

Ok ottimo, mi fa piacere ti sia piaciuto
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.