Esercizi delle olimpiadi

[giammaria]

Complimenti a milizia96! La sua formula è quella voluta e dimostro che è condizione sufficiente per la soluzione; manca ancora la dimostrazione che è condizione necessaria. Forse per assurdo, supponendo che ci siano anche altre soluzioni?
Riscrivo la tesi nella forma
$A=f(f(n-1))+f(n)=n$

Pongo $a=1/phi=(sqrt5-1)/2=0,62$ e ricordo che $a^2+a-1=0$
Ricordando poi che la parte intera di un numero è una sua approssimazione per difetto, deve esistere un numero $x$ tale che
${(f(n-1)=h=[an]=an-x),(0<x<1):}$
Nella disequazione non vale alcun uguale perché la differenza fra l'irrazionale $an$ ed il naturale $h$ non può essere né 0 nè 1.
Analogamente, esiste $y$ tale che
${(f(f(n-1))=f(h)=[a(h+1)]=ah+a-y=a(an-x)+a-y=a^2n-ax-y+a),(0<y<1):}$
Distinguo ora due casi.

I caso: si ha $f(n)=h=an-x$
In questo caso dobbiamo avere nell'ordine $h, an, a(n+1),h+1$ e questo è possibile solo se $0<x<1-a$
Si ha poi
$A=f(f(n-1))+f(n)=a^2n-ax-y+a+an-x=n(a^2+a-1)+n-z=n-z$
avendo posto $z=ax+y-a+x=x(1+a)+y-a$
Gli estremi inferiore e superiore (mai raggiunti) di $z$ si hanno in corrispondenza a quelli di $x,y$ e si ha
$z_("inf")=0*(1+a)+0-a=-a=-0,62$
$z_("sup")=(1-a)(1+a)+1-a=1-a^2+1-a=1-(a^2+a-1)=1$
Abbiamo definito $A$ come la somma di due numeri interi, quindi è intero e tale deve essere anche $z$: è perciò l'unico intero contenuto fra questi estremi, cioè
$z=0->A=n$

II caso: si ha $f(n)=h+1=an-x+1$
In questo caso dobbiamo avere nell'ordine $h, an,h+1, a(n+1)$ e questo è possibile solo se $1-a<x<1$
Si ha poi
$A=f(f(n-1))+f(n)=a^2n-ax-y+a+an-x+1=n(a^2+a-1)+n-z=n-z$
avendo posto $z=ax+y-a+x-1=x(1+a)+y-a-1$
con estremi
$z_("inf")=(1-a)(1+a)+0-a-1=1-a^2-a-1=-1-(a^2+a-1)=-1$
$z_("sup")=1(1+a)+1-a-1=1$
e l'unico intero racchiuso è $z=0->A=n$


@ veciorik. Mille grazie; neanche io conoscevo quella funzione. Nelle istruzioni ho notato che vicino ad essa c'è anche la funzione INDIRIZZO che forse funziona altrettanto bene, ma non ho provato perché, in fondo, me ne basta una.

[totissimus]

Propongo un'altra dimostrazione dell'uguaglianza \(f(n)=\left\lfloor a(n+1)\right\rfloor \)
Posto \(a=\frac{\sqrt{5}-1}{2}\) e quindi \(a^{2}=1-a\) proviamo che

(1) $an<f(n)<a(n+1)$

Per $n=1$ risulta $a<f(1)=1<2a$ quindi la (1) vale in questo caso

Supponiamo che $ai<f(i)<a(i+1)$ per $i=1,\ldots n-1$

In particolare per $i=n-1$:

$a(n-1)<f(n-1)<an<n$

quindi per l'ipotesi induttiva:

\(a\left[f(n-1)\right]<f\left[f(n-1)\right]<a\left[f(n-1)+1\right]\)

e ancora pe la precedente disuguaglianza:

\(a\left[a(n-1)\right]<f\left[f(n-1)\right]<a\left[an+1\right]\)

$a^{2}(n-1)<n-f(n)<a^{2}n+a$

$n-a^{2}n-a<f(n)<n-a^{2}n+a^2<n-a^2n+a$

$n-(1-a)n-a<f(n)<n-(1-a)n+a$

$an-a<f(n)<an+a$

$(n-1)a<f(n)<(n+1)a$

Siccome tra $(n-1)a$ e $an$ cade l'itero $f(n-1)$ e l'ampiezza
di questo intervallo è $a<1$, l'intero $f(n)$ deve cadere tra $na$ e $(n+1)a$
quindi
$na<f(n)<(n+1)a$

La (1) è dunque provata da essa discende ce \(f(n)=\left\lfloor a(n+1)\right\rfloor \)
in quanto $f(n)>an>a(n+1)-1$

[orsoulx]

Posto .... proviamo che

(1) an<f(n)<a(n+1)

Già con n=2 non mi torna: $ f(2)=1 < 2a $

Ciao

[robbstark]

Ammettendo che la dimostrazione di giammaria sia corretta (ho dato un'occhiata e mi sembra ok), abbiamo trovato una funzione che soddisfa le due condizioni. Che questa funzione sia unica è evidente dal fatto che ad ogni step siamo capaci di calcolare il prossimo numero, giusto usando i precedenti, a causa del fatto che la funzione risulta crescente.

L'unico dubbio è che dovrebbe esistere qualche altro modo più semplice per intuire questa funzione o almeno la soluzione dell'esercizio.