1
$\begingroup$

Given are $2n$ (not necessarily distinct) subsets of the set $\{1,2,\dots,k\}$, with the first $n$ sets containing $1$. For an ordering $\sigma$ of $1,2,\dots,k$, its score is calculated as follows, starting from $0$: Going through $\sigma$, for element $x$ in the $i$th place of $\sigma$, for each set, if $x$ belongs to the set and is the $j$th element of the set to be considered, we add $\frac{1}{ij}$ to the score. Is it true that all $\sigma$ maximizing the score must have at least one element from the first $n$ sets in the first two places?

Example: $n=2,k=4$ and four subsets $\{1,2\},\{1,3\},\{2,3\}$ and $\{2,4\}$. The score of $\sigma=(2,1,3,4)$ is calculated by going through $\sigma$ in order. The element $2$ adds score $\frac{3}{1\times 1}$, the element $1$ adds score $\frac{1}{2\times 1}+\frac{1}{2\times 2}$, the element $3$ adds score $\frac{2}{3\times 2}$ and the element $4$ adds score $\frac{1}{4\times 2}$. This gives total score $\frac{101}{24}$.

For motivation, the score function is election scheme variant, and the question asks whether this function can represent voters who like a common candidate.

$\endgroup$
6
  • $\begingroup$ How and where did this specific question arise? $\endgroup$ Dec 23, 2020 at 8:13
  • $\begingroup$ @DavidRoberts As you can see from the Wikipedia link, this is a variant of a known election scheme which aims to apply proportional representation. Check out the link for more details. $\endgroup$
    – pi66
    Dec 23, 2020 at 9:10
  • $\begingroup$ No, I mean why are you interested in this and how did it come up in your research? The way it's formatted it looks to me like an assignment question, but I don't wish to assume it is, given that you are not a first-time poster here naively asking question. $\endgroup$ Dec 23, 2020 at 10:02
  • $\begingroup$ Are the $2n$ subsets all distinct, or can there be repetitions of the same set multiple times? If they represent vote choices the latter seems desirable, but in that case it must be clarified in the question (although I may be thinking too much about the context outside of the question itself). $\endgroup$
    – D. Dona
    Dec 23, 2020 at 13:32
  • $\begingroup$ @D.Dona Indeed they don't need to be distinct. $\endgroup$
    – pi66
    Dec 23, 2020 at 13:54

2 Answers 2

1
$\begingroup$

A quick computer program throws up a counter-example for $n=2$, $k=4$: take subsets $\{1\}, \{1, 2, 3\}, \{2\}, \{3\}$. The maximum score of $\frac{115}{36}$ is obtained by $(1, 2, 3, 4)$, $(1, 3, 2, 4)$, $(2, 1, 3, 4)$, $(3, 1, 2, 4)$, $(2, 3, 1, 4)$, $(3, 2, 1, 4)$ and the last two fail the condition.

$\endgroup$
0
$\begingroup$

Although I could not arrive to answering the question itself, I can at least say: all $\sigma$ maximizing the score must have at least one element from the first $\frac{4}{3}n$ sets in the first two places.

Take $\sigma$ not satisfying the above. In particular, all the elements of the first $n$ sets (including $1$) are at least in 3rd place, and the element $a$ in 1st place is appears in at most $\frac{2}{3}n$ sets: we want to prove then that swapping $1$ and $a$ makes the score grow.

The swapping has no effect on the score coming from the sets in which both elements are contained: in each such set, the parts of the score coming from $1$ and $a$ are exchanged and the score of all the other elements is left untouched (both their position in $\sigma$ and in $S$ are not altered). Obviously, the sets that do not contain either element are also unchanged.

Suppose that $S$ is one of the first $n$ sets: by hypothesis it contains $1$ but not $a$. The score coming from the elements after $1$ (in the original ordering of $\sigma$) are not altered, so what about the ones before $1$? Say that $1$ is the $l$-th element of $S$ wrt the ordering of $\sigma$, call $k_{1},\ldots,k_{l-1}$ the position in $\sigma$ of the elements of $S$ before $1$, and call $k_{l}$ the position of $1$: the old score of all such elements ($1$ included) was $$\frac{1}{1\cdot k_{1}}+\frac{1}{2\cdot k_{2}}+\ldots+\frac{1}{(l-1)\cdot k_{l-1}}+\frac{1}{l\cdot k_{l}},$$ and the new one is $$\frac{1}{2\cdot k_{1}}+\frac{1}{3\cdot k_{2}}+\ldots+\frac{1}{l\cdot k_{l-1}}+\frac{1}{1\cdot 1}.$$ The score has increased by $$1-\sum_{i=1}^{l-1}\frac{1}{i(i+1)k_{i}}-\frac{1}{lk_{l}},$$ and by our hypotheses $k_{l}>k_{l-1}>\ldots>k_{1}\geq 3$, so the worst increment happens for $k_{i}=i+2$ for all $i$; it's an elementary calculation then to show that $l=1$ is the worst case, for which the score increment becomes $\frac{2}{3}$.

If $S$ is not one of the first $n$ sets but it also contains $1$ and not $a$, then similarly its score increases, so there's no harm in ignoring them.

Finally, if $S$ contains $a$ but not $1$ (and there are at most $\frac{2}{3}n$ such $S$), after the swap all the elements of $S$ except $a$ have their score increased or unchanged, so we can ignore them again. The score of $a$ in a single $S$ before the swap was $1$, and after the swap is still positive, so the decrement is at most some $c<1$ (the same $c$ for all sets: we could bound $c$ away from $1$ in some way, if we felt like doing so, but I don't).

Putting all things together, the score increment is at least $\frac{2}{3}\cdot n-c\cdot\frac{2}{3}n>0$.

We can for sure do better with more care, but I'll leave it to more patient people. Also, of course "the first $\frac{4}{3}n$ sets" has no particular significance, any set of $\frac{4}{3}n$ sets including the $n$ sets where $1$ resides would do just fine.

$\endgroup$
3
  • $\begingroup$ To be clear, I doubt that swapping $1$ and $a$ can be improved enough to cover the case in the original question. For once, $1$ is not always one of the two elements at the top of the order of $\sigma$: taking $k=3$ and sets $\{1,2\},\{1,3\},\{2,3\},\{2,3\}$, the orders with $1$ in 3rd place are the ones that have the highest score. $\endgroup$
    – D. Dona
    Dec 23, 2020 at 20:52
  • $\begingroup$ The order doesn't matter, just the partition into n sets and n other sets, so 4n/3 seems wrong. There is an element, call in 1 which is in at least n of the sets. If more than $n$ then pick some $n$ of them to be the first half. There may be "other" elements which are not in any of those n distinguished sets. Is it ever possible that at least one of the highest score permutations has both of its first two members of this "other" type. $\endgroup$ Dec 24, 2020 at 4:19
  • $\begingroup$ @AaronMeyerowitz Yes, that's what I said in the very last sentence: talking about "the first $\frac{4}{3}n$ sets" has no particular significance. $\endgroup$
    – D. Dona
    Dec 24, 2020 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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