podríamos decir a modo de chiste que si es una exposa refinada y con educación ha saludado a todos por respeto. Pero creo que eso está bastante lejos de formar parte de alguna teoría de grafos, en fin…seguiré pensando ;)

En realidad, ahora que releo, no es logica mi respuesta y ademas es equivocada :D La respuesta es: saludo a 4 personas.

Dije que a lo sumo alguien saludo a 8 personas, sacando a su pareja y a si mismo (eran 10 personas totales). Pero, asumiendo que la esposa del anfitrión es la que no saludo a nadie, entonces esta persona no pudo haber saludado a mas de 7 (quitariamos ademas a la esposa del anfitrion!).

Por lo tanto, la persona que no saludo a nadie, es pareja de la persona que dijo haber saludado a todas personas (los 8 restantes).

Graficamente, las parejas y a quienes saludo:
AB , CD , EF , GH , (I=8,J=0)

Nos resta ir acomodando los numeros del 1-7. Voy a asumir que “A” es el anfitrion y a ese no debo asignarle ningún numero.

Uno de ellos (B,C,D,E,F,G o H) saludo a una persona, que inevitablemente es a I (porque saludo a todos los posibles).
- Asumamos que fue un invitado cualquiera: “H=1″
AB , CD , EF , (G,H=1) , (I=8,J=0)

Entonces, necesariamente G es el unico que pudo haber saludado a 7:
AB , CD , EF , (G=7,H=1) , (I=8,J=0)

Recursivamente tenemos:
AB , CD , (E=6,F=2) , (G=7,H=1) , (I=8,J=0)

AB , (C=5,D=3) , (E=6,F=2) , (G=7,H=1) , (I=8,J=0)

Y entonces, la esposa del anfitrion saludo a 4 personas (I, G, E y C).

Lo interesante, es demostrar ahora que no puede ser de otra manera :D

- Asumamos que la esposa del anfitrion saludo solo a 1:
(A,B=1) , CD , EF , GH , (I=8,J=0)

Entonces, nadie pudo haber saludado a 7 personas, porque B saludo a I necesariamente !

- Asumamos que la esposa (B) saludo a 2:
(A,B=2) , CD , EF , GH , (I=8,J=0)

Existe uno que saludo a 1:
(A,B=2) , (C=1,D) , EF , GH , (I=8,J=0)

Entonces, necesariamente, D saludo a 7:
(A,B=2) , (C=1,D=7) , EF , GH , (I=8,J=0)

Entonces, nadie pudo haber saludado a 6 personas!

- Asumamos que la esposa (B) saludo a 3:
(A,B=3) , CD , EF , GH , (I=8,J=0)

Existe uno que saludo a 1:
(A,B=3) , (C=1,D) , EF , GH , (I=8,J=0)

Entonces, necesariamente, D saludo a 7:
(A,B=3) , (C=1,D=7) , EF , GH , (I=8,J=0)

Existe uno que saludo a 2:
(A,B=3) , (C=1,D=7) , (E=2,F) , GH , (I=8,J=0)

Entonces, necesariamente, F saludo a 6:
(A,B=3) , (C=1,D=7) , (E=2,F=6) , GH , (I=8,J=0)

Entonces, nadie pudo haber saludado a 5 personas!

Como veran, es recursiva la cosa :D
El que haya saludado a 7 personas, necesariamente tuvo que ir acompañado de quien saludo a 1, y asi sucesivamente: (7,1),(6,2),(5,3) y como veran, el 4 queda solo, y justamente se le adjudica a la esposa del anfitrion que es al único a quien no teníamos que asignarle un valor. Quizás si empezaba con esto, quedaba mas claro… :D

Besos!

Ah, negra, una aclaración:

Tu buen uso de las palabras \”necesariamente\” e \”inevitablemente\” denotan claramente que, una vez arribada a la conclusión (esto es, que la esposa saludó a cuatro personas) no es necesario que demuestres que no podría haber sido de otra manera.

Aun que llega tarde, aca envio una respuesta grafica al problema que practicamente se dibuja sola, y da la solucion.

Aunque lamentablmenete debo admitir que de primera cai en la misma que Negra, ya que pense que la esposa era la que no conocia a nadie.

AB CD EF GH IJ
C AA AA AA AA
D E CC CC CC
E F G EE EE
F G H I GG
G H I J
H I J
I J
J
80 71 62 53 44

Por ultimo como se ve al final hay dos que responden 4 y solo pueden ser el anfitrion y su esposa.

Saludos