Autor Tema: Problema de grafos

0 Usuarios y 1 Visitante están viendo este tema.

04 Febrero, 2007, 04:43 pm
Leído 2510 veces

chosko

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 25
  • Karma: +0/-0
  • Sexo: Masculino
Buenas, no sé muy bien en que subforo ubicar este mensaje de forma que si es preciso moverlo hagan lo oportuno, jeje.
Bueno, al tema, ahí va el problema:

Cerebelo y su mujer, Florienda celebran una fiesta con cuatro parejas más. Los invitados hablan animadamente entre ellos, pero los miembros de cada pareja no se hablan entre sí. Cerebelo es muy celoso, y quiere saber con cuántos hombres a hablado su mujer. Haciéndose el tonto, le pregunta a Florinda (que se fija en todos los detalles) con cuántas personas ha hablado cada uno de los invitados, incluyéndola a ella y excluyéndose a sí mismo.
Florinda no quiere darle una respuesta directa, y le dice: "No hay dos personas que hayan hablado con el mismo número de gente". Cerebelo hace un cálculo mediante un grafo, se tranquiliza y responde: "Así me gusta, vamos para casa". Florinda asiente y comenta: "Aunque no me he preocupado de controlarte, sé que has hablando sólo con mujeres, y además con todas".

¿Qué calculó Cerebelo? ¿Cómo supo Florinda con quién habló Cerebelo, sin necesidad de controlarle?

PISTA: Piensa en un grafo con 10 vértices, uno por persona. Averigüa con cuantas personas tiene que haber hablado Florinda, y a partir de ahí deduce el resto de respuestas.


Mi conclusión: Ni pajolera idea de por dónde meterle mano. Alguna ayudilla la agradecería, gracias de antemano.

Saludos.

05 Febrero, 2007, 05:33 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 No se si entiendo bien el enunciado porque hay algo que me desoncierta. Dice:

Citar
...le pregunta a Florinda (que se fija en todos los detalles) con cuántas personas ha hablado cada uno de los invitados, incluyéndola a ella y excluyéndose a sí mismo.
Florinda no quiere darle una respuesta directa, y le dice: "No hay dos personas que hayan hablado con el mismo número de gente"...


El se excluye pero ella supongo que si considera que la gente que habló con Cerebelo habló con alguien.

En cualquier caso, cada persona puede hablar con un máximo de 8 invitados (excluyéndose a si mismo y a su pareja). Entonces, segun lo que dice Florinda, los 9 invitados excluido a Cerebelo han hablado con 8,7,6,5,4,3,2,1,0 invitados. Pero esto es imposible: el que habló con 8 habló con todos... también con el que NO HABLO CON NADIE!!!

¿Es así o estoy errado?

Saludos.


05 Febrero, 2007, 06:06 pm
Respuesta #2

germanzorba

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 189
  • Karma: +0/-0
  • Sexo: Masculino
Siguiendo con el análisis del manco. Sí puede ser que una persona haya hablado con 8 y otra con 0. Como obviamente no hablaron entre ellas, tienen que ser pareja. A falta de mejores nombres los llamaremos ocho y cero respectivamente.

La persona que habló con 7, habló con todos los que pudo salvo con cero. La persona que habló solo con 1, solamente habló con ocho. Para que esto sea posible, estos dos deben ser pareja. Los llamaremos siete y uno.

El razonamiento se puede continuar hasta llegar a deducir que Florinda habló con cuatro personas.

Lo que sigue es anotar quién habló con quién (puede ser sobre un grafo de diez vértices, pero podría ser de otro modo). Para que las cantidades de personas con las que cada uno habló sean las correctas, hay una única forma en la que pueden hacerse los cruces. Mirando las relaciones resultantes resulta evidente que Cerebelo puede deducir con quiénes hablo Florinda sabiendo con quiénes habló él.

Spoiler
ocho -> uno, dos, tres, cuatro, cinco, seis, siete, Cerebelo
cero ->
(estos dos tienen que ser pareja)

siete -> ocho, dos, tres, cuatro, cinco, seis, Cerebelo
uno -> ocho
(estos dos tienen que ser pareja)

seis -> siete, ocho, tres, cuatro, cinco, Cerebelo
dos -> siete, ocho
(estos dos tienen que ser pareja)

cinco -> seis, siete, ocho, cuatro, Cerebelo
tres -> seis, siete, ocho
(estos dos tienen que ser pareja)

cuatro -> cinco, seis, siete, ocho

Entonces no hay más alternativa que que cuatro sea Florinda. Además, revisando lo escrito, puede verse que Florinda y Cerebelo hablaron con exactamente las mismas personas.
[cerrar]

05 Febrero, 2007, 06:14 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Citar
Sí puede ser que una persona haya hablado con 8 y otra con 0. Como obviamente no hablaron entre ellas, tienen que ser pareja.


CLARO!!!!!!!!!!!!!!!!!!!!!!!! Ando tonto....  :-\

Muy buena germanzorba!!!

Saludos.