Demostrar el Teorema del Saludo con inducción

Question

Sea $n \in \mathbb{N}$, y suponga que $n \geq 1$. Suponga que está en una fiesta de $n$ personas (incluyéndote a ti mismo). Al final de la fiesta, defina la paridad de una persona como impar si ha dado la mano a un número impar de personas, y par si ha dado la mano a un número par de personas. Demuestre que el número de personas con paridad impar debe ser par.

Mi enfoque es primero encontrar el caso base, que es cuando $n = 1$, entonces $0$ personas han dado la mano a un número impar de personas, y $0$ es par, estamos listos.

Para el paso de inducción, asumimos que para $k \in \mathbb{N}$ personas, el número de personas con paridad impar debe ser par, queremos mostrar que para $k+1$ personas, el número de personas con paridad impar también es par. Intenté dividirlo en dos casos:

• Caso 1: La paridad de la nueva persona es par
• Caso 2: La paridad de la nueva persona es impar

Pero luego me quedo atascado y no sé qué hacer ya que hay tantos casos que pueden ser y me pregunto si hay un enfoque más inteligente.

Answer 1

De manera equivalente, las paridades tienen una suma par. El paso base $n=0$ es trivial. Supongamos que $n=k$ funciona, luego agreguemos a la persona $k+1$. Si esa persona se saluda con $j$ de las primeras $k$ personas, la suma de las paridades aumenta módulo $2$ por $j+j=2j=0$.

Answer 2

Cuando se agrega una persona nueva, esa persona saluda a $p$ personas y altera la paridad anterior.

Suponiendo que la afirmación es verdadera para algún k:

• Hay $k_1$ personas pares
• Hay $k_2$ personas impares y $k_2$ mod $2$ = $0$

Agregando una nueva persona que saluda a $p$ personas (caso $k+1$)

• Si saluda a $p_1$ personas pares, esas personas se vuelven impares
• Si saluda a $p_2$ personas impares, esas personas se vuelven pares
• $p_1$ + $p_2$ = $p$

El nuevo número de personas impares es:

• Caso 1: $k_2$ - $p_2$ + $p_1$ + 1 si $p$ es impar
• Caso 2: $k_2$ - $p_2$ + $p_1$ si $p$ es par

Por hipótesis de inducción, $k_2$ es par.

Y debido a que $p_1$ - $p_2$ = $p$ - $2p_2$ podemos concluir que $p_1$ - $p_2$ = $p$ mod $2$

En ambos casos, el número de personas impares es par.

Answer 3

Creo que tu enfoque es bueno, y casi lo has logrado.

... el caso base, que es cuando $n = 1$, entonces hay $0$ personas que han estrechado la mano con un número impar de personas, y $0$ es par, hemos terminado.

Para el paso de inducción, asumimos que para $k \in \mathbb{N}$ número de personas, el número de personas de paridad impar debe ser par, queremos demostrar que para $k+1$ número de personas, el número de personas de paridad impar también es par.

Considera una fiesta de $k$ personas con $a$ personas que tienen paridad en el saludo y $b$ personas que tienen paridad impar. Según la hipótesis de inducción, $b$ es par. Luego se agrega una nueva persona y debido a sus saludos, $c$ invitados existentes cambian de par a impar y $d$ de impar a par.

• Caso 1: La paridad de la nueva persona ($c{+}d$) es par. El nuevo número de personas de paridad impar es $b{+}c{-}d$. Nota que dado que $c{+}d$ es par, $c{+}d-2d=c{-}d$ también es par. Por lo tanto, $b{+}c{-}d$ es par como se requiere.

• Caso 2: La paridad de la nueva persona es impar. El nuevo número de personas de paridad impar es $b{+}c{-}d{+}1$ (el $+1$ es por la nueva persona). Ahora $c{+}d$ es impar, $c{+}d{+}1$ es par y $c{+}d{+}1-2d=c{-}d{+}1$ también es par. Así que el conteo de paridad impar $b{+}c{-}d{+}1$ es nuevamente par como se requiere.

Answer 4

Sin inducción:

Para cada persona, considera el número de apretones de manos en los que participaron. Si sumas estos $n$ números, deberías obtener dos veces el número total de apretones de manos que ocurrieron (ya que cada apretón de manos se cuenta dos veces). Dado que la suma de estos $n$ números es un número par, ¿qué dice eso sobre el número de números impares?

Answer 5

El número de participantes en un apretón de manos es dos.

Para cualquier número $n$ de apretones de manos. Si sumamos el número de veces que cada persona ha participado en un apretón de manos, contaremos 2n participaciones.

Supongamos que un número impar de personas participaron en un número impar de apretones de manos. El recuento total de participaciones será un número impar. Esto contradice nuestra declaración anterior.

Si desea una demostración por inducción.

Caso base $n=1$ Una persona saluda a nadie y no hay personas con un número impar de apretones de manos.

Supongamos que para todas las reuniones de $n$ personas nuestra proposición se cumple.

Cuando llega el invitado n+1, ha experimentado 0 apretones de manos y nuestra proposición sigue siendo cierta. Para cada apretón de manos que ocurre después de la llegada de este invitado, cambia la paridad de ambos participantes. El número de personas que han experimentado un número impar de apretones de manos cambia por $0, 2,$ o $-2.$

Si nuestra proposición se cumple para $n$ personas, debe cumplirse también para $n+1$ personas.