Pelo princípio da casa dos pombos, como calcular o menor número de elementos a selecionar para garantir que haja pelo menos um de cada categoria?

Selecionar a soma de todas as categorias, exceto a menor, e somar 1.

Explicação:
Segundo o pior caso, podemos escolher todos os elementos de todas as categorias exceto a menor; ao escolher mais uma, obrigatoriamente teremos um da categoria restante. Assim, se as categorias têm tamanhos \(s_1,\dots,s_k\) e \(s_{\min}\) é o menor, o mínimo necessário é \(\sum_{i=1}^k s_i - s_{\min} + 1\), equivalente a \(\sum_{i\neq j}s_i + 1\) (soma das maiores +1).

Exemplo:
Suponha quatro categorias com 10, 7, 5 e 3 itens (total \(=25\), menor \(=3\)).
Aplicando a regra:
\(10+7+5+1=23\)
ou usando a fórmula:
\(25-3+1=23\).
Logo, selecionar 23 itens garante que haja pelo menos um de cada categoria.