IMO 1993 - 5

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

IMO 1993 - 5

Messaggio da ngshya » 09 lug 2010, 19:53

Esiste una funzione dagli interi positivi agli interi positivi tale che:
$ $\begin{cases} f(1)=2\\ f(f(n))=f(n)+n \text{ per ogni } n\\ f(n)<f(n+1) \text{ per ogni } n \text{ ?}\\ \end{cases}$ $

Gigi95
Messaggi: 68
Iscritto il: 20 mag 2010, 16:25

Messaggio da Gigi95 » 09 lug 2010, 21:02

Pongo {$ a_i $} la successione tale che $ a_0=1 $ e $ a_j = f(a_{j-1}) $ $ \forall j \in \mathbb N $, allora si ha che $ a_j = a_{j-2} + a_{j-1} $ $ \forall j \in \mathbb N $, tale successione corrisponde alla successione di Fibonacci (a cui sono tolti lo 0 iniziale e il primo dei due 1) se $ a_0=1 $ e $ a_1=2 $, dunque l'unica successione definita dall'ipotesi è proprio la successione di Fibonacci.
Sono ancora da definire le successioni che iniziano per numeri che non compaiono in quella di Fibonacci (per esempio non sappiamo quanto vale $ f(4) $, ma sappiamo che può valere 6 o 7 per la terza condizione in ipotesi), ma queste successioni si possono sempre definire a piacere, infatti man mano che si va avanti con le successioni esistenti, aumenta il numero dei numeri da definire in quanto aumenta lo spazio tra i numeri in successioni definite (in ogni modo scegliendo f(k) per un valore k compreso tra due numeri in modo che f(k) sia compreso tra le funzioni di quei due numeri, l'intera successione rispetterà la condizione n° 3, questo lo si dimostra per induzione (ora non ho il tempo di farlo)), quindi è possibile scegliere le successioni in infiniti modi.

P.s. Se trovate qualche errore nella mia soluzione fatemelo notare please.
[tex] \lambda \upsilon \iota \varsigma [/tex]

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 09 lug 2010, 22:50

La prima parte va bene, hai dimostrato che, se f esiste, sull'n-esimo numero di Fibonacci fa l'n+1-esimo numero di Fibonacci. Per il resto non hai dimostrato niente, hai solo notato che è verosimile che le cose funzionino. Devi far vedere che è effettivamente possibile "riempire i buchi", oppure dimostrare che è impossibile. Inoltre, non è esatto dire che la funzione è univocamente determinata solo sui Fibonacci, o almeno non lo è a priori. Per farti un esempio, se vuoi una funzione dai naturali ai naturali che sia strettamente crescente e sia l'identità sui numeri pari, a prima vista è definita solo sui numeri pari, ma in realtà lo è anche sui dispari. Oppure, visto che, definita la funzione su un numero "libero", è automaticamente definita su tutta una "successione di Fibonacci generalizzata", è possibile che scegliendo male un valore della funzione, prima o poi due successioni si incontrino con valori diversi. In sintesi, formalizza quel pezzo che dici che si può fare per induzione :D .
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Gigi95
Messaggi: 68
Iscritto il: 20 mag 2010, 16:25

Messaggio da Gigi95 » 10 lug 2010, 11:25

Ok, ora che ho tempo dimostro ciò che volevo dimostrare per induzione:
Supponiamo di avere tre valori $ A<B<C $, tali che $ f(A) < f(C) $ sono valori determinati e $ f(B) $ è ancora da determinare, si può scegliere un valore per $ f(B) $ qualsiasi, purché compreso tra $ f(A) $ e $ f(C) $, dimostriamo che comunque si scelga $ f(B) $, $ f(f(B)) $ è sempre compreso tra $ f(f(A)) $ e $ f(f(C)) $, possiamo esprimere
B come $ A+n $ e C come $ A+n+m $, con $ m,n \in \mathbb N $, e poiché $ f(A) < f(B) < f(C) $, possiamo porre $ f(B) = f(A) + p $ e $ f(C)= f(A) +p +q $ con $ p,q \in \mathbb N $, allora scriviamo:
$ f(f(A)) = f(A) + A $
$ f(f(B)) = f(A) + p + A + n= f(f(A)) +p +n $
$ f(f(C)) = f(A) +p+q +A+m+n = f(f(B)) +q+m $
Analogamente si dimostra che, date tre successioni {$ x_i $}, {$ y_i $} e {$ z_i $}, se $ x_0 < y_0<z_0 $, allora $ x_j<y_j<z_j $ $ \forall j \in \mathbb N $.
[tex] \lambda \upsilon \iota \varsigma [/tex]

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 10 lug 2010, 12:24

Secondo me le idee ce le hai messe, ma come scriveresti una dimostrazione del genere in gara? Diciamo che per come l'hai scritta si capisce che hai capito, ma non è del tutto chiaro dove vai a parare.
Se vuoi un consiglio per formalizzare meglio, prova a scrivere una roba del genere:
sia A il minimo naturale tale che f(A) non è già definita, definisco f(A)=f(A-1)+1. A questo punto è molto più semplice dire quello che hai detto tu senza però incasinarsi, perchè più è intricato quello che scrivi più è facile perdere punti
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 10 lug 2010, 12:28

Gigi95 ha scritto: Supponiamo di avere tre valori $ A<B<C $, tali che $ f(A) < f(C) $ sono valori determinati e $ f(B) $ è ancora da determinare, si può scegliere un valore per $ f(B) $ qualsiasi, purché compreso tra $ f(A) $ e $ f(C) $
questo tra l'altro è errato, perchè se ad esempio sia A+2 che A+1 non sono già determinati e definisci f(A+2)=f(A)+1, come la definisci f(A+1) conservando la monotonia stretta?
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Rispondi