22 votos

Demuestra que en una fiesta con al menos dos personas, hay dos personas que conocen al mismo número de personas...

Bien, ahora, realmente quiero resolver esto por mi cuenta, y creo que tengo la idea básica, sólo que no estoy seguro de cómo ponerla como respuesta en la tarea. El problema en su totalidad:

"Demuestra que en una fiesta con al menos dos personas, que hay dos personas que conocen el mismo número de personas allí (no necesariamente el mismo número) dado que cada persona de la fiesta conoce al menos a una persona. conoce al menos a una persona. Además, hay que tener en cuenta que nadie puede ser su su propio amigo. Esto se puede resolver con un uso complicado del Principio de encasillamiento".

En primer lugar, estoy tratando el concepto de "conocer" como que A puede conocer a B, pero B no tiene por qué conocer a A. Por ejemplo, si Tom Cruise entra en una fiesta, yo le "conozco", pero él no me conoce a mí.

Así que lo que hice primero fue demostrármelo a mí mismo utilizando ejemplos de una fiesta con 2 personas, 3 personas, 4 personas, etc. Efectivamente, bajo cualquier condición, siempre hay al menos un par de personas que conocen al mismo número de personas.

Así que si definimos $n$ como el número de asistentes a la fiesta, entonces podemos ver que esto es cierto en cualquier circunstancia si suponemos que la primera persona conoce el máximo número de personas posible, que es $(n-1)$ (ya que una persona no puede ser amiga de sí misma). Entonces, como no nos interesa el caso de que la segunda persona conozca al mismo número de personas (si no, no hay nada que demostrar), queremos que la segunda persona conozca a una menos que la primera, o $(n-2)$ y así sucesivamente.

Finalmente llegamos a una contradicción donde la última persona sabe $(n-n)$ o 0. Como el 0 no es un valor posible según la definición del problema, esa última persona debe conocer cualquier número de personas de 1 a $(n-1)$ que equivale al número de personas que conoce al menos otra persona.

Ahora... espero que esta sea la "idea correcta". Pero, ¿cómo puedo convertir esta "comprensión general" en una respuesta para un problema que comienza con la palabra "demostrar"?

Permítanme señalar que sólo hemos tocado muy brevemente los conceptos de inducción y el principio de encasillamiento, y que no hemos dado ningún ejemplo de cómo "demostrar" formalmente algo con el principio de encasillamiento. Sí que hemos hablado de cómo demostrar la suma de números por inducción, pero eso es todo en lo que respecta a la inducción.

También: Pregunta de combinatoria: Demuestra que 2 personas en una fiesta conocen a la misma cantidad de gente no funciona realmente para mí, porque

A) no hemos hablado de "combinatoria", y

B) esa pregunta permite que alguien conozca a 0 personas.

13 votos

Si se descarta conocer a 0 personas, y se descarta conocerse a sí mismo, entonces con $n$ personas sólo hay $n-1$ número posible de personas que uno puede conocer: uno puede conocer a 1 persona, 2, otras personas, , o todas $n-1$ otras personas. Dado que hay $n$ personas y sólo $n-1$ diferentes números de personas que podrían conocer, dos de ellos deben conocer el mismo número de personas. Esta es exactamente la principio de encasillamiento .

0 votos

Si conoces a alguien, ¿te conocen necesariamente a ti?

0 votos

@MJD Exacto, eso es básicamente la versión corta de lo que escribí arriba. ¿Pero esta explicación equivale a una "prueba" como pide la pregunta? Si es así, ¡me parece bien! Es que me pareció que probablemente había una manera más formal de escribirlo :)

19voto

Christian Bueno Puntos 350

Dejemos que $n$ sea el número de asistentes a la fiesta. El número máximo de personas que una persona puede conocer es $n-1$ y el número mínimo que puede conocer es 1 (por suposición), lo que nos da $n-1$ posibilidades del número de personas que alguien puede conocer. A cada persona se le debe asignar una de estas $n-1$ números posibles, pero como hay $n$ Los asistentes a la fiesta deben utilizar uno de estos números dos veces debido al principio de encasillamiento, es decir, dos asistentes a la fiesta conocen el mismo número de personas.

1 votos

Esto no es exacto. el mínimo es 0 amigo. Sin embargo, si la amistad es simétrica, no podemos tener al mismo tiempo al participante A con 0 amigos y al participante B con n-1 amigos. Por lo tanto, en cualquier caso, el número de casilleros es n-1.

4 votos

En la pregunta original se planteaba como una suposición que el número mínimo de amigos es 1 mediante la afirmación "dado que cada persona de la fiesta conoce al menos a una persona". Es posible demostrar la misma afirmación sin esa suposición, pero como era libre de usarla, lo hice.

1 votos

Dime cómo lo vas a demostrar sin ese supuesto...... Tengo contraejemplo ...

3voto

Nicole Brewer Puntos 21

Hay que tener en cuenta dos casos:

  1. Supongamos que hay alguien en la fiesta, digamos Joe, que conoce a todos los demás en la fiesta. Él debe saber $n-1$ personas. En este caso, todas las personas de la fiesta deben conocer al menos a Joe, y el número mínimo de personas que una persona puede conocer es $1$ . Esto nos da el conjunto $\{1, 2, ... n - 1\}$ que representa el número posible de personas que cada persona puede conocer.
  2. Supongamos que hay un colado en la fiesta, Harry, que en realidad no conoce a nadie. Esto significa que ni siquiera un miembro de la sociedad como Joe puede conocer a todo el mundo, por lo que el número máximo de personas que puede conocer una persona es $n - 2$ . Esto nos da el conjunto $\{0, 1, ..., n - 2\}$ .

Ambos conjuntos tienen n-1 elementos. Como hay $n$ gente en la fiesta, y $n-1$ posibilidades para el número de personas que cada persona puede conocer, se deduce que debe haber al menos dos personas que conozcan el mismo número de personas.

0 votos

El segundo caso es innecesario porque se da que cada persona conoce al menos a una persona

0voto

Rupam Maiti Puntos 6

Para cada persona del grupo, el número de conocidos es $0$ o $1$ o $2$ ...o... o $n - 1$ .

Supongamos primero que no hay dos personas que tengan el mismo número de conocidos, de modo que cada uno de los $n$ números, $0$ a $n - 1$ está representada.

Pero como la presencia de $0$ significa que hay una persona que conoce nadie, y la presencia de $n - 1$ significa que hay una persona conocida de todos, entonces nuestra suposición de que no hay dos personas tienen el mismo número de conocidos conduce a una contradicción. Esta suposición es insostenible. Nos vemos obligados a concluir que hay dos personas con el mismo número de conocidos.

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