| Autor |
Mensaje |
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
   |
     |
|
4WD
Administrador
Edad: 39
Registrado: 07 Sep 2006
Mensajes: 2430
Ubicación: Ingeniero
Carrera: Mecánica
|
|
Para el caso inicial, existe una mujer al lado de un hombre (la primera es mujer y el segundo [y último], al lado del primero es hombre.
Al incrementar la cantidad de personas, pensás en que en realidad la nueva persona la estás poniendo en el medio. Así, existen 3 casos. 1) Hay un par mujer/hombre a la izq; 2) hay a la derecha; 3) y este es el que prueba, suponete que tenés la mala suerte que no hay pares ni a derecha ni a izquierda ("las nenas con las nenas, los nenes con los nenes"  ), la nueva persona va a ser mujer con lo cual queda al lado del grupo de hombre y tiene un hombre al lado, o es hombre y queda al lado del grupo de mujeres y tiene mujer al lado.
Fijate cómo escribirlo. (La idea para usar la hipótesis inductiva sería considerar que existe una pareja en la hilera de personas y vos efectuas un corte en un lugar intermedio para poner una nueva persona: así o el par estaba a la derecha, o a la izquierda o justo cortaste al par y estás en el 3º caso)
|
|
|
|
_________________
 
 
 
|
|
  |
 |
|
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
| 4WD escribió:
|
Para el caso inicial, existe una mujer al lado de un hombre (la primera es mujer y el segundo [y último], al lado del primero es hombre.
Al incrementar la cantidad de personas, pensás en que en realidad la nueva persona la estás poniendo en el medio. Así, existen 3 casos. 1) Hay un par mujer/hombre a la izq; 2) hay a la derecha; 3) y este es el que prueba, suponete que tenés la mala suerte que no hay pares ni a derecha ni a izquierda ("las nenas con las nenas, los nenes con los nenes" ), la nueva persona va a ser mujer con lo cual queda al lado del grupo de hombre y tiene un hombre al lado, o es hombre y queda al lado del grupo de mujeres y tiene mujer al lado.
Fijate cómo escribirlo. (La idea para usar la hipótesis inductiva sería considerar que existe una pareja en la hilera de personas y vos efectuas un corte en un lugar intermedio para poner una nueva persona: así o el par estaba a la derecha, o a la izquierda o justo cortaste al par y estás en el 3º caso)
|
Gracias, algo asi se me habia ocurrido, voy a ver si llego a lago "lindo" y lo subo al wiki (previo cerciorarme de que este bien )
|
|
|
|
_________________
arielik
[CAMPAÑA] Colaboremos entre todos por un foro más ordenado (click aquí)
[CAMPAÑA] Hacer un tópico por cada curso y con información ¡útil! (click aquí)
|
|
| |
|
|
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
| |
|
|
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
| |
|
|
4WD
Administrador
Edad: 39
Registrado: 07 Sep 2006
Mensajes: 2430
Ubicación: Ingeniero
Carrera: Mecánica
|
|
| arielik escribió:
|
Bueno, se me ocurrio algo...
Si digo que en el caso base tengo solo dos personas a0 y a1, a0= mujer y a1= varón -> se cumplela tesis de que hay un varon y una mujer consecutivos.
Ahora, el paso inductivo, digo que a0 = mujer , ai (con 0 < i <n> a0 y a1 cumplen la tesis ya que a0 = mujer y a1 = ai con i=1 = varon.
Ahora, si los ai son todos mujeres -> ai (con i = n-1) y an cumplen con la tesis.
El ultimo caso es que ai este conformado por varones y mujeres en tal caso va a existir un ai y un ak (con k distinto de i) que cumpla la tesis.
Esto esta probado asi?
Me parece medio chota la demostración
Help!!!
Saludos,
|
El parser del foro te hizo pelota lo que escribiste entre signos de mayor y menor.
Usá [tex]\LaTeX[/tex], no seas foro!
|
|
|
|
_________________
|
|
| |
|
|
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
| |
|
|
4WD
Administrador
Edad: 39
Registrado: 07 Sep 2006
Mensajes: 2430
Ubicación: Ingeniero
Carrera: Mecánica
|
|
No me gusta mucho...
La pienso en el bondi y te cuento mañana
|
|
|
|
_________________
|
|
| |
|
|
AndresDj
Nivel 4
Registrado: 27 Oct 2005
Mensajes: 77
|
|
Ariel, ahí no estás aplicando inducción. Cuando decís "en tal caso va a existir un ... que cumpla la tesis" como que estás volviendo a enunciar lo que te piden demostrar.
Para armar una demostración por inducción, la clave es que pienses alguna manera de ir "aumentando de a uno" la solución, de forma tal que, si antes de aumentar se cumplía la condición, entonces también se cumple después de aumentar. El paso inductivo es eso.
Ponele que tu fila original es:
![[tex]\{a_0,a_1,...,a_{n-1}\}[/tex]](images/latex/18e07fa1be16ed0863d4333c72c00021fcf64421_0.png "[tex]\{a_0,a_1,...,a_{n-1}\}[/tex]")
Armemos, para poder preparar la demostración, la siguientes filas imaginarias:
![[tex]S_i=\{a_0,...,a_i,a_{n-1}\}[/tex]](images/latex/1ea65403a9e88732f7bcb8a37b96b7106303930f_0.png "[tex]S_i=\{a_0,...,a_i,a_{n-1}\}[/tex]")
Serían las filas de los primeros i-1 con el último tipo al final (bah, capaz que se puede escribir mejor eso, porque si i=0 entonces a_0 y a_i son uno solo, propongan algo). El paso inductivo va a ser demostrar que, si la condición se cumple para S_i, entonces se cumple para S_{i+1}. Es decir, hay que demostrar que:
![[tex]P(S_i) \Rightarrow P(S_{i+1})[/tex]](images/latex/17fbfdb21bf9f63d75e234c619cf3830898da3d2_0.png "[tex]P(S_i) \Rightarrow P(S_{i+1})[/tex]")
Formalicemos ![[tex]P(S_i)[/tex]](images/latex/5fae38c08d1f5ba18788f68e251b5486013720ea_0.png "[tex]P(S_i)[/tex]") :
![[tex]P(S_i) \equiv (\exists j / 0 \leq j < i \land a_j \in M \land a_{j+1} \in H) \lor a_i \in M[/tex]](images/latex/3e439fe132a62c34f886a46db27de4de8e75665e_0.png "[tex]P(S_i) \equiv (\exists j / 0 \leq j < i \land a_j \in M \land a_{j+1} \in H) \lor a_i \in M[/tex]")
Eso es lo mismo que decir que hay un hombre atrás de una mujer en alguna parte de la fila. M y H son los conjuntos de mujeres y hombres, claro. Acordate de que la fila termina con un ![[tex]a_{n-1} \in H[/tex]](images/latex/162b7ff6187241bdd2288b4c31cee29e476c4794_0.png "[tex]a_{n-1} \in H[/tex]") .
Por lo tanto:
![[tex]P(S_{i+1}) \equiv (\exists j / 0 \leq j < i+1 \land a_j \in M \land a_{j+1} \in H) \lor a_{i+1} \in M[/tex]](images/latex/b2b60e6eda865645d94903333814abd29b2a4ebe_0.png "[tex]P(S_{i+1}) \equiv (\exists j / 0 \leq j < i+1 \land a_j \in M \land a_{j+1} \in H) \lor a_{i+1} \in M[/tex]")
Fijate que son dos cláusulas. Para demostrar ![[tex]P(S_{i+1})[/tex]](images/latex/9cef8a8bea4ae282ed8a0457f2c0183b9fc533fc_0.png "[tex]P(S_{i+1})[/tex]") , hay que demostrar que alguna de sus dos cláusulas es verdadera. Si ![[tex]a_{i+1} \in M[/tex]](images/latex/5f9722396b0a87dcd40d83bdbbe160aa0963af88_0.png "[tex]a_{i+1} \in M[/tex]") (en otras palabras, si la nueva persona en la fila es una mujer) se cumple la segunda. Hay que ver qué pasa si el nuevo es un hombre.
Acordate de que partimos de que es verdadero. Por lo tanto, al menos una de sus dos cláusulas se cumple. Si se cumple la primera, entonces también se va a cumplir la primera de , porque existe j de 0 a i que cumple aquello escrito después. Si la primera no se cumple, entonces ![[tex]a_i \in M[/tex]](images/latex/a56a1dfb9da951ea2fc218bd084cf2d548e507fd_0.png "[tex]a_i \in M[/tex]") . En tal caso, la primera cláusula de se va a cumplir en j=i.
Ergo, si entonces .
Falta mostrar que ![[tex]P(S_0)[/tex]](images/latex/79e32bef5fc41a0aff60f4ccbf01fac21d21c696_0.png "[tex]P(S_0)[/tex]") es verdadero. Esa es la fila de la primera mujer con el último hombre, nada más. Como se ve, cumple la condición.
Ah, un paso que me comía, es decir que ![[tex]P(S_{n-1})[/tex]](images/latex/d7d24e76d4a5c37b7c4de56753ece753deb92d1d_0.png "[tex]P(S_{n-1})[/tex]") es la fila original. Nos pedían demostrar para esa. Demostrando que se cumple para todas las S, demostramos que se cumple para la fila original.
Bue, le tengo confianza a la demostración pero me asombra que haya quedado larga, si encuentran una manera de expresarla más brevemente, u otra demostración más simple, avisen, me cansé  .
Saludos!
|
|
|
|
|
|
| |
|
|
Jorge Pérez
Nivel 6
Registrado: 02 May 2006
Mensajes: 210
|
|
Una posible demostración es ésta:
Llamamos ![[tex] P_n[/tex]](images/latex/fa96c999e3dee169f6d8151888360db334df9f8e_0.png "[tex] P_n[/tex]") a la proposición:
![[tex] Pn:[/tex]](images/latex/9306d0d94fda68f30fcef012be3bfa9427f76851_0.png "[tex] Pn:[/tex]") En toda fila con n individuos que comienza con una mujer y
termina con un varón, hay en algún lugar de la fila una mujer y un varón consecutivos.
Probamos que es cierta para ![[tex] n \ge 2 [/tex]](images/latex/f84c7ee5fad1de72d0877190b9301e277aa5830a_0.png "[tex] n \ge 2 [/tex]") .
Caso ![[tex] n=2 [/tex]](images/latex/4b20d40ce7ca7d89e90209535bf2c8445490c5c2_0.png "[tex] n=2 [/tex]") .
Obvio, porque hay sólo dos personas en la fila, y una es mujer y la otra es varón.
Paso Inductivo.
Suponemos que ![[tex] Pn[/tex]](images/latex/6742220df5ef2ebdd62370f9e6e12b02be893893_0.png "[tex] Pn[/tex]") es verdadera para cierto y probamos que ![[tex] P_{n+1}[/tex]](images/latex/e175396a0ff846756083c809c35e4b88a24c0c10_0.png "[tex] P_{n+1}[/tex]") es verdadera.
Supongamos entonces que tenemos una fila con ![[tex] n+1 [/tex]](images/latex/24a05886a888373e4c5f76adf618783e4ecd11aa_0.png "[tex] n+1 [/tex]") individuos, donde el primero es mujer y el último varón. Hay dos casos
1) El ante último es mujer. Entonces en la fila hay un hombre y una mujer consecutivos.
2) El ante último es varón. Entonces en ese caso, necesariamente ![[tex]n \ge 2 [/tex]](images/latex/f60c9f81b3160a9330c249724aa6f83cd4278146_0.png "[tex]n \ge 2 [/tex]") .
Consideremos la fila de compuesta por los primeros ![[tex] n [/tex]](images/latex/ba32499a92979830d7506acd015fdd74e520f8d2_0.png "[tex] n [/tex]") individuos. Esta fila comienza con una mujer y termina con un varón. Entonces, por la hipótesis inductiva, debe haber, en algún lugar de la fila un hombre y una mujer consecutivos.
Con esto queda probado que ![[tex]P_{n+1}[/tex]](images/latex/247e05c50611bfd207f9f07eabe28b8a59f94328_0.png "[tex]P_{n+1}[/tex]") es verdadera.
|
|
|
|
|
|
| |
|
|
AndresDj
Nivel 4
Registrado: 27 Oct 2005
Mensajes: 77
|
|
| Bien Jorge, me gustó tu demostración y es mucho más corta.
|
|
|
|
|
|
| |
|
|
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
| |
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
![[tex]a_{0} = mujer[/tex]](images/latex/2b2a568099e3b842d3ae9bcc4afd3c82a1b40cf6_0.png "[tex]a_{0} = mujer[/tex]")
, ![[tex]a_{i} (con\ 0 \le i \le n )[/tex]](images/latex/fc75ada00781742f8555c6a242199d43f1719166_0.png "[tex]a_{i} (con\ 0 \le i \le n )[/tex]")
todos varones ![[tex]a_{0} \ y\ a_{1}[/tex]](images/latex/45e0729c31e5a9a92e025ea0c1669a6dd5558543_0.png "[tex]a_{0} \ y\ a_{1}[/tex]")
cumplen la tesis ya que ![[tex]a_{0} =\ mujer\ y\ a_{1} = varon[/tex]](images/latex/9c67ec30355de9e9fb6b864b6ca8875c88312301_0.png "[tex]a_{0} =\ mujer\ y\ a_{1} = varon[/tex]")
![[tex]a_{i}[/tex]](images/latex/c1125b82e945d266389477bf787e139f0b7606b0_0.png "[tex]a_{i}[/tex]")
son todos mujeres ![[tex]\rightarrow a_{i}\ (con\ i = n-1)\ y\ a_{n}[/tex]](images/latex/3b36ec4b3cb809aaa1f4ce71023334e8448c246c_0.png "[tex]\rightarrow a_{i}\ (con\ i = n-1)\ y\ a_{n}[/tex]")
cumplen con la tesis.
![[tex]a_{i}\ y\ un\ a_{k}\ (con\ k \neq i)[/tex]](images/latex/048b7d65431d11342ea9cdb6f4a1a675cda4bf93_0.png "[tex]a_{i}\ y\ un\ a_{k}\ (con\ k \neq i)[/tex]")
que cumpla la tesis.
)), además arregle un poco la página