Se houver k categorias distintas, quantos elementos é preciso selecionar para garantir que dois pertençam à mesma categoria?

k+1

Explicação:
Pelo Princípio da Casa dos Pombos, no pior caso escolhe-se um de cada categoria, totalizando \(k\) sem repetições, portanto é necessário mais um para assegurar uma repetição, ou seja \(k+1\).

Exemplo:
Temos uma caixa com 5 cores de botões, queremos garantir dois da mesma cor. Aqui \(k=5\), então precisamos de \(k+1\) retiradas, \(5+1=6\). Assim, ao retirar 6 botões, necessariamente haverá pelo menos dois da mesma cor.