[davdav]

Buenas tardes. Dejo por aquí un problema muy sencillo a ver si alguien sabe resolverlo.

Hay un problema muy conocido que dice: Si tenemos 50 niños y 50 niñas distribuidos
en una fila, siempre es posible encontrar 50 personas consecutivas de las cuales 25 serán niños y 25 niñas.

Y se puede demostrar muy fácilmente. Si en la fila de las primeras 50 personas hubiera 25 niñas/niños, ya está resuelto el problema. Si hubiera menos niñas,
por ejemplo 15 niñas, eso significaría que en las 50 restantes deberían estar las restantes 35.

Por ejemplo, llamemos A(1,50) al número de niñas en las primeras 50 personas. Cada vez que avanzamos una posición, es decir, pasamos por ejemplo de A(1,50) a A(2,51), el número de niñas sólo puede aumentar o disminuir en 1 unidad. Por tanto, como en nuestro ejemplo A(1,50)=15, y por tanto A(51,100)=35, entonces para llegar a este número deberemos haber pasado sí o sí por una hilera de 50 personas consecutivas que tuviera 25 niñas.


Ahora bien, creo que este problema se puede generalizar para cualquier fila de personas que tengan igual número de niñas y niños,
siendo la hilera de personas consecutivas n, y el número de niñas/niños que podremos encontrar en ella n/2.

Por ejemplo: es posible encontrar en una fila de 50 personas una hilera consecutiva de 8 personas, en las que la mitad sean niños y la mitad niñas.

¿Es posible demostrar que se cumple, o que no, esta generalización? En caso afirmativo, ¿cuál sería la manera más sencilla posible de demostrarlo?
(Alomejor se demuestra de manera igual de evidente que el problema inicial y no he llegado a darme cuenta)

Gracias de antemano.

[Ignacio Larrosa]

Buenas tardes. Dejo por aquí un problema muy sencillo a ver si alguien sabe resolverlo.

Hay un problema muy conocido que dice: Si tenemos 50 niños y 50 niñas distribuidos
en una fila, siempre es posible encontrar 50 personas consecutivas de las cuales 25 serán niños y 25 niñas.

Y se puede demostrar muy fácilmente. Si en la fila de las primeras 50 personas hubiera 25 niñas/niños, ya está resuelto el problema. Si hubiera menos niñas,
por ejemplo 15 niñas, eso significaría que en las 50 restantes deberían estar las restantes 35.

Por ejemplo, llamemos A(1,50) al número de niñas en las primeras 50 personas. Cada vez que avanzamos una posición, es decir, pasamos por ejemplo de A(1,50) a A(2,51), el número de niñas sólo puede aumentar o disminuir en 1 unidad. Por tanto, como en nuestro ejemplo A(1,50)=15, y por tanto A(51,100)=35, entonces para llegar a este número deberemos haber pasado sí o sí por una hilera de 50 personas consecutivas que tuviera 25 niñas.


Ahora bien, creo que este problema se puede generalizar para cualquier fila de personas que tengan igual número de niñas y niños,
siendo la hilera de personas consecutivas n, y el número de niñas/niños que podremos encontrar en ella n/2.

Por ejemplo: es posible encontrar en una fila de 50 personas una hilera consecutiva de 8 personas, en las que la mitad sean niños y la mitad niñas.

¿Es posible demostrar que se cumple, o que no, esta generalización? En caso afirmativo, ¿cuál sería la manera más sencilla posible de demostrarlo?
(Alomejor se demuestra de manera igual de evidente que el problema inicial y no he llegado a darme cuenta)

Creo que es válido el mismo razonamiento. Si tienes \( \frac{n}{2} \) niños y \( \frac{n}{2} \) niñas en fila, y examinas todas las secuencias de \( 2d \) de ellos, te puedes encontrar que ya de entrada hay \( d \) niños y \( d \) niñas. De no ocurrir así, supongamos que hay menos niñas que niños. Como en toda la fila hay igual número de ellos, en otra secuencia de \( 2d \) debe haber más niñas. Como cada vez que desplazamos la secuencia el número de niñas que incluye permanece, aumenta en uno o disminuye en uno, para ir de una a otra necesariamente se pasa por una en la que hay exactamente \( d \) niñas.

Saludos,

[davdav]

Creo que es válido el mismo razonamiento. Si tienes \( \frac{n}{2} \) niños y \( \frac{n}{2} \) niñas en fila, y examinas todas las secuencias de \( 2d \) de ellos, te puedes encontrar que ya de entrada hay \( d \) niños y \( d \) niñas. De no ocurrir así, supongamos que hay menos niñas que niños. Como en toda la fila hay igual número de ellos, en otra secuencia de \( 2d \) debe haber más niñas. Como cada vez que desplazamos la secuencia el número de niñas que incluye permanece, aumenta en uno o disminuye en uno, para ir de una a otra necesariamente se pasa por una en la que hay exactamente \( d \) niñas.

Saludos,

Intuitivamente la idea es la misma, sí, pero en este caso no quedaría demostrada esta afirmación. ¿Cómo se puede demostrar más formalmente que vas a encontrar otra hilera de 2d personas consecutivas con mayor número de niñas? (Al haber inicialmente igual nº de niñas que niños se intuye que tiene que ser así, pero no queda demostrado).

[robinlambada]

Hola.

Creo que es válido el mismo razonamiento. Si tienes \( \frac{n}{2} \) niños y \( \frac{n}{2} \) niñas en fila, y examinas todas las secuencias de \( 2d \) de ellos, te puedes encontrar que ya de entrada hay \( d \) niños y \( d \) niñas. De no ocurrir así, supongamos que hay menos niñas que niños. Como en toda la fila hay igual número de ellos, en otra secuencia de \( 2d \) debe haber más niñas. Como cada vez que desplazamos la secuencia el número de niñas que incluye permanece, aumenta en uno o disminuye en uno, para ir de una a otra necesariamente se pasa por una en la que hay exactamente \( d \) niñas.

Saludos,

Intuitivamente la idea es la misma, sí, pero en este caso no quedaría demostrada esta afirmación. ¿Cómo se puede demostrar más formalmente que vas a encontrar otra hilera de 2d personas consecutivas con mayor número de niñas? (Al haber inicialmente igual nº de niñas que niños se intuye que tiene que ser así, pero no queda demostrado).

Si se puede demostrar, por el hecho de que hay igual número de niños que de niñas en total.
Si en la 1ª hilera de 2d personas encuentras más niños que niñas pasas a la segunda hilera de 2d personas, que ocurre igual, pasa a la 3ª hilera, tarde o temprano llegarás a una hilera con más niñas que niños, por reducción al absurdo, si no pasara así es decir en todas las hileras hubiera más niños que niñas al sumar los niños y niñas de todas las hileras llegarías a que hay más niños en total que niñas, lo cual es absurdo.

Saludos.

[davdav]

Si se puede demostrar, por el hecho de que hay igual número de niños que de niñas en total.
Si en la 1ª hilera de 2d personas encuentras más niños que niñas pasas a la segunda hilera de 2d personas, que ocurre igual, pasa a la 3ª hilera, tarde o temprano llegarás a una hilera con más niñas que niños, por reducción al absurdo, si no pasara así es decir en todas las hileras hubiera más niños que niñas al sumar los niños y niñas de todas las hileras llegarías a que hay más niños en total que niñas, lo cual es absurdo.

Saludos.

Cierto, es verdad, no lo había pensado así.

Gracias a ambos por la respuesta.

[Masacroso]

Una forma más formal (valga la redundancia ). La demostración es equivalente a mostrar que si tenemos una función \( D:\{0,\ldots,2n\}\to\{0,\ldots,2n\} \) para algún \( n\in\Bbb N_{>0} \) que cumple que

1) \( D(k)=x\implies D(k+1)\in\{x-1,x,x+1\} \) para cualquier \( k\in\{0,\ldots,2n-1\} \)

2) \( D(0)=x \) y \( D(2n)=2n-x \), para algún \( x\in\{0,\ldots,2n\} \).

Entonces existe un \( k\in\{0,\ldots,2n\} \) tal que \( D(k)=n \).

Se puede demostrar por contradicción: supongamos que tal \( k \) no existe y, sin pérdida de generalidad, que \( D(0)<n \), entonces necesariamente debido a la primera propiedad tenemos que \( D(1)<n \), y por inducción en \( k \) se demuestra que \( D(k)<n \) para todo \( k\in\Bbb N \), lo cual es imposible ya que por la segunda propiedad \( D(2n)>n \).

[robinlambada]

Mi razonamiento anterior es válido si n es divisible entre 2d, en caso de que no lo fuera y fuera por ejemplo \( n=k\cdot{}(2d) +r \) con r el resto de la división Euclidea \( 0<r<2d \), a lo sumo si en todos los grupos de 2d así formados desde \( A(1,2d) \) hasta \( A((k-1)\cdot{2d}+1,2dk) \) en el último de r componentes habría más niñas que niños, si juntamos los dos últimos grupos desde \( A((k-1)\cdot{2d},n) \) de \( 2d+r \) componentes seguiría habiendo más niñas que niños, por que en los restantes \( k-1 \) primeros grupos habria en total más chicos.

ahora solo falta probar que del último grupo de 2d+r personas se puede reducir a uno de 2d personas con d chicos y d chicas puesto que en el hay más de d niños y niñas ya que en el penúltimo grupo originalmente de 2d integrantes había más niños que niñas antes de su unión y en la unión de ambos hay más niñas que niños.

Creo que esta última parte que no demuestro se puede demostrar quitando adecuadamente componentes del grupo de \( 2d+r \) hasta quedarse con 2d integrantes con igual chicos y chicas, teniendo en cuenta k y r.

P.D.:Lo dejo para que lo pensemos( lo marcado en verde), ahora debo irme.

Añadido, parece que masacroso lo resolvio más formal y elegantemente.

[robinlambada]

Hola.
Creo que o no he entendido del todo la demostración de masacroso, o pienso que la hace para 4n personas ( 2n chicos y 2n chicas) y los grupos son de la mitad de personas 2n . Pero no la hace en general para grupos menores de personas 2d con d<n. al menos eso entiendo.

Por paridad creo haberlo solucionado.

Sean 2n personas con con n niños y n niñas.

Sea D la función que da la diferencia entre el número de niños y niñas de los primeros k personas de la fila.

\( D:\left\{{1,2...2n}\right\}\rightarrow{}\left\{{-n,....-1,0,1,...n}\right\} \)

Entonces tenemos estas propiedades:

\( D(0)=0 \) , \( D(2n)=0 \)

Si \( D(k)=m \) entonces \( D(k\pm{}1)=m\pm{}1 \)

Es decir \( D(k+1)-D(k)=\pm{}1 \)

El problema se limita a demostrar que existen 2 p,q con \( 0\leq{}q<p\leq{}2n \)

Tal que \( p-q=2d\leq{}n \)  y \( D(p)-D(q)=0 \).

Podemos suponer que  \( D(2d)=m\neq{}0 \) ( si no la demostracion es trivial por ser D(2d)=0, la primera subfila de las 2d primeras personas tiene diferencia cero, igual chicos que chicas )por comodidad m>0

Entonces \( D(2d+1)-D(1)=m\pm{}2 \) ya que \( D(2d+1)=m\pm{}1 \) y \( D(1)=\pm{}1 \), por tanto al irnos moviendonos por la fila con 2d elementos, desde k=0 hasta k=2n-2d la paridad de m no cambia siempre será par o impar.

Si partimos de que \( D(2n)-D(0)=0-0=0 \) que es par.

Haciendo \( D(2n-1)-D(1)=\pm{}2 \) llegaremos a que \( D(2n-l)-D(l)=\pm{}2t \) y \( 2n-2l=2d \) que también es par

Llegamos a que \( D(2d)=m=2k' \) es par.

Como hay el mismo número de niños que de niñas, no puede ser \( D(2d+l)-D(l)>0 \)  siempre, llegara un momento en que exista un q tal que

\( D(2d+q=p)-D(q)=0 \)

Saludos.

[Masacroso]

Claro, mi demostración es sólo para grupos de tamaño \( 4n \), de otro modo tendríamos "medias personas". Por ejemplo, si he entendido bien para una fila de tamaño \( 5 \) tendríamos \( 2,5 \) chicos y \( 2,5 \) chicas, ¿no? Y si intentamos generalizar desde un número de chicos y chicas iguales, por ejemplo desde \( 5 \) chicas y \( 5 \) chicos (para un total de \( 10 \) personas en fila) tendríamos que demostrar que existe una fila interior de \( 5 \) personas donde la mitad son cada una de un sexo distinto, volviendo otra vez a los \( 2,5 \) de cada sexo.

Por eso sólo he generalizado para \( 4n \), no veo como hacerlo en otro caso.

Aclarando: la demostración de arriba equivale a demostrar que en una fila de \( 4n \), donde \( 2n \) son de cada sexo, existe una fila interna de tamaño \( 2n \) tal que el número de chicos y chicas es el mismo (es decir, constituida por \( n \) chicos y \( n \) chicas).

AÑADIDO: ¡Ah..! ya veo, se busca un resultado más general para un fila interior de tamaño \( 2d \). Ok, veré como puedo llegar hasta ello.

SEGUNDO AÑADIDO: de mi función anterior \( D \) se pueden generalizar funciones similares \( D_n(\cdot,d) \) y demostrar cada caso mostrando que existen \( k_1\neq k_2 \) tales que \( D_n(k_1,d)\le d\le D_n(k_2,d) \) para cualquier \( d\in\{1,\ldots,n\} \).

Es decir, mi demostración anterior variaría en lo siguiente: definimos las funciones \( D_n(\cdot,d):\{0,\ldots,4n-2d)\}\to\{0,\ldots,2d\} \) que cuentan el número de chicos (o chicas) en filas de tamaño \( 2d \) en posición \( k \), con las propiedades

1) \( D_n(k, d)=x\implies D_n(k+1,d)\in\{x-1,x,x+1\} \) para todo \( k\in\{0,\ldots,4n-2d-1\} \).

2) \( D_n(0,n)=x\implies D_n(2n,n)=2n-x \).

Entonces se puede demostrar que existen \( k_1\neq k_2 \) tales que \( D_n(k_1,d)\le d\le D_n(k_2,d) \) para cualquier \( d\in\{1,\ldots,n\} \), y utilizando la estrategia anterior mostrar que efectivamente existe un \( k \) tal que \( D_n(k,d)=d \).

Sin embargo debe haber una demostración por inducción más sencilla y menos aparatosa.
 

[Luis Fuentes]

Hola

 Ando con prisas, pero algunas ideas generales:

 1) No es cierto en general que en una hilera de \( n \) niños y \( n \) niñas, dado \( d<n \) exista necesariamente \( 2d \) personas consecutivas con \( d \) niños y \( d \) niñas. Por ejemplo:

\( n=4,d=3 \), con la configuración \( HHMMMMHH \)

2) La clave para generalizar la idea del problema inicial y lo que apunta Ilarrosa es efectivamente justificar que existe un grupo de \( 2 \)d personas consecutivas con más niños que niñas y otro donde ocurre lo contrario. En ese caso es claro que "por en medio" se encuentra un grupo con \( d \) niños y \( d \) niñas. Es el cabo suelto y la madre del cordero de todo esto.

 3) Como bien apuntó robinlambda eso está justificado si \( n=kd \), para \( k>1 \).

 4) Queda por tanto:

 4.1) Hacer la hipótesis correcta sobre que hay que exigir a \( d \) respecto de \( n \), para que se cumpla el resultado. Por ejemplo uno sospecha que al menos para \( d\leq n/2 \) debería de funcionar.

 4.2) Luego probar la hipótesis.

 5) En la propuesta formal de masacroso la parte "difícil" o no tan obvia es probar que:

existen \( k_1\neq k_2 \) tales que \( D_n(k_1,d)\le d\le D_n(k_2,d) \) para cualquier \( d\in\{1,\ldots,n\} \)

De hecho como vimos en el contraejemplo inicial no es cierto sin alguna condición adicional sobre \( d \).

 6) En la de robinlambada (donde por cierto para evitar equívocos apunto que definie una función \(  \)D de significado diferente a la de masacroso), no es cierta esta parte... ¡la esencial!:

Como hay el mismo número de niños que de niñas, no puede ser \( D(2d+l)-D(l)>0 \)  siempre, llegara un momento en que exista un q tal que

\( D(2d+q=p)-D(q)=0 \)

 No veo como de todo lo anterior se deduce lo rojo. Es más, sabemos que sin usar alguna condición adicional sobre \( d \) de hecho no es cierto.

Saludos.

P.D. Como curiosidad el resultado si es cierto para cualquier \( d\leq  \)n si la disposición es en una mesa circular. Y ahí si es fácil de probar.