Prosté zobrazení
Úloha číslo: 2809
Dokažte, že zobrazení \(f: \mathbb N\times \mathbb N\to \mathbb N\) definované předpisem \(\displaystyle f(x,y)=\frac{(x+y)(x+y+1)}{2}+y \) je prosté.
Nápověda
Pokuste se nejprve uspořádat dvojice \((x,y)\) tak, aby hodnota funkce \(f\) rostla.
Řešení
Bez újmy na obecnosti uvažme nejprve případ \((x+y)<(x'+y')\). Potom
\[ f(x,y)=\frac{(x+y)(x+y+1)}{2}+y=\frac12(x^2+2xy+y^2+x+3y) <\frac12(x^2+2xy+y^2+3x+3y)=\] \[=\frac12(x+y+1)(x+y+2)\le\frac12(x'+y')(x'+y'+1) <\frac{(x'+y')(x'+y'+1)}{2}+y=f(x',y')\] .Je-li \((x+y)=(x'+y')\) a \(y<y'\) dostaneme \(f(x,y)<f(x',y')\) okamžitě.
Z rovností \((x+y)=(x'+y')\) a \(y=y'\) bychom dostali i \(x=x'\), funkce \(f\) je tedy prostá.
