Personas y apartamentos

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 400
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Personas y apartamentos

Mensaje sin leer por Prillo » Jue 27 Oct, 2011 11:40 pm

En un edificio con [math] apartamentos viven [math] personas. Decimos que un apartamento esta sobrepoblado si en él viven por lo menos [math] personas. Cada día, los habitantes de algún apartamento sobrepoblado se pelean y cada uno se va a vivir a un apartamento distinto del edificio para evitar verse entre sí (al menos ese día). Es cierto que este proceso debe terminar algún día?

Avatar de Usuario
pornprimes
Mensajes: 10
Registrado: Lun 18 Oct, 2010 12:16 am

Re: Personas y apartamentos

Mensaje sin leer por pornprimes » Dom 30 Oct, 2011 2:04 am

Toy flasheando?
Spoiler: mostrar
Por palomar, como hay más departamentos que personas, el problema sigue. Q.E.D.
Spoiler: mostrar
Yo dawg. Nah, ahora va en serio:
Por palomar, hay al menos 15 apartamentos vacíos al empezar, o no habría ninguno sobrepoblado.
Si el proceso nunca termina, estos 15 apartamentos tienen, en total, en el día 14, exactamente [math] (?) personas. Absurdo.
In fact, si no entendí nada mal y no flasheé por la hora, alcanza con que haya 9 apartamentos vacíos, i.e. 125 personas. ¿Es la mejor cota? Ya pensar ejemplos da paja.

Avatar de Usuario
ésta

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2017 OFO - Jurado-OFO 2018
Mensajes: 295
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Re: Personas y apartamentos

Mensaje sin leer por ésta » Dom 30 Oct, 2011 2:24 am

Con 120 personas ya es mentira el problema
Imagen

Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1020
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Personas y apartamentos

Mensaje sin leer por Ivan » Dom 30 Oct, 2011 2:24 am

Creo que flasheaste.
Spoiler: mostrar
Sale mirando una cuenta que decrece en cada paso.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)

Avatar de Usuario
Carolang
Mensajes: 65
Registrado: Vie 05 Nov, 2010 12:14 am
Nivel: Exolímpico
Ubicación: Flores

Re: Personas y apartamentos

Mensaje sin leer por Carolang » Dom 13 Nov, 2011 8:14 pm

Conste que no revisé mucho xD si hay algo que está mal me lo hacen saber.
Spoiler: mostrar
Supongamos que un apartamento comienza con [math] ocupantes, y que pasan [math] turnos. Está claro que al final del i-ésimo turno el apartamento tiene a lo sumo [math] ocupantes.

Ordenamos a los apartamentos según el orden en el que los elegimos para que sus habitantes se peleen. Sean [math] los [math] apartamentos.
Observamos que si elegimos una habitación en el turno [math], recién podemos elegirla de vuelta en el turno [math] (al principio del turno [math], con [math], la habitación tiene a lo sumo [math] ocupantes, para que tenga [math] tiene que pasar que [math]). Luego en los primeros [math] turnos debemos elegir habitaciones diferentes. Esto quiere decir que elegimos, para [math], la habitación [math] en el i-ésimo turno.

Para poder elegir la habitación [math] en el i-ésimo turno, esta habitación debe tener [math] ocupantes o más. Sea [math] la cantidad de ocupantes iniciales de la i-ésima habitación. Por lo que vimos arriba, la cantidad de ocupantes iniciales más la cantidad de turnos que pasaron antes de elegir la habitación es por lo menos [math], es decir que[math] para las primeras [math] habitaciones.

Sumamos esta cantidad para estas habitaciones. Tenemos que:

[math]

[math]

[math]

Esto significa que la sumatoria de las cantidades iniciales de personas en estas habitaciones debe ser por lo menos [math]. Sin embargo el enunciado dice que la cantidad de personas es a lo sumo [math]. Se sigue que el procedimiento nunca dura más de [math] pasos, por lo tanto termina.
Última edición por Carolang el Dom 13 Nov, 2011 9:59 pm, editado 1 vez en total.
Imagen Azúcar, flores y muchos colores.

Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1020
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Personas y apartamentos

Mensaje sin leer por Ivan » Dom 13 Nov, 2011 8:49 pm

Si en el departamento [math] hay [math] personas se puede ver que en cada paso la suma [math] decrece al menos [math]:

Sin perder generalidad supongamos que los habitantes del departamento [math] se pelean y se van a vivir a los departamentos [math].

Entonces tenemos que la suma luego de ese día es:

[math]

Con lo cual la diferencia es

[math]

Cómo la suma siempre es positiva el proceso termina en algún momento.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)

Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 47
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario - Santa Fe

Re: Personas y apartamentos

Mensaje sin leer por Fran2001 » Mié 18 Mar, 2020 10:10 am

Spoiler: mostrar
Sea $N$ una noche.
El próximo departamento que se pelee debe tener al menos $15$ habitantes en la noche $N$.
El siguiente debe tener al menos $14$ habitantes en la noche $N$ (ya que en cada noche recibe a lo sumo $1$ habitante).
El siguiente debe tener al menos $13$ habitantes en la noche $N$ (ya que en cada noche recibe a lo sumo $1$ habitante).
$\vdots$
El siguiente debe tener al menos $1$ habitante en la noche $N$ (ya que en cada noche recibe a lo sumo $1$ habitante).

Es decir que si se pelearan $15$ noches, deberíamos tener al menos $1+2+\dots +15=120$ personas.
Por lo tanto el proceso debe durar menos de $15$ noches.
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4

Responder