How minimize $\sum p_b \ln{p_b}$? I have a multiset $A = \{a_1,\dots,a_n\}$ of integers. Let $q = P(a_i = a_j)$ when $i$ and $j$ are chosen independently and uniformly from $\{1,\dots, n\}$.  Let $B$ be the set of integers in $A$. We know that $|B| \leq n$.  Finally let $p_b = P(a_i = b)$ when $i$ is chosen uniformly from $\{1,\dots, n\}$.

How small can $-\sum_{b \in B} p_b \ln{p_b}$ be as a function of $q$ and $n$?

 A: Just to make contact with wikipedia, I'll note that $S=-\sum p_b \ln p_b$ is the entropy and $q$ is the Simpson index. As other people have noted, there's some trickiness with there being only certain allowed $(n,q)$ pairs, so to avoid this let's assume that $n$ is large and $q$ is not too close to 0 or 1. 
To maximize the entropy, you want to spread out the distribution as much as possible, without having the Simpson index fall below $q$. The distribution that does this has $p_1 \approx \sqrt{q}$, $p_i=1/n$ for $i=2,\ldots,\sim n(1-\sqrt{q})$. (Obviously, for finite $n$, $p_1$ will have to be slightly smaller than $\sqrt{q}$.) This gives $S\sim (1-\sqrt{q})\ln n$.
To minimize the entropy, you want to concentrate the distribution as much as possible, without having the Simpson index go above $q$. To do this, let $|B|=\lceil 1/q\rceil$, and have $p_1, \ldots, p_{\lfloor 1/q \rfloor}$ close to $q$, with $p_{\lceil 1/q\rceil}$ getting the small remainder of the probability. This gives $S\sim -\ln q$.
Note that this also works the other way -- given $n$ and $S$, these same distributions give the maximum and minimum possible values of $q$.
A: A beginning:
In the first place a set $B:=[m]$ is given, and for each $k\in B$ we have a multiplicity $f(k)\in{\mathbb N}_{\geq1}$. The pair $(B,f)$ constitutes the multiset $A$ in your question.
Put $\sum_{k=1}^m f(k)=:n$. Then the probability that you choose the value $k$ when picking a random element from $A$ is ${f(k)\over n}=:p_k$, and the probability $q$ that you choose two equal values in two independent choices is given by
$$q={1\over n^2}\sum_{k=1}^m f^2(k)=\sum_{k=1}^m p_k^2\ .$$
It follows that we have to maximize/minimize the function
$$H(p):=-\sum_{k=1}^m p_k\>\log p_k$$
under the constraints
$$p_k\geq0,\quad \sum_{k=1}^m p_k=1,\quad \sum_{k=1}^m p_k^2=q\ .$$
Consider this as a continuous optimization problem. Depending on the value of $q$, the sphere $\sum_k p_k^2=q$ may intersect the simplex $p_k\geq0$, $\>\sum_k p_k=1$ in a complicated way, and setting up a simple Lagrange multiplier scheme does not sufficiently take care of the global situation, so much the more as it will lead to transcendental equations. But it seems that the following Lemma is true: When $H$ is extremal at an admissible ${\bf p}$ then we cannot have three values $p_1>p_2>p_3>0$. This is corroborated by the follwing figure which shows the level lines of $H$ on a subsimplex $p_1+p_2+p_3=s$ for $s=0.4$ and in red a curve $p_1^2+p_2^2+p_3^2={\rm const.}\ $. One can see that the red curve is tangent to the level lines of $H$ only in points where  two of the $p_k$ are equal.

Therefore one would have to do the following: For all possible choices of $m_1\geq0$, $m_2\geq0$ with $m_1+m_2\leq m$  solve
$$m_1p_1+m_2p_2=1,\qquad m_1p_1^2+m_2p_2^2=q$$
for $p_1$ and $p_2$. When an admissible solution exists compute the corresponding $$H({\bf p})=-m_1\> p_1\log p_1-m_2\>p_2\log p_2\ .$$
The smallest and the largest values found in this way are the extremal values of $H$ under the given constraint.
