(Insper-04) Um individuo é dito magnético se e somente se para qualquer conjunto de dez pessoas que o conhecem, existe no conjunto pelo menos uma pessoa que simpatiza com ele. Se exatamente 100 pessoas conhecem um individuo, para que ele seja magnético
a) é suficiente que dentre as 100 pessoas que conhecem o individuo, pelo menos 10 simpatizem com ele.
b) é necessário e suficiente que dentre as 100 pessoas que conhecem o individuo, pelo menos 51 simpatizem com ele.
c) é suficiente que dentre as 100 pessoas que conhecem o individuo. pelo menos 90 simpatizem com cle.
d) é necessário e suficiente que dentre as 100 pessoas que conhecem o individuo, pelo menos 91 simpatizem com ele.
e) é necessário que as 100 pessoas que conhecem o individuo simpatizem com ele.

Passo 1

Resumindo, temos um indivíduo conhecido por exatamente 100 pessoas. Dizemos que ele é magnético se, para qualquer grupo de 10 dentre essas 100 pessoas, existe ao menos uma que simpatiza com ele. O objetivo é achar uma condição sobre o número de simpatizantes entre as 100 que seja equivalente a essa definição.

Passo 2

Vamos modelar: seja S o conjunto das 100 pessoas que conhecem o indivíduo, e seja X\subseteq S o conjunto de quem simpatiza com ele. A condição “para qualquer conjunto de 10 pessoas que o conhecem, existe ao menos uma que simpatiza” significa exatamente que nenhum subconjunto de tamanho 10 de S está inteiramente dentro de S\setminus X (os que não simpatizam).

Passo 3

Se existisse um subconjunto de 10 não-simpatizantes, esse grupo violaria a condição: ele seria um grupo de 10 sem nenhum simpatizante. Logo, o tamanho de S\setminus X (número de não-simpatizantes) deve ser menor que 10. Assim,
|S\setminus X|\le9.

Passo 4

Como |S|=100, temos
|X| = |S| - |S\setminus X| \ge 100 - 9 = 91.
Isto é, é necessário e suficiente que haja pelo menos 91 simpatizantes entre as 100.

Resposta

d) é necessário e suficiente que dentre as 100 pessoas que conhecem o indivíduo, pelo menos 91 simpatizem com ele.