Flashcard FC303332
Se em uma coleção qualquer todo subconjunto de tamanho k contém ao menos um elemento que não é A, qual o máximo de elementos do tipo A que a coleção pode ter?
Princípio da Casa dos Pombos
FGV · 2022
Se em uma coleção qualquer todo subconjunto de tamanho k contém ao menos um elemento que não é A, qual o máximo de elementos do tipo A que a coleção pode ter?
Mostrar resposta e comentário
Resposta
No máximo k-1 elementos do tipo A.Se houvesse ≥ k elementos do tipo A, poderíamos escolher k desses elementos e obter um subconjunto sem nenhum elemento que não é A, contradizendo a hipótese. Portanto o máximo é k-1.
Exemplo:
Coleção com n = 10 objetos e condição: todo subconjunto de tamanho k = 5 tem ao menos um que não é vermelho. Então o máximo de objetos vermelhos é \(k-1=4\).
Logo o número mínimo de não-vermelhos é \(n-(k-1)=10-4=6\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300422
Conteúdo do catálogo FC Concursos · Atualizado em