0
$\begingroup$

I am trying to prove that the integer function: $$ \pi(a,b) = a + \frac{b(b-1)}{2} \qquad 1\leq a < b $$ is a pairing function; which amounts to showing that it is injective. (My end-goal would be to use it as a symmetric pairing function.)

AFAICS, proving that it is injective amounts to showing that given four integers $1\leq a<b$ and $1\leq c<d$, the following implication holds: $$ a + \frac{b(b-1)}{2} = c + \frac{d(d-1)}{2} \quad\Rightarrow\quad a=c \quad b=d $$

I have a feeling that proving this involves finding two inequalities on $a$ and $c$ (or $b$ and $d$), which can only both be true in case of equality. But I am not sure whether this approach is indeed correct, and if so, what these inequalities would be.

So far, using substitution and re-arranging terms, I have reached the following inequalities, which should hold simultaneously: $$ d(d-1) + 2c < b(b+1)\\ b(b-1) + 2a < d(d+1) $$ I like these because of the symmetry between $b$ and $d$, and the assymmetry $x(x-1)$ and $x(x+1)$, but I am not sure about the next steps needed to conclude.


Edit: it looks like @Brian_Scott solved this in the comments of this post. However I do not understand the proof just yet.. If anyone could please help flesh it out a little bit more, that would be greatly appreciated.

$\endgroup$
3
$\begingroup$

For $1\leq a< b$ and $1\leq c < d$, suppose: $a + \frac{b(b-1)}{2} = c + \frac{d(d-1)}{2}$ and $(a,b) \neq (c,d)$.

Wlog assume $d>b$ (if they are equal, then $a=c$ and we have a contradiction), then:

$$a -c = \frac{d(d-1)-b(b-1)}{2} = \frac{(d-b)(d+b-1)}{2}\geq \frac{(d+b-1)}{2}> \frac{2b-1}{2}=b-\frac{1}{2}>a$$

Therefore $c < 0$, and we have a contradiction.

$\endgroup$
  • $\begingroup$ I can see why $b - 1/2 > a$, which leads to $c < 0$ and a contradiction; but not $b - 1/2 > a-c$, is that a typo? $\endgroup$ – Sheljohn Jul 16 at 10:52
  • $\begingroup$ $-c\leq -1$ and $a<b$ so $a-c<b-1<b-\frac{1}{2}$. Contradiction because $a-c<a-c$. But yeah, your idea also works. $\endgroup$ – AO1992 Jul 16 at 10:57
2
$\begingroup$

You can prove this via contradiction. Suppose $\pi(a,b)=\pi(a',b')$.

First case $b=b'$, show this implies $a=a'$.

Second case, $b < b'$. Hence $b' \ge b+1$. This gives you an inequality for $a-a'$ which yields a contradiction with the assumption $a < b$.

Edit: As $b' \ge b+1$ we have $\frac{b'(b'-1)}{2}-\frac{b(b-1)}{2}\ge \frac{(b+1)b}{2}-\frac{b(b-1)}{2}=b$. Now if $\pi(a,b)=\pi(a',b')$ this gives $a-a'>b$ which contradicts $a <b$ where I used that $b' > b$ implies $a' < a$.

$\endgroup$
  • $\begingroup$ The part "This gives you an inequality for $a-a'$" in unclear to me, could you please add a bit more detail? $\endgroup$ – Sheljohn Jul 16 at 10:48
  • $\begingroup$ $b' \ge b+1$ give you an estimate for the difference between the $b$ and $b'$ terms. The $a$ and $a'$ must make up for that difference. $\endgroup$ – quarague Jul 16 at 10:52
  • $\begingroup$ This gives you $a-a' \geq (b + b' - 1)/2 \geq b$, leading to $a' < 0$, is that what you mean? $\endgroup$ – Sheljohn Jul 16 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.