Como provar que um número não pode estar em um subconjunto de k elementos cuja soma deve ser um valor fixo?

Comparando a soma exigida dos outros k-1 elementos com a soma máxima possível desses k-1 elementos; se a soma máxima for menor, o número não pode pertencer ao subconjunto.

Explicação: primeiro determine a soma total e a soma alvo do subconjunto.
Se o número \(x\) estivesse no subconjunto de tamanho \(k\), os outros \(k-1\) elementos precisariam somar \(S_{\text{alvo}}-x\).
Calcule a soma dos \(k-1\) maiores números disponíveis, se essa soma for menor que \(S_{\text{alvo}}-x\), então é impossível que \(x\) faça parte do subconjunto, pois mesmo escolhendo os maiores valores não se atinge a soma requerida.

Exemplo:
Considere os cartões \(1\) a \(12\).
A soma total é \(1+2+\dots+12=78\), logo cada caixa deve somar \(78/2=39\).
Se uma caixa tem \(4\) cartões e testamos \(x=1\) nela, os outros \(3\) teriam de somar \(39-1=38\).
Mas os três maiores números restantes são \(12,11,10\) e \(12+11+10=33<38\).
Como 33 é menor que 38, é impossível que o \(1\) esteja nessa caixa de 4 cartões.