1
$\begingroup$

Assume there is a static max of N for either value, such that X <= N and Y <= N.

I would like a function such that:

func(X0,Y0) != func(X1,Y1) for all values IFF: 1. X0,Y0,X1,Y1 <= N 2. X0 != X1 and Y0 != Y1 3. X0 != Y1 and Y0 != X1 

So to be clear, func(X,Y) = func(Y,X).

The result of this function should be an integer, and it should also be simple and trivial to calculate X and Y from the result of the function.

I'd like to also be able to do this without determining which of X or Y is the max.

Is this something that is impossible by principle?

Thanks!

EDIT:

Oops! N is non-negative.

  • 0
    Surely $x$ and $y$ are non-negative also?2012-04-22

3 Answers 3

3

$f(x,y)=2^{x+y}3^{|x-y|}$ should do. Given an output, divide by 2 repeatedly until you get an odd number, then divide by 3 repeatedly until you get 1; counting up the numbers of divisions, you find $m$ and $n$ such that the output was $2^m3^n$. Now to retrieve $x$ and $y$, all you have to do is solve the equations $x+y=m$, $x-y=n$, getting $x=(m+n)/2$, $y=(m-n)/2$. The solution is unique (except for swapping $x$ and $y$, and that's what you asked for), by the unique factorization theorem.

  • 0
    @Gerry, admittedly, I was just hoping for a slightly more general (yet still constructive) answer regardless of the sign of $x$ and $y$. But if we can assume $x, y\geq 0$, then you've finished the question quite nicely.2012-04-23
2

How about this: let $f(x,y) = (2N+1)(x-y)^2 + (x+y)$. Then, since $0 \leq x+y \leq 2N$ (I'm assuming your integers are non-negative), you can easily extract the sum and difference of $x$ and $y$ by dividing by $2N+1$ and looking at the quotient and remainder.

2

You could use the Cantor pairing function, making the first argument max(X,Y) and the second min(X,Y). As described in the article, you can recover the two arguments, but you have thrown away the info of which is the greater.

  • 0
    Or even better, use a triangular-number inspired method to get a bijection between $\mathbb{N}$ and $\{ (x,y) \in \mathbb{N}^2 \mid x \leq y \}$.2012-04-22