De quantos modos se pode iluminar uma sala que possui m lâmpadas?

Passo 1

O enunciado pergunta de quantos modos podemos iluminar uma sala que possui m lâmpadas. Aqui cada lâmpada pode estar acesa ou apagada, mas para que a sala fique iluminada precisamos que pelo menos uma lâmpada esteja acesa. Portanto vamos modelar o problema como a contagem de subconjuntos não-vazios de um conjunto de m lâmpadas.

Passo 2

Primeiro lembramos que um conjunto com m elementos tem, ao todo,
2^m
subconjuntos (pois para cada lâmpada podemos escolher “ligada” ou “desligada”).

Passo 3

Dentre esses 2^m subconjuntos, há exatamente um que é o subconjunto vazio (todas as lâmpadas desligadas), o qual não ilumina a sala.

Passo 4

Logo, o número de modos de iluminar (isto é, escolher pelo menos uma lâmpada acesa) é
2^m - 1

Resposta

2^m - 1

Exercícios de Livros Relacionados