Counting $2010^2$-tuples

Question

Here's a problem i invented myself, but i'm not sure about my solution. I'll show it later, so people can enjoy trying to find one:

Consider the function $f:\mathbb{R}^2\to\{1,2,...,2012\}$ that satisfies the following rule: If $a<b<c$, then $f(a,c)=f(b,c)=f(a,b)$ and $f(b,a)=f(c,a)=f(c,b)$.

Let $x_1,x_2,...,x_{2010}$ be a sequence of real numbers, which are all different.

Find the number of possible ordered $2010^2$-tuples

$$\Bigl(f(x_1,x_1),f(x_1,x_2),\ldots,f(x_1,x_{2010}),f(x_2,x_1),f(x_2,x_2),\ldots,f(x_2,x_{2010}),\ldots,f(x_{2010},x_{2010})\Bigr)$$

Answer 1

The conditions imply that all values of $f(a,b)$ with $a\lt b$ are the same and that all values of $f(a,b)$ with $a\gt b$ are the same. Thus we have $2010$ values $f(a,a)$ and two different values for different arguments, for a total of $2012$ values, which is also the number of available values in the range.

Thus there are $2012^{2012}$ different ordered tuples.

Answer 2

From your first condition, we must have that $f(x,y)$ can only attain a single value if $x<y$. Suppose that $a<x<y<b$. Then $f(x,y)=f(x,b)=f(a,b)$, and given $x<y$ and $x'<y'$, we can compare $f(x,y)$ and $f(x',y')$ to $f(\min(x,x'),\max(y,y'))$. Similarly, we can only attain a single value for f(x,y) if $x>y$.

Permuting the $x_i$ permutes the resulting ordered tuple, so we can assume that the $x_i$ are sorted. For ease of visualization, let us represent the tuple as a square matrix with $f(x_i,x_j)$ at entry $(i,j)$. Then the conditions mean that all the entries above the diagonal will be the same, all the entries below the diagonal will be the same, and we have no other constraints. Thus, to specify $f$ we must specify the 2010 values along the diagonal, the single value above the diagonal, and the single value below the diagonal. For each choice we have $2012$ options. Therefore there are $2012^{2010+2}=2012^{2012}$ possibilities.