Questão M03 da 2ª fase da FUVEST 2023

Question

Considerando A = \{1,2,3,4\} e B = \{1,2,3,4,5,6\},

a) quantas funções f: A \to A (não necessariamente sobrejetoras) existem?

b) quantas são as funções f: B \to B que satisfazem f(f(n)) = n, para todo n \in B?

c) escolhendo aleatoriamente uma função f: B \to B bijetora, qual é a probabilidade de f ter ao menos um ponto fixo?

Note e adote:
Dizemos que n \in B é um ponto fixo de f se f(n) = n.

Answer 1

Questão M03 da 2ª fase da FUVEST 2023

2º dia · Matemática

Considerando A = \{1,2,3,4\} e B = \{1,2,3,4,5,6\},

a) quantas funções f: A \to A (não necessariamente sobrejetoras) existem?

b) quantas são as funções f: B \to B que satisfazem f(f(n)) = n, para todo n \in B?

c) escolhendo aleatoriamente uma função f: B \to B bijetora, qual é a probabilidade de f ter ao menos um ponto fixo?

Note e adote:
Dizemos que n \in B é um ponto fixo de f se f(n) = n.

Reportar erro na questão

Resolução comentada

Resposta esperada pela FUVEST

a) O número de funções possíveis é igual a 4^4 = 256.

b) Permutando 0 par: 1 opção (identidade).

Permutando 1 par: \frac{6\times 5}{2} = 15 combinações.

Permutando 2 pares: \frac{\frac{6\times 5}{2}\times \frac{4\times 3}{2}}{2} = 45 combinações.

Permutando 3 pares: \frac{\frac{6\times 5}{2}\times \frac{4\times 3}{2}}{6} = 15 combinações.

Total: 76 funções.

c) O diagrama em árvore a seguir ilustra as sequências sem repetição e que não possuem ponto fixo.

[Figura: Diagrama de árvore com ramificações a partir do nó superior 1 até 2 (3,4,5,6), desdobrando-se pelos níveis sucessivos até o nível 6 inferior para ilustrar os casos de desarranjos]

Entre parênteses, estão as opções que são análogas, em número de casos. Cada nível da árvore representa o possível valor da função em um número, começando do 1, no nível superior, e terminando em 6, no nível inferior. Cada nó é feito escolhendo algum valor diferente do nível correspondente e que ainda não apareceu na sequência. Por exemplo: o valor de f(1) pode ser 2,3,4,5 ou 6. Se escolhemos f(1)=2 (e os outros casos são análogos), podemos ter f(2)=1 ou f(2)= 3 (ou 4,5,6, que são casos análogos). Somando todas essas combinações, não se esquecendo de multiplicar pelo número de possibilidades análogas em cada nó, obtêm-se 265 funções sem ponto fixo. Como o total de funções bijetoras é 6! = 720, são 720 – 265 = 455 funções com ponto fixo. Logo, a probabilidade é 455/720, ou 91/144.

Ver como a FUVEST publicou

Publicada pela banca.

Resolução comentada

a) Cada elemento de A pode ser levado a qualquer um dos 4 elementos de A, e as escolhas são independentes. Pelo princípio multiplicativo:

4\cdot 4\cdot 4\cdot 4 = 4^4 = 256

Existem 256 funções.

b) A condição f(f(n))=n para todo n mostra que f é bijetora, pois ela é inversa de si mesma (f=f^{-1}). Então cada elemento ou é ponto fixo, ou forma um par \{a,b\} com f(a)=b e f(b)=a. Basta contar quantos pares (trocas) a função tem:

0 pares (identidade): 1 função.
1 par: escolhemos 2 elementos, \binom{6}{2}=15. Os outros 4 ficam fixos.
2 pares: \dfrac{\binom{6}{2}\binom{4}{2}}{2}=\dfrac{15\cdot 6}{2}=45. Dividimos por 2 porque a ordem dos pares não importa.
3 pares: \dfrac{\binom{6}{2}\binom{4}{2}\binom{2}{2}}{3!}=\dfrac{15\cdot 6\cdot 1}{6}=15.

Somando: 1+15+45+15=76.

Existem 76 funções.

c) As funções bijetoras de B em B são as 6!=720 permutações. Vamos contar o complementar, as que não têm ponto fixo (permutações caóticas, ou desarranjos). Por inclusão-exclusão:

D_6 = 6!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\right)=720-720+360-120+30-6+1=265

Portanto, o número de bijeções com pelo menos um ponto fixo é 720-265=455. A probabilidade é

\frac{455}{720}=\frac{91}{144}\approx 0{,}63

Probabilidade =\dfrac{91}{144}.

Assuntos: análise combinatória, funções, probabilidade.

Reportar erro na resolução

Ver como caiu na prova

Questão M03 no caderno da 2ª fase da FUVEST 2023