0
$\begingroup$

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

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

  • 0
    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 http://meta.math.stackexchange.com (stating your browser and OS version).2012-10-03
  • 1
    @joriki: I’m pretty sure that it’s the same as [this bug](http://meta.math.stackexchange.com/a/6248/12042). Davide Cervone is working on it; the temporary work-around is to use the MathJax contextual menu to set Math Settings->Renderer->SVG.2012-10-03
  • 0
    @Brian: Interesting. MathML works for me, too, even though I get a warning that not all features might render correctly in my browser.2012-10-03
  • 0
    Is the second value meant to be $f(x_1,x_3)$?2012-10-03
  • 0
    Also, what's the role of $x_{2011}$ and $x_{2012}$? Why are they in the sequence but then never get used?2012-10-03
  • 0
    Do I interpret the question correctly as counting the number of possible matrices $\bigl(f(x_i,x_j)\bigr)_{0 as $x_1,\ldots,x_{2010}$ each range over the reals and $f$ ranges over all possible functions of the type described? It is not that the question is hard, but why on earth should anyone be interested in knowing that?2012-10-03
  • 0
    @Marc Van Leeuwen: yes, i have changed my original question and corrected the mistakes.2012-10-03

2 Answers 2

3

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.

  • 0
    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.2012-10-03
  • 0
    @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$.2012-10-03
  • 0
    I don't understand. Because, if $x_1, then $f(x_1,x_2)$ and $f(x_2,x_3)$ will be the same. But if $x_2, then $f(x_1,x_2)$ and $f(x_2,x_3)$ are not always the same.2012-10-04
  • 0
    @barto: Sorry, my mistake.2012-10-04
  • 0
    @barto: How can you be uncertain about the interpretation of a problem you invented yourself? It's meant the way you meant it, no?2012-10-04
  • 0
    Right, but i can't exclude other interpretations. The question was not that clear.2012-10-04
2

From your first condition, we must have that $f(x,y)$ can only attain a single value if $x. Suppose that $a. Then $f(x,y)=f(x,b)=f(a,b)$, and given $x and $x', 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.