Italian TST 2005: problema n°4

[Simo_the_wolf]

Spostato da MindFlyer
-------------------------------

Sia data la funzione $ f(-) $ dall'insieme $ \{1,2,...,1600\} $ in sè tale che:

1) $ f^{(2005)}(x)=x $ per ogni $ x $
2) $ f(1)=1 $

(a) Dimostrare che esiste almeno un altro punto fisso oltre $ 1 $ (cioè tale che $ f(x)=x $
(b) La tesi rimane valida se al posto di $ 1600 $ si considera un intero maggiore?

P.S.: $ f^{(n)}(x) $ si considera la funzione $ f(-) $ applicata $ n $ volte

[MindFlyer]

Questo è un po' difficile da classificare, ma di certo non è Algebra.
Non so se sia più Teoria dei Numeri o più Combinatoria.

EDIT: Alla fine ha vinto Teoria dei Numeri. Anche se questo potrebbe essere un grosso hint...

[info]

Lasciano, per il momento, in sospeso i 2 es di geometria e combinatoria, le cui sol mi paiono lunghe da scrivere, provo questo che pare carino...

- Non esiste nessun numero diverso da 1 tale che f(x)=1.

Infatti se fosse f(x)=1, allora, f^2005(x)=1, ma è f^2005(x)=x. Contradiction, man....

- allora la funzione manda (2,3,...,1600) in (2,3,...,1600). Ammettiamo che non esistano altri punti fissi nella funzione. Prendiamo una qualsiasi x nell'insieme privo dell'1 e formiamo una catena tale che:

f(x1)=x2--f(x2)=x3---f(x3)=x4---... --- f(xn)=x1

questa catena si può sempre formare, deve avere n>=2 (altrimenti esisterebbero punti fissi), ed è univocamente determinata, nel senso che se invece di x1 avessimo preso x3 avremmo ottenuto sempre la medesima catena, anche se con gli indici sciftati... Elementi esterni alla catena non possono essere tali che f(y)=xi, infatti se questo fosse il caso, applicando la funzione potremmo ottenere solo valori della catena e non potrebbe essere f^(2005)y=y. Quindi possiamo eseguire il medesimo procedimento con i numeri rimasti più volte senza rischiare di dovere intersecare delle catenem in modo da dividere tutti i 1599 numeri in catene separate.

Ora però notiamo che deve essere n/2005, perchè sia f^2005(x)=x.

Ora la diofantea 401a+5b=1599 non è risolvibile per a e b interi, infatti:

1599-401=1198
1198-401=797
797-401=396

non abbiamo mai ottenuto un multiplo di 5. Questo vuol dire che esisteranno varie catene di lunghezza unitarie che si idenficano con altri punti fissi della funzione... (che può essere anche vista come una contraddizione delle ipotesi)

b) La tesi non rimane valita se la difoantea 401a+5b=k-1 possiede soluzione (a,b) entrambe positive...

[Simo_the_wolf]

e quand'è che la diofantea 401a+5b=k ha soluzioni a,b interi positivi???

[thematrix]

uhm,forse soluzioni non negative...

[info]

Non capisco, vuoi una condizione su k??... Sul fatto che simili numeri esistano e siano grandi a piacere (ciò che serve per invalidare la tesi), basta dare alla a ed alla b numeri positivi e vedere che k esce fuori... o c'è qualche errore nella dimo?

[Simo_the_wolf]

c'è una particolarità che ha 1599 rispetto a 401 e 5... quel è? Prova a vedere se esiste qualche numero k>1599 t.c. 5a+401b=k non ha soluzioni con a,b positivi...

[info]

Ah! Ho capito cosa intendi... Beh... in questo caso sono fortunato e non devo manco faticare! Il primo problema carino che ho risolto (due o tre anni fà!credo...) era la diofantea:

ax+by=c

determinare il max c non esprimibile in quella forma (a e b sono dati e primi tra loro, x e y appartengono ad N). Il max c era (ab-a-b) che si applica al problema...

Beh... però questo non credo fosse richiesto dal problema, non bastava dire che almeno per un numero maggiore di 1600 non vale??... anche perchè un ragazzo che gareggia e conosce il teorema è parecchio avvantaggiato rispetto a qualcun altro che se lo deve dimostrare (insomma, io c'avevo perso un pò di tempo ragionando su svariate serie aritmetiche)... la richiesta è cmq ambigua! Come l'hanno considerata, per curiosità? Se volevano la risposta completa, il problema non era equo...

[frengo]

questo teorema (il massimo numero non esprimibile come combinazione lineare "non negativa" di a e b è ab-a-b ) ce l'hanno detto durante il pre-imo un paio di giorni prima della prova, e infatti di tutti e 6 gli esercizi questo è stato quello con più "7".

[kemhONE]

questo teorema (il massimo numero non esprimibile come combinazione lineare "positiva" di a e b è ab-a-b ) ce l'hanno detto durante il pre-imo un paio di giorni prima della prova, e infatti di tutti e 6 gli esercizi questo è stato quello con più "7".

Ma perché "positiva"?
Forse mi sbaglio, ma in questo caso non dovrebbe trattarsi di interi non negativi?
Altrimenti come si risolve 5a+401b=1600??

[frengo]

Si si hai ragione adesso cambio....
comunque il senso si era capito.
in ogni caso la dimostrazione di quel teorema nel problema numero 4 NON era richiesta(sennò 7 non lo prendevo).

[Marco]

questo teorema (il massimo numero non esprimibile come combinazione lineare "non negativa" di a e b è ab-a-b ).

Mmmmh... Naoki Sato ne propone una dimostrazione che mi piace molto, non fosse altre per il fatto che definisce una certa cosa un grapefruit (che, se non mi inganno, è un pompelmo). Sapete che ho un debole per le definizioni fantasiose.

Ah, e per chi è stato a sentire, anche a Cesenatico, nella conferenza di Jan Pataki è stato dimostrato (alzi la mano chi se ne è accorto...).

Ciao. M.

[HiTLeuLeR]

questo teorema (il massimo numero non esprimibile come combinazione lineare "non negativa" di a e b è ab-a-b ) ce l'hanno detto durante il pre-imo un paio di giorni prima della prova [...]

Oh, beh... La questione è arcinota, in TdN. Per la cronaca, quel numeretto là (e intendo $ ab-a-b $) si chiama indice di Frobenius. L'ho detto giusto per poter mettere il becco anche da queste parti!!!