En una fiesta la gente se da la mano entre sí (no necesariamente todos con todos).
(a) Demuestra que 2 personas se dan la mano el mismo número de veces.
(b) Demuestre que el número de personas que se dan la mano un número impar de veces es par.
Me parece que esta pregunta es muy difícil y no encuentro la forma de empezar a responderla. Sería estupendo que me dieran una pequeña pista para poder al menos empezarla.
Pistas:
Para (A) con $n$ personas en la fiesta, ¿cuál es el número posible de manos que podría estrechar cada persona?
Demuestre que es imposible que alguien haya estrechado la mano a todo el mundo y que alguien no haya estrechado la mano a nadie simultáneamente.
¿Hay alguna manera de utilizar el principio de encasillamiento aquí?
Para (B) contar el número de apretones de manos que se producen sumando cuántos apretones de manos participaron las personas individualmente y reconocer que esto sobrecontó de alguna manera (porque cada apretón de manos lo contamos dos veces: una de la persona más baja de las dos y otra de la persona más alta). Esto nos da un resultado útil llamado "el lema del apretón de manos".
¿Qué sucede entonces si hay un número impar de personas que estrecharon un número impar de manos? Recuerda que el número de apretones de manos debe ser un número entero.
@OsheenSachdev ¿Has oído hablar de la principio de encasillamiento ? Si sólo tiene $k$ agujeros y estrictamente más de $k$ palomas y colocar cada paloma en un agujero, al menos un agujero debe tener estrictamente más de una paloma en él. ¿Cuántas posibilidades hay de número de apretones de manos para que un individuo participe? ¿Cuántas personas se dan la mano?
$(a)$ Digamos que hay $n$ personas en la fiesta y asumir que todos se dan la mano al menos una vez. El número de apretones de manos posibles para todo el mundo es entonces $n-1$ (el auto-apretón de manos no cuenta) mientras haya $n$ personas en el partido, por lo que el principio de pingeon-hole da el resultado deseado. Ahora bien, si no suponemos que todo el mundo estrecha al menos una mano, entonces podemos separar el $n$ personas entre $k$ que no dan la mano y $m$ que hacen ( $k+m=n$ ), y el problema se reduce al último caso (con $n=m$ ).
$(b)$ Si una persona $A$ da la mano a una persona $B$ entonces $B$ se da la mano con $A$ . Aunque parezca una tontería, esto nos dice que podemos contar los apretones de manos por parejas, por lo que el número total de apretones de manos debe ser par. Contando por separado los apretones de manos de los que han dado un número par de apretones de manos y los que han dado un número impar de apretones de manos se llega a la conclusión deseada.
Si el número de todos los apretones de manos es n(n-1), este número es par en cualquier caso porque el producto de un número par por un número impar es siempre par. Si n es par, n-1 es impar y si n es impar, n-1 es par.
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.
1 votos
@TakahiroWaki Esto es un ejercicio común de combinatoria y principio de encasillamiento. Es posible que el PO no haya incluido una frase clave que diga que nadie da la mano a otro más de una vez cada uno. Esto nos permite describir el escenario como un grafo simple (no un multigrafo), y el resultado se puede reformular "cualquier secuencia de grados en un grafo tendrá una entrada repetida" No hay contraejemplo porque es cierto.
0 votos
He comprobado que dar la mano a la misma persona es, como mucho, una sola vez. Parece que he contado varias veces.