Quantos valores podem ser doados com 4 cédulas?

por be_osc Ter 05 Mar 2019, 16:53

Dispõe-se de 4 cédulas, nos valores de 1, 5, 10 e 50 reais, com as quais pretende-se fazer uma doação para uma instituição beneficente. Nessas condições, quantos valores diferentes (não nulos) poderão ser doados?

Resposta: 15

Very Happy

por be_osc Ter 05 Mar 2019, 17:24

Consegui resolver.

Se doarmos 4 cédulas temos 1 possibilidade (66)
Se doarmos 1 cédula temos 4 possibilidades (1, 5, 10, 50)
Se doarmos 2 cédulas, temos 6 possibilidades = C4,2
Se doarmos 3 cédulas, temos 4 possibilidades = C4,3

Somando: 1+4+6+4 = 15

por **Elcioschin** Ter 05 Mar 2019, 18:51

Outro modo:

O total de possibilidades é 2⁴ = 16
Acontece que temos que descontar a possibilidade C(4, 0) = 1, pois não se pode doar zero.

x = 16 - 1 ---> x = 15

Para um valor n qualquer ---> x = 2ⁿ - 1

por be_osc Ter 05 Mar 2019, 20:10

Elcioschin escreveu:Para um valor n qualquer ---> x = 2ⁿ - 1

De onde vem essa relação?

por **Mateus Meireles** Ter 05 Mar 2019, 20:15

be_osc escreveu:
Elcioschin escreveu:Para um valor n qualquer ---> x = 2ⁿ - 1

De onde vem essa relação?

Me metendo um pouco no tópico, o Élcio usou que cada cédula pode ou não participar da doação, daí serem duas possibilidades. Para n cédulas, 2ⁿ. O -1 surge para retirarmos o caso em que nenhuma cédula participa da doação, ou seja, nenhuma valor é doado. Só tem que tomar cuidado com outros problemas que apareçam cédulas combinadas que resultem em uma mesma soma de valor doado, o que não é o caso desse problema.

por be_osc Ter 05 Mar 2019, 20:24

Mateus Meireles escreveu:Só tem que tomar cuidado com outros problemas que apareçam cédulas combinadas que resultem em uma mesma soma de valor doado, o que não é o caso desse problema.

Caramba, um problema desses seria muito complicado lol.

Obrigado por responder, eu só não tinha entendido o 2ⁿ.

Boa noite!

por **Elcioschin** Qua 06 Mar 2019, 23:29

Uma explicação para a fórmula:

Seja o conjunto com 3 elementos {a, b, c}

Quantos subconjuntos ele tem? É simples:

1) Subconjunto vazio: {Ø}
2) Subconjuntos com 1 elemento: {a}, {b}, {c}
3) Subconjuntos com 2 elementos: {a, b}, {a, c), {b, c}
4) Subconjuntos com 3 elementos {a, b, c}

Total de subconjuntos = 8 = 2³ ---> Descontando {Ø} ---> 2³ - 1 = 7

Para n elementos ---> 2ⁿ --> Descontando {Ø} ---> 2ⁿ - 1