Question

Sea $A = \{1, 2, 3, 4\},$ y sean $f$ y $g$ funciones elegidas al azar (no necesariamente distintas) de $A$ a $A.$ La probabilidad de que el rango de $f$ y el rango de $g$ sean disjuntos es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halla $m.$

Let $A = \{1, 2, 3, 4\},$ and let $f$ and $g$ be randomly chosen (not necessarily distinct) functions from $A$ to $A.$ The probability that the range of $f$ and the range of $g$ are disjoint is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m.$

Respuesta

Solución:

Condicionemos según el rango de $f.$ Si tiene $k$ elementos, entonces el rango de $g$ es disjunto de él exactamente cuando $g$ manda $A$ a los $4 - k$ elementos restantes, lo que ocurre para $(4-k)^4$ de las $4^4 = 256$ funciones $g.$

Cuenta las funciones $f$ por tamaño del rango: $4$ funciones constantes; $\binom{4}{2}(2^4 - 2) = 84$ con rango de tamaño $2;$ $\binom{4}{3} \cdot 36 = 144$ con rango de tamaño $3$ (hay $36$ sobreyecciones de cuatro elementos sobre tres); y $4! = 24$ biyecciones. El número de pares favorables es $\begin{aligned} &4 \cdot 3^4 + 84 \cdot 2^4 \\ &\quad {}+ 144 \cdot 1^4 + 24 \cdot 0^4 \\ &= 324 + 1344 + 144 = 1812. \end{aligned}$

La probabilidad es $\frac{1812}{4^8} = \frac{1812}{65536} = \frac{453}{16384},$ y como $16384$ es una potencia de $2$ mientras que $453 = 3 \cdot 151$ es impar, esto ya está en su forma irreducible. Por lo tanto $m = 453.$

Condition on the range of $f.$ If it has $k$ elements, then the range of $g$ is disjoint from it exactly when $g$ maps $A$ into the remaining $4 - k$ elements, which happens for $(4-k)^4$ of the $4^4 = 256$ functions $g.$

Count functions $f$ by range size: $4$ constant functions; $\binom{4}{2}(2^4 - 2) = 84$ with range size $2;$ $\binom{4}{3} \cdot 36 = 144$ with range size $3$ (there are $36$ surjections from four elements onto three); and $4! = 24$ bijections. The number of favorable pairs is $\begin{aligned} &4 \cdot 3^4 + 84 \cdot 2^4 \\ &\quad {}+ 144 \cdot 1^4 + 24 \cdot 0^4 \\ &= 324 + 1344 + 144 = 1812. \end{aligned}$

The probability is $\frac{1812}{4^8} = \frac{1812}{65536} = \frac{453}{16384},$ and since $16384$ is a power of $2$ while $453 = 3 \cdot 151$ is odd, this is in lowest terms. Thus $m = 453.$

2014 AIME I Problema 12

Solución:

El Problema 12 en otros años