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 :)
0 votos
@frogeyedpeas Nope no necesariamente. A conoce a B pero B no necesariamente conoce a A.
0 votos
Este es el objetivo del ejercicio. Cite el principio de encasillamiento y habrá terminado.
0 votos
@CptSupermrkt A mí me parece una prueba. Las pruebas no necesitan ser formal simplemente tienen que ser estanco . ;)
4 votos
En primer lugar, +1 por una pregunta bien redactada que demuestra tu esfuerzo. En segundo lugar, el primer comentario anterior, de MJD, es una prueba perfectamente válida. Fíjate en una sutil diferencia entre el tuyo y el suyo: das por hecho que la primera persona sabe $n-1$ personas, el segundo sabe $n-2$ etc., lo cual es difícil de justificar sin un poco más de esfuerzo. De la manera más hábil, se deja que el número de personas conocidas por la primera persona, la segunda, etc. sea cualquiera, y se invoca el principio de encasillamiento para decir que se tiene $n$ números que toman valores en $1$ a $n-1$ , por lo que algunos dos deben coincidir. De todas formas esto es seguramente lo que quería tu profesor.
0 votos
Gracias, no me había fijado en el menos uno.