[SNS 2013 P.6]

[gilgamesh]

Si consideri il polinomio :
$ p(x,y)= \frac {(x+y)^2+3x+y}{2} $

Nel seguito chiameremo numeri naturali i numeri interi non negativi (incluso quindi anche lo zero). Denoteremo con $ \mathbb{N} $ l'insieme dei numeri naturali.
1)Si dimosri che se $ x \in \mathbb{N} $ e $ y \in \mathbb{N} $ allora anche $ p(x,y) \in \mathbb{N} $
2) Si determinino tutte le coppie $ (x,y) \in \mathbb{N} \times \mathbb{N} $ tali che $ p(x,y)=2013 $
3) Si dimostri che la funzione $ p: \mathbb{N}^2 \rightarrow \mathbb{N} $ che associa a (x,y) il numero naturale $ p(x,y) $ è invertibile.

Ecco l'ultimo problema propostoci ieri al test SNS. Scrivo nell'hide il mio risultato del punto 2, nel caso qualcuno non vuole saperlo , vorrei sapere in particolare come dimostrereste l'ultimo punto.

Testo nascosto:

(60,2)

[jordan]

Qualcuno puo' spostarlo in Tdn?

Punto 1. $2p(x,y)=(x+y)^2+3x+y \equiv (x+y)+x+y \equiv 2(x+y) \equiv 0 \pmod 2$.

Punto 3. $p(x,y)=\binom{x+y+1}{2}+x$. Se fosse $p(x_1,y_1)=p(x_2,y_2)$ per qualche $(x_1,y_1) \neq (x_2,y_2)$ allora wlog $0\le x_1<x_2$ implica
$$x_2-x_1=\binom{x_1+y_1+1}{2}-\binom{x_2+y_2+1}{2} \ge \binom{x_1+y_1+1}{2}-\binom{x_1+y_1}{2}=(x_1+y_1)^2$$.

Visto che $x_2-x_1>0$ allora $x_1+y_1+1>x_2+y_2+1$, e in particolare $x_1+y_1>x_2+y_2\ge x_2 \ge (x_1+y_1)^2$, che è falso per tutti gli $x_1+y_1 \in \mathbb{N}$.

Punto 2. Esiste al massimo una soluzione $(x,y)$ all'equazione $p(x,y)=k$. Edit, e' sufficiente prendere il numero triangolare piu' grande che non è maggiore di $k$, e poi verificare che una tale soluzione esiste.

[jordan]

Una soluzione piu' pulita del punto 3:
$$\binom{x+y+1}{2} \le p(x,y) < \binom{x+y+2}{2}.$$

[Triarii]

Credo si possa fare usando come bound $ (x+y)^2 $ e $ (x+y+2)^2 $
Domanda idiota: in questo caso quando chiede di dimostrare l'invertibilità non bisogna dimostrare anche la surgettività? (certi n non mi pare possano essere scritti in tale forma...) Dunque quando si tratta di funzioni simili per invertibilità basta l'"iniettività"?

[jordan]

$e^x$ è invertibile, ma non assume mai valori negativi.

Ps. Il tuo bound non funziona; e anche se fosse vero, non vedo come concluderesti che è iniettiva..

[LeZ]

Io ho dimostrato la surgettività così:$ p(x,y)=\frac{(x+y)^2+3x+y}{2}=a $. Come trovo $ a+1 $? Tramite la trasformazione che manda $ x $ in $ x+1 $ e $ y $ in $ y-1 $. Bisogna poi aggiungere una nota, ovvero che quando $ y-n=0 $, è necessario fare la trasformazione che manda $ x+n $ in $ 0 $ e $ y-n $ in $ x+n+1 $ se non ricordo male. Mostrando che $ 0 $ è esprimibile, la surgettività è fatta.

[Triarii]

Allora posto la mia pseudo soluzione, perchè non riesco a capire dove è l'errore
Chiamo $ 2p(x,y)=LHS $ per semplicità.
$ (x+y)^2=x^2+2xy+y^2<LHS $ per $ x\ne 0 $ e $ y\ne 0 $
$ (x+y+2)^2=x^2+y^2+4+2xy+4x+4y>LHS $
Quindi ad esempio per risolvere il punto b) basta dire
$ (x+y)<\sqrt 4026\approx 63,4 \rightarrow x+y\le 63 $
$ x+y+2>\sqrt 4026 \rightarrow x+y+2>63 \rightarrow x+y>61 $
Quindi ho 2 casi: $ x+y=62 $ e $ x+y=63 $
Pongo quindi nella equazione prima $ x $e $ y=62-x $, che dà infatti le soluzioni trovate da gilgamesh., poi provo con $ x $e $ 63-x $ che non dà soluzioni intere.
Si noti che nell'equazione $ LHS=k $ abbiamo sempre un bound su $ x+y $, che può assumere solo 2 valori. Infatti vale per quanto detto su che $ x+y\le \lfloor \sqrt k \rfloor $ e che$ x+y+2>\lfloor \sqrt k \rfloor $ , da cui $ x+y>\lfloor \sqrt k \rfloor -2 $. Quindi $ x+y $può assumere solo 2 valori. Chiamando la parte intera $ a $, per esplicitare $ x $abbiamo 2 casi che ci conducono a 2 equazioni: $ x+y=a $ e $ x+y=a-1 $
I) $ a^2+3x+a-x=k $ da cui $ a^2+a+2x=k $
II) $ a^2-2a+1 +3x-x+a-1 a^2-a-1+2x=k $da cui $ a^2-a+2x=k $
($ k $è ovviamente pari visto che abbiamo moltiplicato la relazione iniziale per 2 ambo i membri)
Dimostro ora che fissato k, solo una coppia fissata $ (x,y) $ posta nella relazione dà di fatto come risultato $ k $.
Infatti vale sempre che$ x+y $ è compreso fra i 2 valori. Per l'iniettività poi dovrei dimostrare che o un caso o l'altro mi dà una soluzione negativa (poi lo posto se ci riesco a farlo a modino)
Poi so nota che comunque esiste sempre una soluzione x positiva nel secondo caso per ogni k, visto che comunque $ a^2-a $ è sempre pari e quindi ogni k pari ha soluzione (dividendo per 2 posso quindi ottenere tutti i naturali.
Dove sbaglio?

e anche se sarebbe vero

E qui mi vendico u.u

[jordan]

Sbaglio che sarebbe un congiuntivo

Comunque si, il bound infatti non era su $p(x,y)$ ma su $2p(x,y)$.Riguardo la tua soluzione, $x+y$ puo' assumere solo due valori, ok. Poi come concludi?

Ps. Col bound del terzo post, data l'equazione $p(x,y)=k$ con $k$ fissato implica che $x+y$ è fissato, per cui se fosse $p(x_1,y_1)=p(x_2,y_2)$ allora $x_1=x_2$ e di conseguenza $y_1=y_2$..

[Chuck Schuldiner]

surgiggiettività

fixed

[Triarii]

Per dimostrare l'iniettività penso basti dire questo:
i due casi sono
1)$ 2x=k-a(a+1) $ ($ x+y=a) $
2)$ 2x=k-a(a-1) $ ($ x+y=a-1 $)
Supponiamo$ x_1 $ e $ y_1 $ soddisfino il caso 1. Dimostro che non esiste una coppia $ x_2 y_2 $ tali che soddisfino il secondo.
Deve valere che$ x_1\ge0 y_1\ge0 \Rightarrow 0\le x_1 \le a $
Sottraendo membro a membro le 2 equazioni sopra ottengo $ x_2-x_1=a $ (*)
Ciò implica che $ x_2\ge a $, ,a ciò è assurdo perchè implica che $ y_1 $ sia negativo.
Supponiamo ora invece che $ x_2 $ e $ y_2 $ soddisfino la seconda. Dimostro che non esiste una coppia $ x_1 y_1 $ che soddisfino la prima.
Con un ragionamento analogo ottengo $ 0\le x_2\le a-1 $
Confrontandola con (*) tuttavia abbiamo che $ x_1 $ sia negativo, assurdo.
Quindi per ogni k esiste solo una coppia che soddisfi la richiesta (infatti trovato il cso "giusto" x è determinato univocamente, così come y)

[Albertobucci95]

Per quanto riguarda il punto 2: pongo $ x+y=z $ così si ha: $ z^2+3(z-y)+y=4026 $
Adesso ricavando la $ y $ si ha: $ 2y=z^2+3z-4026 $ con $ y<z $
Per essere poi $ y $ positivo deve essere $ z(z+3)>4026 $ che è vera per $ z>61 $
Ora se pongo $ z=62 $ trovo la prima ed unica coppia $ (60,2) $
Unica perchè al crescere minimo di $ z $ si ha uno spropositato crescere di $ y $ che va contro l'ipotesi!($ z=x+y>y $)

[LudoP]

$e^x$ è invertibile, ma non assume mai valori negativi.

Non sono tanto d'accordo. Per essere invertibile deve essere iniettiva e suriettiva; $e^x$ non e` suriettiva se la vedi come funzione $\Bbb R \rightarrow \Bbb R$, percio` non e` invertibile. Certo, se la vedessi come funzione $\Bbb R \rightarrow \Bbb R^+$, allora si`; ma si tratta di due funzioni diverse.

[jordan]

$e^x$ non e` suriettiva se la vedi come funzione $\Bbb R \rightarrow \Bbb R$, percio` non e` invertibile. Certo, se la vedessi come funzione $\Bbb R \rightarrow \Bbb R^+$, allora si`; ma si tratta di due funzioni diverse.

Mmh sì; dipende se, data una qualunque corrispondenza, restringiamo il codomonio alla sua immagine, rendendola "di forza" suriettiva. Sarà anche questione di definizione, hai ragione