For any set $X$ and cardinal $\kappa$ let $[X]^\kappa$ denote the collection of subsets of $X$ with cardinality $\kappa$. If $n$ is a positive integer, let $[n]:=\{1,\ldots,n\}$.

Let $V$ and $K$ be finite, non-empty sets and let $b$ be a positive integer with $b < |K|$. For the following, we think of $V$ as the set of "voters", and $K$ is the set of "candidates" and $b$ is the "ballot size". If $f:V \to [K]^b$ is a map, we can think of $f$ as an instance of "ballot casting", and $f(v)$ is the "ballot" of voter $v\in V$.

Define the set of voters for $k\in K$ by $$\text{vote}(k) = \{v \in V: k\in f(v)\}.$$ Call $k\in K$ is popular if $2\cdot \text{vote}(k) > |V|$, that is, more than half of the voters $v\in V$ have $k$ on their ballot $f(v)$.

For any integer $n>1$ we define the happy ballot size of $n$ as the smallest positive integer $b$ such that there is a finite nonempty set $V$ and a map $f:V \to [[n]]^b$ such that ever candidate $k\in[n]$ is popular. Denote the happy ballot size of $n$ by $\text{hb}(n)$.

Question. What is the value of $\lim \inf_{n\to\infty}\frac{\text{hb}(n)}{n}$?

  • 1
    $\begingroup$ @mathworker21 Presumably $[[n]]^b$ is the notation $[\dots]^b$ applied to $[n]=\{1,\dots,n\}$. $\endgroup$ – Bruno Le Floch Feb 5 at 12:38

Your Answer

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

Browse other questions tagged or ask your own question.