Skip to main content
2 of 2
deleted 15 characters in body

Achieving every possible ranking by rearranging weights

This problem actually arose as a question in the real world (see the paragraph "Origin of the problem" below).

Let $\mathbb{N}$ denote the set of the positive integers and let $n\in\mathbb{N}$. If $w:\{1,\ldots,n\}\to \mathbb{N}$ is a function (the letter $w$ stands for "weight function") and $S\subseteq \{1,\ldots,n\}$ we say that the score of $S$ with respect to $w$ is $$\text{sc}_w(S) = \sum_{k\in S}w(k).$$ Suppose that ${\cal A}$ is a set of subsets of $\{1,\ldots,n\}$ such that no member of ${\cal A}$ is contained in another member of ${\cal A}$, and let $a=|{\cal A}|$.

Question. Given a bijective map $\varphi:\{1,\ldots,a\}\to{\cal A}$, is it possible to find a weight function $w:\{1,\ldots,n\}\to \mathbb{N}$ such that for all $k\in\{1,\ldots,a-1\}$ we have $$\text{sc}_w(\varphi(k)) > \text{sc}_w(\varphi(k+1)) ?$$

(In more intuitive but less exact terms, is it possible to achieve any ranking of the members of ${\cal A}$ by cleverly choosing the weight function $w:\{1,\ldots,n\}\to\mathbb{N}$?)

Origin of the problem. A friend of mine is a math teacher and he noted that in the most recent exam, his students all had solved a different set of problems, such that no student had solved a subset of problems that another student had solved. Every problem gives a certain amount of points. For simplicity he assumed that the students get all points if they solved a certain problem, and no points otherwise. The question he asked me was whether he could achieve any ranking of his students by re-assigning the points to the problems.