# Counting $2010^2$-tuples

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)$$

-
There's a preview under the text area where you compose the question. If it isn't working for you, it might be worthwhile to file a bug report at meta.math.stackexchange.com (stating your browser and OS version). –  joriki Oct 3 '12 at 11:29
@joriki: I’m pretty sure that it’s the same as this bug. Davide Cervone is working on it; the temporary work-around is to use the MathJax contextual menu to set Math Settings->Renderer->SVG. –  Brian M. Scott Oct 3 '12 at 11:31
@Brian: Interesting. MathML works for me, too, even though I get a warning that not all features might render correctly in my browser. –  joriki Oct 3 '12 at 11:34
Is the second value meant to be $f(x_1,x_3)$? –  joriki Oct 3 '12 at 11:37
Also, what's the role of $x_{2011}$ and $x_{2012}$? Why are they in the sequence but then never get used? –  joriki Oct 3 '12 at 11:40

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.

-
I agree. The problem is that the question can be interpreted otherwise: assuming that the sequence is variable. That's what i did and got $2012^{2010}\cdot(2012+\frac{2012!}{2})$ as answer. I now finally understand the incertainty about my solution. –  barto Oct 3 '12 at 13:54
@barto: It doesn't matter whether the sequence is variable. The values of the sequence play no role in the count; they're just $2010$ arbitrary labels, and the only thing we need to know about them is that they're all different and can be compared using $\lt$. –  joriki Oct 3 '12 at 23:35
I don't understand. Because, if $x_1<x_2<x_3$, then $f(x_1,x_2)$ and $f(x_2,x_3)$ will be the same. But if $x_2<x_1<x_3$, then $f(x_1,x_2)$ and $f(x_2,x_3)$ are not always the same. –  barto Oct 4 '12 at 14:49
@barto: Sorry, my mistake. –  joriki Oct 4 '12 at 14:52
@barto: How can you be uncertain about the interpretation of a problem you invented yourself? It's meant the way you meant it, no? –  joriki Oct 4 '12 at 14:58

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.

-