Seja
, onde
para todo
. Dados
,
, encontre condições necessárias e suficientes para que:
.
Passo 1
Beleza, o enunciado diz o seguinte: temos um conjunto
com todos os
. Queremos achar quando, para duas variáveis diferentes
e
, vale sempre
Conteúdo: é basicamente teoria de “knapsack” (mochila) e cobertura (“cover”). A gente vai usar a ideia de que, se colocar 1 em
e
viola a capacidade
, então nunca dá para ter os dois iguais a 1. E vice-versa.
Passo 2
Primeiro, mostramos que
Teoria: se
, qualquer vetor
que tenha
e
faria
,
violando a restrição da mochila. Logo, não há com os dois 1 juntos, e sempre dá
.
violando a restrição da mochila. Logo, não há
Passo 3
Agora a recíproca: suponha que para todo
valha
. Se por acaso tivéssemos
então o vetor que define
satisfazeria
ou seja, estaria em , mas tem
, contradição. Logo é impossível
. A única opção é
ou seja, estaria em
Resposta
Condição necessária e suficiente: