$$\textrm{Cuantas funciones inyectivas $f:\{1,2,3,...,50\}\longrightarrow \{1,2,3,...,80\}$ hay que satisfagan simultaneamente las condiciones:}$$
$$\textrm{$f(1)$ es par}$$
$$\textrm{$f(2)=4$}$$
$$\textrm{$f(3)\leq6$}$$
Firma
Tema
[No Resuelto](17/10/05) Tema 1 - Ej 2
A falta de Marcelo, tengo q aparecer yo alguna vez no? =)
Primero, veamos que es contar funciones inyectivas. tenemos \(f : \lbrace 1,2,3,...,50 \rbrace \rightarrow \lbrace 1,2,3,...,80 \rbrace\). Imaginen que no hay condiciones. Entonces si agarro por ejemplo f(1), puede ir a parar a 80 lugares distintos, pero cuando agarre f(2) tengo 79 posibilidades y asi... entonces la cantidad de funciones inyectivas va a ser \(80 * 79 * 78 .... * 30\)
Muy bien, empecemos a ver las condiciones..
\(f(2) = 4\) quiere decir que solo tengo una posibilidad de asignar el f(2) en vez de 80.. \(1 * 79 * 78 .... * 30\)
\(f(1) \; es \; par\) Bueno, supongamos que ya elegi primero a f(2) = 4, entonces me quedan de las 79 posibilidades, 39 que son pares: \(1 * 39 * 78 .... * 30\)
\(f(3) \leq 6\) Esta es la q arma quilombo. F(3) puede ser 1,2,3,5,6. Pero el problema esta si f(1) es 2 o 6, entonces lo que voy a hacer es separar los casos y los trato como conjuntos disjuntos y los sumo.
Caso 1: f(1) ni 2 ni 6. Entonces hay 5 posibilidades para f(3) y quedaria \(1 * 39 * 5 * 77 .... * 30\)
Caso 2 y 3: f(1) es o 2 o 6. Quedaria 4 posibilidades para f(3) y tengo el f(1) fijado entonces : \(1 * 1 * 4 * 77 .... * 30\) <-- dos veces eso
Vamos a escribirlo mas lindo:
Caso 1: \(39 * 5 * \frac{77!}{30!}\)
Caso 2 y 3: \(2\; *\; (4 * \frac{77!}{30!})\)
Y la respuesta es : \(39 * 5 * \frac{77!}{30!}+2\; *\; (4 * \frac{77!}{30!})\)
Espero que les haya gustado! (o entendido en su defecto..)
Hola,
En el caso 1, cuadno decis q f(1) no es ni 2 ni 6 ahi no sería por 39 sino por 37 ya que no estarias contando esos dos lugares.
Es correcto lo que digo?
Me parece que esto va en Ejercicios de Combinatoria, no en Ejercicios de Conjuntos.
Yo lo hice casi igual a Nico, pero me dio distinto. No sé si está bien.
Como Nico, empiezo por el caso más fácil y le voy agregando las condiciones:
$$f \text{ es una funci\'on } \Leftrightarrow \forall \; x \in Dom(f) \; \exists! \; y \in Codom(f) / f(x) = y$$
$$f \text{ es inyectiva } \Leftrightarrow \forall \; y \in Im(f) \; \exists! \; x \in Dom(f) / f(x) = y$$
Entonces a cada elemento del dominio debo asignarle un elemento distinto del codominio:
$$\text{para} \: f(1) \; \: \text{ tenemos } 80 \text{ posibilidades}$$
$$\text{para} \: f(2) \; \: \text{ tenemos } 79 \text{ posibilidades} \Rightarrow 80 \cdot 79 \text{ posibilidades en total}$$
$$\text{para} \: f(3) \; \: \text{ tenemos } 78 \text{ posibilidades} \Rightarrow 80 \cdot 79 \cdot 78 \text{ posibilidades en total}$$
$$\color{white} \text{.} \color{black} \qquad \quad \vdots \qquad \qquad \quad \; \; \vdots$$
$$\text{para} \, f(50) \text{ tenemos } 31 \text{ posibilidades} \Rightarrow 80 \cdot 79 \cdot 78 \cdot (\, \cdots) \cdot 31 = \frac{80!}{(80-50)!} = \frac{80!}{30!} = ( \prod\limits_{i=31}^{80} i ) \text{ posibilidades en total}$$
Ahora le sumamos la condición de que \(f(1)\) debe ser par:
$$\text{para} \: f(1) \; \: \text{ tenemos } \frac{80}{2}=40 \text{ posibilidades (solo puede tomar valores pares)}$$
$$\text{para} \: f(2) \; \: \text{ tenemos } 79 \text{ posibilidades} \Rightarrow 40 \cdot 79 \text{ posibilidades en total}$$
$$\text{para} \: f(3) \; \: \text{ tenemos } 78 \text{ posibilidades} \Rightarrow 40 \cdot 79 \cdot 78 \text{ posibilidades en total}$$
$$\color{white} \text{.} \color{black} \qquad \quad \vdots \qquad \qquad \quad \; \; \vdots$$
$$\text{para} \, f(50) \text{ tenemos } 31 \text{ posibilidades} \Rightarrow 40 \cdot 79 \cdot 78 \cdot (\, \cdots) \cdot 31 = \frac{80}{2} \cdot \frac{(80-1)!}{(80-50)!} = \frac{80 \cdot (79)!}{2 \cdot (30)!} = \frac{80!}{30! \cdot 2} = \frac{ ( \prod\limits_{i=31}^{80} i ) }{2} \text{ posibilidades en total}$$
Ahora le sumamos la condición de que \(f(2) = 4\) :
$$\text{para } \: f(1) \; \: \text{ tenemos } \frac{80}{2} - 1 = 39 \text{ posibilidades (solo puede tomar valores pares y } f(2) = 4 \text{)}$$
$$\text{para} \: f(2) \; \: \text{ tenemos } 1 \text{ posibilidad} \Rightarrow 39 \cdot 1 \text{ posibilidades en total}$$
$$\text{para} \: f(3) \; \: \text{ tenemos } 78 \text{ posibilidades} \Rightarrow 39 \cdot 1 \cdot 78 \text{ posibilidades en total}$$
$$\text{para} \: f(4) \; \: \text{ tenemos } 77 \text{ posibilidades} \Rightarrow 39 \cdot 1 \cdot 78 \cdot 77 \text{ posibilidades en total}$$
$$\color{white} \text{.} \color{black} \qquad \quad \vdots \qquad \qquad \quad \; \; \vdots$$
$$\text{para} \, f(50) \text{ tenemos } 31 \text{ posibilidades} \Rightarrow 39 \cdot 1 \cdot 78 \cdot 77 \cdot (\, \cdots) \cdot 31 = (\frac{80}{2} - 1) \cdot \frac{(80-1-1)!}{(80-50)!} = 39 \cdot \frac{78!}{30!} = 39 \cdot ( \prod\limits_{i=31}^{78} i ) \text{ posibilidades en total}$$
Y ahora le sumamos la última condición: \(f(3) \leq 6\)
$$f(3) \leq 6 \Rightarrow f(3) = \{ 1, 2, 3, 4, 5, 6 \}$$
pero \(f(2) = 4 \; \wedge \; f(1) \text{ es par } \Rightarrow f(3) = \{ 1, \color{red}2\color{black}, 3, \not{4}, 5, \color{red}6\color{black} \}\)
$$\text{( N\'otese que tanto } f(1) \text{ como } f(3) \text{ pueden tomar los valores en rojo y que } f(3) \neq 4 \text{ porque una de las condiciones ya es } f(2) = 4 \text{ )}$$
entonces separo en casos disjuntos:
a) \(f(1) \text{ es par } \wedge f(1) \color{red}>\color{black} 6 \Rightarrow f(3) = \{1, 2, 3, \not{4}, 5, 6\}\)
b) \(f(1) \text{ es par } \wedge f(1) = \color{red}6\color{black} \Rightarrow f(3) = \{1, 2, 3, \not{4}, 5, \not{6}\}\)
c) \(f(1) \text{ es par } \wedge f(1) = \color{red}2\color{black} \Rightarrow f(3) = \{1, \not{2}, 3, \not{4}, 5, 6\}\)
y luego los sumo.
Caso a)
$$f(1) \text{ es par } \wedge f(1) \color{red}>\color{black} 6 \Rightarrow f(3) = \{1, 2, 3, \not{4}, 5, 6\}$$
$$\text{para } \: f(1) \; \: \text{ tenemos } \frac{80}{2} - 1 = 39 \text{ posibilidades (solo puede tomar valores pares y } f(2) = 4 \text{ ) }$$
$$\text{para} \: f(2) \; \: \text{ tenemos } 1 \text{ posibilidad} \Rightarrow 39 \cdot 1 \text{ posibilidades en total}$$
$$\text{para} \: f(3) \; \: \text{ tenemos } 5 \text{ posibilidades} \Rightarrow 39 \cdot 1 \cdot 5 \text{ posibilidades en total}$$
$$\text{para} \: f(4) \; \: \text{ tenemos } 77 \text{ posibilidades} \Rightarrow 39 \cdot 1 \cdot 5 \cdot 77 \text{ posibilidades en total}$$
$$\text{para} \: f(5) \; \: \text{ tenemos } 76 \text{ posibilidades} \Rightarrow 39 \cdot 1 \cdot 5 \cdot 77 \cdot 76 \text{ posibilidades en total}$$
$$\color{white} \text{.} \color{black} \qquad \quad \vdots \qquad \qquad \quad \; \; \vdots$$
$$\text{para} \, f(50) \text{ tenemos } 31 \text{ posibilidades} \Rightarrow 39 \cdot 1 \cdot 5 \cdot 77 \cdot 76 \cdot (\, \cdots) \cdot 31 = (40 - 1) \cdot 1 \cdot 5 \cdot \frac{(80-3)!}{(80-50)!} = 39 \cdot 5 \cdot \frac{77!}{30!} = 39 \cdot 5 \cdot ( \prod\limits_{i=31}^{77} i ) \text{ posibilidades en total}$$
Caso b)
$$f(1) \text{ es par } \wedge f(1) = \color{red}6\color{black} \Rightarrow f(3) = \{1, 2, 3, \not{4}, 5, \not{6}\}$$
$$\text{para } \: f(1) \; \: \text{ tenemos } \frac{80}{2} - 1 -1 = 38 \text{ posibilidades (solo puede tomar valores pares, } f(2) = 4 \text{ y } f(1) = 6 \text{ ) }$$
$$\text{para} \: f(2) \; \: \text{ tenemos } 1 \text{ posibilidad} \Rightarrow 38 \cdot 1 \text{ posibilidades en total}$$
$$\text{para} \: f(3) \; \: \text{ tenemos } 4 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \text{ posibilidades en total}$$
$$\text{para} \: f(4) \; \: \text{ tenemos } 77 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \cdot 77 \text{ posibilidades en total}$$
$$\text{para} \: f(5) \; \: \text{ tenemos } 76 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \cdot 77 \cdot 76 \text{ posibilidades en total}$$
$$\color{white} \text{.} \color{black} \qquad \quad \vdots \qquad \qquad \quad \; \; \vdots$$
$$\text{para} \, f(50) \text{ tenemos } 31 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \cdot 77 \cdot 76 \cdot (\, \cdots) \cdot 31 = (40 - 1 - 1) \cdot 1 \cdot 4 \cdot \frac{(80-3)!}{(80-50)!} = 38 \cdot 4 \cdot \frac{77!}{30!} = 38 \cdot 4 \cdot ( \prod\limits_{i=31}^{77} i ) \text{ posibilidades en total}$$
Caso c)
$$f(1) \text{ es par } \wedge f(1) = \color{red}2\color{black} \Rightarrow f(3) = \{1, \not{2}, 3, \not{4}, 5, 6\}$$
$$\text{para } \: f(1) \; \: \text{ tenemos } \frac{80}{2} - 1 -1 = 38 \text{ posibilidades (solo puede tomar valores pares, } f(2) = 4 \text{ y } f(1) = 2 \text{ ) }$$
$$\text{para} \: f(2) \; \: \text{ tenemos } 1 \text{ posibilidad} \Rightarrow 38 \cdot 1 \text{ posibilidades en total}$$
$$\text{para} \: f(3) \; \: \text{ tenemos } 4 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \text{ posibilidades en total}$$
$$\text{para} \: f(4) \; \: \text{ tenemos } 77 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \cdot 77 \text{ posibilidades en total}$$
$$\text{para} \: f(5) \; \: \text{ tenemos } 76 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \cdot 77 \cdot 76 \text{ posibilidades en total}$$
$$\color{white} \text{.} \color{black} \qquad \quad \vdots \qquad \qquad \quad \; \; \vdots$$
$$\text{para} \, f(50) \text{ tenemos } 31 \text{ posibilidades} \Rightarrow 38 \cdot 1 \cdot 4 \cdot 77 \cdot 76 \cdot (\, \cdots) \cdot 31 = (40 - 1 - 1) \cdot 1 \cdot 4 \cdot \frac{(80-3)!}{(80-50)!} = 38 \cdot 4 \cdot \frac{77!}{30!} = 38 \cdot 4 \cdot ( \prod\limits_{i=31}^{77} i ) \text{ posibilidades en total}$$
Nótese que el caso c) me dió lo mismo que el caso b), cosa que si uno se daba cuenta antes (como Nico) podía hacer la cuenta una sola vez y multiplicar el resultado por 2.
Sumo los casos disjuntos para obtener el resultado final:
$$\text{ a) } + \text{ b) } + \text{ c) } = \text{ a) } + \, 2 \cdot \text{ b) } } = 39 \cdot 5 \cdot \frac{77!}{30!} \, + \, 2 \cdot ( 38 \cdot 4 \cdot \frac{77!}{30!} ) = \frac{77!}{30!} ( 3 \cdot 5 \cdot 13 \, + \, 2^4 \cdot 19 ) = \frac{499 \cdot 77!}{30!} = 499 ( \prod\limits_{31}^{77} i )$$
$$\, \therefore \; \text{Hay } 499 ( \prod\limits_{31}^{77} i ) \text{ funciones inyectivas } f:\{1, 2, 3, (\ldots), 50\} \rightarrow \{1, 2, 3, (\ldots), 80\} \text{ que satisfacen simultaneamente } f(1) \text{ es par } \wedge \; f(2) = 4 \; \wedge \; f(3) \leq 6 \text{ . }$$
$$499 ( \prod\limits_{31}^{77} i ) \approx 2,7312 \cdot 10^\color{red}83\color{black}$$
La verdad no sé si tiene sentido el resultado, es un número MUY grande...
Espero que esté bien. Estuve horas con el \(\LaTeX\) jaja
Si ven algún error, avisen.
Firma
Vicente Luy escribió:
Si me equivoco contradíganme con amor, porque con amor digo.
Si erro póngame maestros, que luego yo les enseño, porque con amor hago.
Editado 2 veces.
Nico creo que en una parte donde te contradecís, si no es ni 2 ni 6, entonces quedan 3 chances, no 5.
Fijate, o quizás estoy pensando mal.
A mi me dio \(3 \times 1 \times 39 \times \binom{80}{47} + 2 \times 1 \times 38 \times \binom{80}{47}\)
Firma
Powered by GTX 660ti
Tenés razón en la corrección a Nico? pero me parece que tu resultado está mal: cuando multiplicas por el número combinatorio en realidad deberías multiplicar por \(77\times 76 \times \cdots \times 31\).
Ahh, te recuerdo que es obligatorio escribir las expresiones matemáticas en \(\LaTeX\). Si no sabés usarlo hay un instructivo en la sección de reglas del foro.
Firma
Quimey