Let's say I have $N$ people each with a score tuple $(x_i, y_i)$. The total score each person $i$ receives is $Xx_i + Yy_i$ where $X$ and $Y$ are both positive integers (without any upper bound). The $X$ and $Y$ values are the same for every person. In other words, they act as weights for the score tuple of every person.
Now the question is, assuming we are free to choose any value for $X$ and $Y$, in how many ways can we rank each person? (i.e. in how many ways can we sort them by total score)
Assume that when the scores are equal, we can break ties arbitrarily, meaning that if for example we have two persons $A$ and $B$ and both have equal score tuple, we can rank them in two ways total.
I have made very little progress with this. Some observations I've made are:
- If all score tuples are in order, such that $x_i < x_{i+1}$ and $y_i < y_{i+1}$, then it's only possible to rank them in one way. For example $(1, 1)$, $(2, 3)$, $(6, 8)$ has only one possible order, no matter how we choose $X$ and $Y$.
- If we have N people and all the tuples are equal, then the answer should be $N!$.
- If we have two people with $(6, 10)$ and $(10, 6)$, then there are two ways of ranking them.
Also in the case of $(1, 1)$, $(2, 2)$, $(6, 10)$, $(10, 6)$, $(20, 20)$, we can tell that some tuples are in order (following observation 1), and the ones in the middle are the same as observation 3, so the total ways of ranking them is also 2. The two possible ways are:
$(1, 1)$, $(2, 2)$, $(6, 10)$, $(10, 6)$, $(20, 20)$
$(1, 1)$, $(2, 2)$, $(10, 6)$, $(6, 10)$, $(20, 20)$
I kind of think one way would be to discard all tuples that don't generate any "conflict" (in the sense of observation 1) and keep only the ones that could be ranked in many ways, and then do some kind of formula, but I'm not capable of finding it as of yet.
Note: I'm not 100% sure if my observations are correct.
Best Answer
Imagine the points $(x_i,y_i)$ in the plane, and consider the family of lines orthogonal to the normal vector $(X,Y)$. These are the lines with slope $-\frac XY$, so you can choose any negative rational slope $m$ and the points get ranked according to which of the family of lines with slope $m$ they’re on.
Now let $n_m$ be the number of lines with (negative rational) slope $m$ containing more than one point, and let $n_{mk}$ with $1\le k\le n_m$ be the number of points on the $k$-th line with slope $m$. Points that lie on the same line have the same score, so if you choose one of the “ambiguous” values for $m$ such that $n_{mk}$ points lie on a line, there are $n_{mk}!$ different choices for ordering those points, and if $n_m$ lines have more than one point, an order can be freely chosen on each line independently, so there are $\prod_{k=1}^{n_m}n_{mk}!$ different orders for this value of $m$. One of these orders is the same as the one corresponding to slope $m+\epsilon$, and one is the same as the one corresponding to slope $m-\epsilon$, so if we add all these contributions, we’re double-counting all the unambiguous orders between the ambiguous slopes, so we have to subtract $1$ for each ambiguous slope and then add $1$, so the number of different orders is
$$ 1+\sum_m\left(\prod_{k=1}^{n_m}n_{mk}!-1\right)\;. $$