Is my reasoning here correct or is there a better way to solve this problem?

Given a set of items $I$ and a set of baskets $B$, where each basket contains $k$ items, what is the maximum number of pairs of items that show up at least once among the baskets? A pair is defined as $(i_1, i_2); i_1 \neq i_2; i_1, i_2 \in B_j$ i.e. pairs do not cross basket boundaries.

(I think) I solved the problem by doing the following:

$$ \text{max number of pairs} = \begin{cases} \binom{\lvert I \rvert}{2}, & k\lvert B \rvert \lt \binom{\lvert I \rvert}{2} \\ \binom{\lvert I \rvert}{k\lvert B \rvert}\binom{k}{2}\lvert B \rvert, & \text{otherwise} \end{cases} $$

My reasoning was that I could maximize the number of pairs if I could get the maximum distinct number of pairs in each of the $\lvert B \rvert$ baskets. This should work when $k\lvert B \rvert \lt \binom{\lvert I \rvert}{2}$. Otherwise, there will be at least one pair repeated, but it is possible to create an instance of the problem where all $\binom{\lvert I \rvert}{2}$ possible pairs from $I$ are observed among the $\lvert B \rvert$ baskets.

Is this correct? Was there a better (or just different) way to do it?

  • $\begingroup$ Presumably there are $|I|$ kinds of items, but as many of each kind as you want. Is that correct? $\endgroup$ – Ross Millikan Sep 18 '18 at 16:59
  • $\begingroup$ Yes, that is correct. And now that I think about it, I've been glossing over the fact that each basket itself is a set of items. So I think there must be $k$ distinct items in each basket by definition of a basket. e.g. If I buy 5 packs of diapers, it still only counts for 1 item in my basket on my receipt. But I hope it doesn't change the problem. $\endgroup$ – matthiasdenu Sep 18 '18 at 17:05
  • $\begingroup$ Oh sorry! I need to be more careful; $I$ is a set of distinct items. $\endgroup$ – matthiasdenu Sep 18 '18 at 17:11
  • $\begingroup$ That is how I read it, but the same item can be in multiple baskets. $\endgroup$ – Ross Millikan Sep 18 '18 at 17:12

There are only ${|I| \choose 2}=\frac 12|I|(|I|-1)$ pairs, so if there are lots of baskets you will have that many. Your first inequality is in the wrong direction because you want lots of baskets to get the maximum number of pairs.

Each basket can contain at most $\frac 12k(k-1)$ pairs, so if there are lots of items and all the pairs are distinct there will be $\frac 12k(k-1)|B|$ pairs.

It gets hard in the middle range. Suppose there are two baskets, each of which can hold six items, and eight kinds of items. There are $28$ pairs and each basket can hold $15$ pairs, but you can't get them all. If an item is in only one basket it can only participate in $5$ pairs of the $7$ it could participate in. You only have room to put four types of item in each basket, so your baskets have $1,2,3,4,5,6$ and $1,2,3,4,7,8$ or something like it. This means you are missing four pairs-$57,58,67,68$ so have only $24$ pairs. I don't know of an easy formula here.


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.