Galileiana 2014 - 4

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Leonida
Messaggi: 61
Iscritto il: 12 set 2011, 19:37
Località: Maserada (Treviso)

Galileiana 2014 - 4

Messaggio da Leonida » 05 set 2015, 18:42

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$
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"

Avatar utente
Nemo
Messaggi: 73
Iscritto il: 03 dic 2013, 17:35

Re: Galileiana 2014 - 4

Messaggio da Nemo » 08 set 2015, 00:50

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à.
Ultima modifica di Nemo il 10 set 2015, 22:18, modificato 3 volte in totale.
[math]

Avatar utente
Leonida
Messaggi: 61
Iscritto il: 12 set 2011, 19:37
Località: Maserada (Treviso)

Re: Galileiana 2014 - 4

Messaggio da Leonida » 08 set 2015, 14:55

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!!"

Avatar utente
Nemo
Messaggi: 73
Iscritto il: 03 dic 2013, 17:35

Re: Galileiana 2014 - 4

Messaggio da Nemo » 08 set 2015, 19:03

Ho corretto un typo.

Edit: invano, perché era proprio sbagliata l'induzione...
Ultima modifica di Nemo il 10 set 2015, 22:07, modificato 1 volta in totale.
[math]

Avatar utente
Drago96
Messaggi: 1136
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Galileiana 2014 - 4

Messaggio da Drago96 » 08 set 2015, 21:01

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) ;)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
Nemo
Messaggi: 73
Iscritto il: 03 dic 2013, 17:35

Re: Galileiana 2014 - 4

Messaggio da Nemo » 09 set 2015, 08:39

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 :lol:)
[math]

Avatar utente
Nemo
Messaggi: 73
Iscritto il: 03 dic 2013, 17:35

Re: Galileiana 2014 - 4

Messaggio da Nemo » 10 set 2015, 22:26

Fatto! Ora funziona?
[math]

Rispondi