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.

Improve this question
$\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$
    – Gerhard Paseman
    Jun 5, 2018 at 8:34

2 Answers 2

Reset to default
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)$.

Improve this answer
$\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\})$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.