Una pregunta de impar sobre la inducción.

Question

Dado $n$ $0$ y $n$ $1$ distribuido de cualquier manera alrededor de un círculo, demuestre, usando la inducción en $n$ que es posible comenzar en algún número y proceder en el sentido de las agujas del reloj alrededor del círculo hasta la posición inicial original de manera que, en cualquier punto del ciclo, hayamos visto al menos tantos $0$ 's como $1$ 's:

Answer 1

Hay al menos un caso de $0$ seguido de un $1$ . Eliminar estos dos números, encontrar (por hipótesis de inducción) un buen punto de partida para el círculo reducido, poner el $0$ y $1$ volver a entrar y utilizar la misma posición de partida. Se comprueba fácilmente que se trata de una posición inicial válida.

Tampoco es difícil mostrar el resultado sin inducción: Una persona que camina alrededor del círculo y deja caer un dólar en cada $0$ visto y recogiendo un dólar (de la nada) en cada $1$ visto terminará con la misma cantidad con la que empezó. Y conseguirá completar el recorrido siempre que empiece con suficiente dinero en el maletín. Para un punto de partida arbitrario, elige la cantidad mínima válida de dólares para empezar. Entonces, en algún punto del recorrido el maletín está vacío. Empezar el recorrido en ese lugar en cambio da el resultado deseado.

Answer 2

Alternativamente: Contar el número total de formas de organizar $0$ s y $1$ s alrededor de un círculo ( $2n$ dígitos binarios en total), considere el número de palabras Dyck de longitud $2n$ es decir, el $n$ th Número catalán y luego utilizar el principio de encasillamiento. "QED"

Answer 3

Aunque ya se ha dado una prueba sencilla de tu problema en otras respuestas, he querido complementarlas con algo más de información (espero que interesante). De hecho, este es un caso especial de un problema muy antiguo:

Dejemos que $(a_i)_{i=0}^{n-1}$ sea una secuencia de $n$ números reales de suma no negativa, es decir, $\sum_{i=0}^{n-1} a_i \geq 0$ . Entonces, existe un índice $k$ tal que todas las sumas parciales (de $n$ plazos a partir de $k$ ) $\sum_{i=k}^{m+k} a_{i\ \bmod n}$ para $m = 0,1,\ldots,n$ son no negativos.

En su configuración cambie $0$ s a $(-1)$ s y utilizar el teorema anterior. En cuanto a su demostración, se puede utilizar la inducción, pero es más fácil hacerlo directamente. El punto clave es que, cuando se parte del nivel más bajo posible, todo el resto del camino estará realmente por encima (es decir, mayor o igual) de cero.

En la imagen de arriba podemos ver dos de sumas parciales (por comodidad), la línea negra horizontal delgada es el cero absoluto. Si partiéramos del nivel más bajo posible (línea roja oscura), todos los demás (franjas verdes oscuras) estarían por encima del nivel inicial (línea azul).

La demostración del teorema mencionado pone exactamente la observación en fórmulas y concluye después de un cálculo bastante simple. No la reproduciré aquí, porque sólo ofuscaría la idea básica que hay detrás de la imagen.

Espero que esto ayude ;-)