Como, pelo princípio da casa dos pombos, calcular o número mínimo de retiradas para garantir um par (esquerda+direita) de uma cor específica?

Retire todas as botas de outras cores e, entre as da cor desejada, retire \(p+1\) botas, onde \(p\) é o número de pares dessa cor.

Explicação:
Calcule primeiro as botas não desejadas (cada par = 2 botas). No pior caso você pode tirar todas elas sem obter a cor desejada. Depois, entre as botas da cor desejada existem \(p\) esquerdas e \(p\) direitas; para garantir obter uma de cada, pode ser necessário tirar \(p+1\) dessas botas (pois as primeiras \(p\) podem ser todas do mesmo pé).
Logo, total mínimo = (botas de outras cores) + \((p+1)\).

Exemplo:
Suponha 4 pares vermelhos (desejada), 2 pares azuis e 1 par pretos.
Botas não desejadas = \(2\cdot2 + 2\cdot1 = 4+2 = 6\).
Aqui \(p=4\), então precisa \(p+1 = 5\) botas vermelhas.
Total = \(6 + 5 = 11\).