Olimpíadas ⇒ (OBM) Combinatória

[Ashitaka]

Quantas funções f:{1, 2, 3, 4, 5} --> {1, 2, 3, 4, 5} satisfazem f(f(x)) = f(x) para todo x {1, 2, 3, 4, 5}?

Resposta

---

Gab: 196.

[PedroCunha]

Olá.

Solução da banca:

Para que

Código: Selecionar tudo

[tex3]f(f(x)) = f(x)[/tex3]

então a imagem de f deverá só conter pontos fixos. Utilizando esse fato temos:

Com 5 pontos fixos na imagem teremos 1 função possível.
Com 4 pontos fixos na imagem teremos

Código: Selecionar tudo

[tex3]\binom{5}{1} \cdot 4 = 20[/tex3]

funções
Com 3 pontos fixos na imagem teremos

Código: Selecionar tudo

[tex3]\binom{5}{2} \cdot 3^2 = 90[/tex3]

funções
Com 2 pontos fixos na imagem teremos

Código: Selecionar tudo

[tex3]\binom{5}{3} \cdot 2^3 = 80[/tex3]

funções
Com 1 ponto fixo na imagem teremos

Código: Selecionar tudo

[tex3]\binom{5}{4} \cdot 1^4 = 5[/tex3]

funções
logo o total de funções f satisfazendo

Código: Selecionar tudo

[tex3]f(f(x)) = f(x)[/tex3]

igual a 196.

Boa sorte com a resolução,

Att.,
Pedro

[Ashitaka]

Já faz bastante tempo, mas gostaria de deixar uma solução que vi há muito tempo, mas que não é minha:

"Primeiro caso: só tem um elemento no conjunto imagem: (cinco escolhe um), segundo caso: tem dois elementos no conjunto imagem: primeiro vamos escolher esses elementos: (cinco escolhe dois), os dois elementos escolhidos só podem ter imagem igual a eles mesmos pelo enunciado, mas os outros podem escolher livremente: 2.2.2, resultando em 80, terceiro caso tem três elementos no conjunto imagem: primeiro vamos escolher esses elementos: (cinco escolhe 3), os três elementos escolhidos só podem ter imagem igual a eles mesmos pelo enunciado, mas os outros podem escolher livremente: 3.3, resultando em 90, perceba que essa sequência nada mais é que (cinco escolhe k).(k elevado a 5 menos k), onde k varia de 1 até 5, logo queremos 5+80+90+20+1=196. Observação: organizar com esses binômios ajuda na generalização do problema."

Obrigado, Pedro.