Sia $\mathbb{Z}^+$ l'insieme degli interi positivi. Trovare tutte le funzioni $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ che soddisfano le seguenti proprietà:
(i) per ogni $n \in \mathbb{Z}^+$ vale $f(f(n)) \leq$ $\displaystyle \frac {n +f(n)}{2}$
(ii) per ogni $n \in \mathbb{Z}^+$ vale $f(n) \leq f(n+1)$
(iii) per ogni $m,n \in \mathbb{Z}^+$ con $m \neq n \\ $ vale $MCD(f(m),f(n)) = 1$
Galileiana 2014 - 4
Galileiana 2014 - 4
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"
Re: Galileiana 2014 - 4
Si nota che \(f(n)=1\) soddisfa tutte le proprietà, infatti, poiché \(n \in \mathbb{Z}^+\), \(f(f(n))=1 \le\dfrac{n+1}{2}\), \(f(n)=f(n+1)\), \(gcd(1,1)=1\).
Se \(\exists k \in \mathbb{Z}^+ : f(k)\ne 1\), allora \( \forall n\ge k \; \; \: f(n+1)>f(n)\); infatti, per la \((\textrm{ii})\), \(f(n+1)\ge f(n)\) e, per la \((\textrm{iii})\), \(\forall n \ge k \; \; \: f(n+1) \ne f(n) \).
Dimostro per induzione che \(\forall n \ge k \; \; \: f(n) \ge n +f(k) -k \qquad (a)\)
- p. base \(\qquad f(k) \ge k + f(k) -k \)
- p. induttivo \(\qquad f(n)\ge n +f(k) -k \overset{f(n+1)>f(n)}{\implies} f(n+1)>f(n)\ge n +f(k) -k \)\(\implies f(n+1)\ge n+1 +f(k) -k\).
Se \(\exists k \in \mathbb{Z}^+ : f(k) > k\), allora \(\forall n \ge k \quad f(n) \overset{(a)}{\ge} n +f(k) -k > n\), da cui \(\dfrac{n+f(n)}{2} \overset{(\textrm{i})}{\ge} f(f(n)) > f(n)\), da cui \( f(n) < n\), assurdo.
Se \( \forall n \in \mathbb{Z}^+ \; \; f(n) \le n\; \) e \(\; \exists k \in \mathbb{Z}^+ : f(k)\ne 1\), allora \( \forall n \ge k \;\;\:0 \le n-f(n) \overset{(a)}{\le} k-f(k)\). Da ciò segue che \(\exists h \ge k : \forall n \ge k \;\;\: h-f(h)\le n-f(n)\), ma \(\forall n \ge h \;\;\: n-f(n) \overset{(a)}{\le} h-f(h)\), da cui \(\forall n \ge h \;\;\: f(n)=n+f(h)-h\) e quindi esistono \(l \ne m\) tali che \(f(l)\) e \(f(m)\) sono entrambi pari e questo contraddice la \((\textrm{iii})\).
Dunque, se non ho sbagliato qualcosa, solo \(f(n)=1\) soddisfa tutte le proprietà.
Se \(\exists k \in \mathbb{Z}^+ : f(k)\ne 1\), allora \( \forall n\ge k \; \; \: f(n+1)>f(n)\); infatti, per la \((\textrm{ii})\), \(f(n+1)\ge f(n)\) e, per la \((\textrm{iii})\), \(\forall n \ge k \; \; \: f(n+1) \ne f(n) \).
Dimostro per induzione che \(\forall n \ge k \; \; \: f(n) \ge n +f(k) -k \qquad (a)\)
- p. base \(\qquad f(k) \ge k + f(k) -k \)
- p. induttivo \(\qquad f(n)\ge n +f(k) -k \overset{f(n+1)>f(n)}{\implies} f(n+1)>f(n)\ge n +f(k) -k \)\(\implies f(n+1)\ge n+1 +f(k) -k\).
Se \(\exists k \in \mathbb{Z}^+ : f(k) > k\), allora \(\forall n \ge k \quad f(n) \overset{(a)}{\ge} n +f(k) -k > n\), da cui \(\dfrac{n+f(n)}{2} \overset{(\textrm{i})}{\ge} f(f(n)) > f(n)\), da cui \( f(n) < n\), assurdo.
Se \( \forall n \in \mathbb{Z}^+ \; \; f(n) \le n\; \) e \(\; \exists k \in \mathbb{Z}^+ : f(k)\ne 1\), allora \( \forall n \ge k \;\;\:0 \le n-f(n) \overset{(a)}{\le} k-f(k)\). Da ciò segue che \(\exists h \ge k : \forall n \ge k \;\;\: h-f(h)\le n-f(n)\), ma \(\forall n \ge h \;\;\: n-f(n) \overset{(a)}{\le} h-f(h)\), da cui \(\forall n \ge h \;\;\: f(n)=n+f(h)-h\) e quindi esistono \(l \ne m\) tali che \(f(l)\) e \(f(m)\) sono entrambi pari e questo contraddice la \((\textrm{iii})\).
Dunque, se non ho sbagliato qualcosa, solo \(f(n)=1\) soddisfa tutte le proprietà.
Ultima modifica di Nemo il 10 set 2015, 22:18, modificato 3 volte in totale.
[math]
Re: Galileiana 2014 - 4
Riguarda il passo base della tua induzione...
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"
Re: Galileiana 2014 - 4
Ho corretto un typo.
Edit: invano, perché era proprio sbagliata l'induzione...
Edit: invano, perché era proprio sbagliata l'induzione...
Ultima modifica di Nemo il 10 set 2015, 22:07, modificato 1 volta in totale.
[math]
Re: Galileiana 2014 - 4
Non è un typo, è proprio che tu hai detto che $f(n)\neq1\implies f(n+1)>f(n)$, perciò non puoi applicare l'ipotesi induttiva a tutti gli $n$.
Per fare un esempio concreto, considera già solo $f(1)=f(2)=1$ e poi $f(n)=n-1$ per $n\ge3$ (che soddisfa tutto quello che hai scritto prima dell'induzione)
Per fare un esempio concreto, considera già solo $f(1)=f(2)=1$ e poi $f(n)=n-1$ per $n\ge3$ (che soddisfa tutto quello che hai scritto prima dell'induzione)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Galileiana 2014 - 4
Nella dimostrazione (sbagliata) di fatto c'era un typo, però la dimostrazione è appunto sbagliata, quindi poco conta...
A breve modificherò quello che ho scritto - non so se in meglio o in peggio (vi ricordo che sono quello che usa Monte Carlo
)
A breve modificherò quello che ho scritto - non so se in meglio o in peggio (vi ricordo che sono quello che usa Monte Carlo
)[math]