Injective mapping

Task number: 2816

Show that the mapping \(f: \mathbb N\times \mathbb N\to \mathbb N\) defined by the equation \(\displaystyle f(x,y)=\frac{(x+y)(x+y+1)}{2}+y \) is injective.

  • Hint

    First try to arrange the pairs \((x,y)\) such that the value of the function \(f\) increases.

  • Resolution

    Without loss of generality we first consider the case \((x+y)<(x'+y')\). Then

    \[ 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')\] .

    If \((x+y)=(x'+y')\) and \(y<y'\) we have \(f(x,y)<f(x',y')\) immediately.

    In the case that \((x+y)=(x'+y')\) and \(y=y'\) then also \(x=x'\). So the function \(f\) is injective.

Difficulty level: Moderate task
Solution require uncommon idea
Cs translation
Send comment on task by email