5 votos

Pregunta de teoría de gráfico elemental

He encontrado nadie que clasificado hasta el momento había dado una prueba correcta. Lo cutre es que también no sé cómo encontrar una prueba simple . Así que me decidí a preguntar. La pregunta es:

Ocho estudiantes en una clase se les pide cómo muchos de los otros siete estudiantes saben. Un estudiante sabe todos los estudiantes. Pero sólo dos estudiantes el mismo número de estudiantes. Mostrar que estas dos estudiantes conocen entre sí.

5voto

user8269 Puntos 46

No sé si este es lo suficientemente simple, pero aquí va.

Todo el mundo sabe que entre cero y siete. Ya que alguien sabe de siete, nadie sabe a cero. Ya que sólo dos se conocen el mismo número, los grados de los vértices en la convivencia gráfico debe ser 1, 2, 3, 4, 5, 6, 7, con una repetición.

Ya que hay un 7 y un 6, no puede haber dos 1s. Así que hay un único 1.

Ya que hay un 1 y un 2, no puede haber dos 6s. Así que hay una sola 6.

Ya que hay un 7, un 6 y un 5, no puede haber dos 2s. Así que hay un solo 2.

Ya que no hay un solo 1 y solo un 2 y un 3, no puede haber dos 5s. Así que hay una sola 5.

Ya que hay un 7, un 6, un 5 y un 4, no puede haber dos 3s. Ahora hemos descartado todo, pero dos 4s.

El 7 conoce todo el mundo. El 6 sabe todo, pero el 1. El 5 lo sabe todo, pero la 1 y la 2. Cada 4 conoce a todos, pero el 1, 2 y 3. Así, el 4s saber el uno del otro.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X