1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Of course there is the universal map sending k to 2^k, but you are looking for something more optimal I presume. You might consider ordering the subsets from smallest to largest, and then inducing a lexicographic order to break ties, and then start building a function which differs on the initial subsets contained in a member of A. For example, you don't want a function on 1,2,3,4 such that 1,3,5 and 2,4,5 get the same weighting. Gerhard "Might Be Set Cover Like" Paseman, 2018.06.05. $\endgroup$ Commented Jun 5, 2018 at 8:34

2 Answers 2

2
$\begingroup$

The following should give an example where you can't achieve every ranking.

Let $n=4$ and let $\mathcal{A} = \{ (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} = [4]^{(2)}$.

I claim that we can't achieve any ranking which starts $(1,2) > (3,4) > \ldots$.

Indeed, since $sc_w(1,2) > sc_w(3,4)$ if follows that $\max \{ w(1),w(2) \} > \min \{ w(3),w(4)\}$ and so by symmetry we may assume that $w(1) > w(4)$.

But then $sc_w(1,3) > sc_w(3,4)$, contradicting our assumption that only $(1,2)$ was better than $(3,4)$.

$\endgroup$
2
$\begingroup$

Consider $\mathcal A = \{\{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}\}$. Then $sc(\{1,3\}) - sc(\{1,4\}) = sc(\{2,3\}) - sc(\{2,4\})$. In particular, it's impossible to have $sc(\{1,3\}) > sc(\{1,4\})$ but $sc(\{2,3\}) < sc(\{2,4\})$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .