Acertijo Premio. Torneo de resolución de Acertijos. Por Lorena Bergamini
Este problema me lo propuso un profesor que entrenaba para olimpiadas matemáticas.
Un acertijero se entrena para el segundo torneo de acertijos de Pequeños Enigmas durante 11 semanas. Cada día resuelve al menos un acertijo, y a lo sumo 12 por semana.
Al final del entrenamiento notó que hubo una cantidad de días consecutivos, en los que resolvió, en total, 21 problemas. Y también notó que esto hubiera pasado de cualquier forma que haya hecho el entrenamiento, bajo las condiciones antes expuestas.
¿Por qué estaba seguro de esto?
Demostrar que, en las condiciones del problema, siempre habrá un conjunto de días consecutivos en los que resolvió un total de 21 acertijos.
|Dicho por Lorena Bergamini a las 10:25 PM|
Este es un problema tal vez complejo y no muy simple de demostrar. Sin embargo, es interesante ya que ilustra un "principio" que permite resolver muchos otros problemas.
Si les cuesta dar con la solución, después iremos poniendo otros problemas más simples que se resuelven con la aplicación del mismo principio.
Con este problema continúo pagando los premios a los ganadores del torneo.
Gracias Lorena.
A ver si se animan los que faltan.
Suscribirse a:
Enviar comentarios (Atom)
109 comentarios:
postearÃa la respuesta, pero últimamente a estas horas de la noche me dedico a la colombofilia...
Juan Pablo,
entonces envÃa la respuesta por paloma mensajera ;)
Juan Pablo, eso suena fatal =P! ¿O es que compartes afición con Pantuflo Zapatilla, el padre de Zipi y Zape?
Yo voy a ser valiente y exponer mi análisis apresurado a ver si a alguien le sirve. Acotando el planteamiento me parece obvio que el número de acertijos resueltos en 11 semanas será 77 como mÃnimo y 131 como máximo. También que no puedo hacer más de 6 en un mismo dÃa y, por tanto, 21 acertijos deben ser resueltos entre 11 y 21 dÃas.
Una semana tiene 169 (13 al cuadrado pero pura casualidad) formas distintas de ser "organizada" dentro de las normas y supongo que 11 semanas admitirán 169 elevado a 11 = 3,22e24 combinaciones posibles.
Cuando tenga todas revisadas vuelvo.
Tomamos tres semanas consecutivas del medio de la secuencia. Para que no cumplan los 21 dÃas, deben estar en la siguiente secuencia:
1122222 12 2222211
Esto hace que tomando una semana para atrás nos quede el extermo izquierdo (valer igual para el derecho con una semana para adelante) quede
12 1122222
De esta secuencia tomamos los 12 dÃas + 1 ó 2 dependiendo de la semana anterior
Tomando otra semana para atrás nos puede quedar
1122222 12 1122222, tomamos 2222 12 1 = 21
ó
2222211 12 1122222, tomamos 22211 12 1 = 21
ó
1222221 12 1122222, tomamos 2221 12 11 = 21
Siempre se pueden juntar 21 dÃas. Lindo problema Lorena!!
Un cosa más. Basta con que el enunciado abarcara sólo 3 semanas para obligar a la existencia de 21 dÃas consecutivos. o no?
PD. Donde puse en mi comment anterior "extermo" me referÃa a extremo, no a un termo que se me rompió ;)
Demostración:
Es imposible escribir 77 números seguidos que cumpliendo las condiciones del enunciado no me permitan encontrar una serie de números seguidos dentro de ella que sume 21.
Si alquien lo consigue renunciaré a esta demostración.
En serio Lorena : ¿existe alguna demostración que ocupe menos de 20 lÃneas? Todos los caminos que sigo me resultan muy prolijos.
Disinerge a mi me da que en 9 dÃas podemos hacer 21 ejercicios:
6 12(7dias) 3
(y 24 en nueve dÃas también: 6 12(7dias) 3 )
Demostración:
Es imposible encontrar una serie de 77 números que cumpliendo las condiciones del enunciado no me permitan encontrar una serie de números seguidos dentro de ella que sume 21.
Cuando alguien me envÃe una que no me lo permita, renunciaré a esta demostración.
En serio, Lorena : ¿existe alguna demostración que ocupe menos de 20 lÃneas? Todos los caminos que sigo me resultan muy prolijos.
Disinerge a mi me da que en 9 dÃas podemos hacer 21 ejercicios:
6 12(7dias) 3
(y 24 en nueve dÃas también: 6 12(7dias) 6 )
Perdón por el duplicado, pense que el primero no habia salido.
Si, es verdad itn, casi nada de lo que dije fué riguroso. Además me ha dado por la combinatoria ya que no me veo capaz de resolver el problema y descubro con horror ;) que hay 1017 combinaciones distintas para una sola semana por lo que acabo en 1,20e33 posibles "soluciones" legales.
Entonces 21 acertijos se harán como mÃnimo en 9 y máximo en 21 dÃas.
Markelo habla de un principio interesante, que ignoro por completo y no soy capaz de deducir.
Espero que me llegue la inspiración, mientras tanto me sumo al postulado de itn como dogma de fé.
itn, te lo demostrarÃa a golpe de vista, en mucho menos de 20 lÃneas.
Casualmente, como guardo las palomas en jaulas cuya capacidad máxima es de una docena, dividida cada jaula en siete compartimientos, cuando las encierro cada noche sin dejar compartimientos vacÃos verifico el enunciado...
Perdón a todos. Leà mal el enunciado. Parece ser que en las horas tempranas de la mañana las neuronas todavÃa no se me activan :(. No tomen en cuenta mis comment anteriores
Juan Pablo, te lo suplico, deja las palomas encerradas y cuéntanos algo esclarecedor. Al menos una pista!
Gracias Lorena por este problema difÃcil.
TodavÃa no tengo ni idea de cómo atacarlo...
A ver si se me ocurre algún isomorfismo jejeje
le acabo de dedicar un post, porque es bueno que esto vaya de a pares
Gracias Lorena!
Me sale humo por las orejas, pero al menos todavÃa no lo ha resuelto nadie y eso me motiva. Muy bonito tu problema.
Disculpen que llegue tarde. Pero es divertido leer los comentarios juntos.
De todas formas, veo que no fue necesario llegar antes, ya que JuanPablo ha estado orientando acertadamente a todos. Gracias JuanPablo!
Aquà tengo una demostración bastante poco cientÃfica, y que no hace uso de pares/impares como sugiere JuanPablo:
El mÃnimo de problemas por dÃa es 1, asà que si hacemos uno por dÃa, en 3 semanas tendremos la fatÃdica suma de 21:
---7--- ---7--- ---7--- = 21
1111111 1111111 1111111
Entonces cambiemos el último 1 por un dos, para que del 20 pase al 22:
---7--- ---7--- ---8--- = 22
1111111 1111111 1111112
--6--- ---7--- ---8--- = 21
El problema es que si no tomamos el primer 1, volvemos a tener 21, como se ve en la suma de abajo de la hilera. En general, cuando una de las "puntas" de la suma 22 es un 1, para sumar 21 basta con no tomarlo.
Asà que para que no quede un 1 en la punta de la izquierda, empecemos con un 2, y como sumando a la derecha se llega antes a 21, tenemos que cambiar a 2 también el 6to dÃa de la tercera semana:
---8--- ---7--- ---7-- = 22
2111111 1111111 111112?
Ahora bien, si tomamos a partir del 2do dÃa, sumamos 20 al llegar al último 2 que agregamos, por lo que el siguiente número debe ser tambÃen al menos 2:
---8--- ---7--- ---7-- = 22
---6-- ---7--- ---9--- = 22
2111111 1111111 1111122
--5-- ---7--- ---9--- = 21
Pero de nuevo nos queda un 1 en la punta izquierda, y se suma 21 no tomándolo, asà que tendremos que seguir agregando 2s:
---10-- ---7--- -5-- = 22
---8-- ---7--- --7-- = 22
--6-- ---7--- --9--- = 22
-4-- ---7--- --11--- = 22
2221111 1111111 1112222
-3- ---7--- --11--- = 21
De nuevo con la suma 4+7+11 queda un 1 en la punta (4to dÃa de la primera semana), pero si este lo transformamos en 2, tendremos que transformar en 2 los dÃas 2do y 3ero de la tercera semana, lo que ya hace que sobrepasemos el máximo de 12 problemas por semana.
Sumar de a más sólo acelerarÃa la aparición de esa superación del máximo en la tercera semana.
Uh, esto se ve mejor con fonts de tamaño fijo, pero el blog no acepta la instrucción <code>. =(
Cambié <code> por <tt> que si se acepta. Markelo
En el contexto del problema, "semana" es un perÃodo de 7 dÃas, comprendidos entre lunes y domingo, comenzando a entrenarse un lunes. Creo...
Resulta que hay al menos 2 dÃas a la semana en los cuales sólo hago un ejercicio; que hay al menos 6 perÃodos de 2 semanas consecutivas en los que hago el mismo número de ejercicios; que hay al menos 3 semanas (de lunes a domingo, consecutivas o no) en las cuales hago el mismo número de ejercicios; pero de tanto gorjeo de palomas me he mareado y me he cansado de meterlas en cajas. Que algún alma caritativa me dé una pista!!! Socorro!!!!
JuanPablo!!! Yole te llama! (es que justo hoy, yo no tengo el alma caritativa, jeje).
Singing: pares no sólo significa "que no es impar".
Mejor dicho: "pares" no sólo significa "que no son impares"
tengo algo pero no me acaba de convencer ni a mÃ, pero espero que a alguien le inspire:
Tomemos un grupo de 3 semanas (al igual que Alejo, creo que bastan 3 para sumar 21). Llamemos a1, ..., a21 a los problemas que resuelvo del dÃa 1 al 21 y llamemos s1, ...,s21 a las sumas sj=a1+...+aj. Tenemos 21 sumas, si alguna es divisible por 21 ya está! Si ninguna lo es hay al menos 2 que tienen el mismo resto al dividir por 21, sean sk y sl con k>l. consideremos sk-sl= ak+a(k-1)+...+a(l+1) que sumará 21.
Para que vayan afinando la punterÃa, les revelo cual es el famoso principio que está implicado en esta demostración:
El principio del palomar
Si... Juan Pablo no estaba loco ni es (creo) colombófilo. Eran todas pistas.
En google encontrarán abundante material sobre este principio.
Igual, no crean que con esta ayuda está todo resuelto. TodavÃa tienen que pensar bastante para imaginar como aplicarlo.
por cierto, k y l son las que dice Yole
A mi la solución de Yole me parece perfecta, pero creo que harÃa falta aclarar que s7<=12 y s14<=24 y s21<=36
Es decir que sx nunca será 42 o más y por lo tanto si es divisible entre 21 es 21. Por otro lado es claro que ¬(sk= sl) si ¬(k=l), porque al menos se suma uno cada vez.
Y por lo mismo de que ¬(sx>=42), sk=sl+21, siendo además sl<21.
(itn, dile a david que gracias por los simbolitos)
Por más cierto: la paridad no la veo en ningún lado
Una semana puede tener entre 7 y 12 acertijos
Cualquier semana tiene al menos 2 unos
En cualquier semana se puede sumar 7 con distinta cantidad de números
Tomando tres semanas consecutivas se puede sumar 21 salvo para semanas de muchos pares.
Las semanas de muchos pares (12 acertijos: 1122222) molesta en un sentido en el tiempo pero no en el otro, es decir que siempre tenemos al menos un impar para sumar y forzar el 21.
¡Vaya campeona, Yole!.
¡Y ole y ole Yole! ;)
En cuanto a lo de la paridad, ya lo ha dicho Lorena, no se refiere a que "no sea impar"... ¿a que se refiere entonces? Pues a formar una parejita especial.
Algunas conclusiones: lo de las 11 semanas es para despistar ¿no?... BastarÃa con que el número de semanas sea 3 o más. El caso lÃmite es cuando son 3 semanas y es cuando parece más asombroso. En el espacio tan corto de 21 dÃas aseguras que hay dÃas consecutivos que suman 21 !
Lo del máximo de 12 problemas por semana también es algo arbitrario ¿verdad? Se podrÃa ajustar algo más todavÃa permitiendo hasta un máximo de 13 por semana. Pero no 14 por semana, porque entonces 14*3 = 42 y ya no funciona. En estas condiciones, un caso en el que no habrÃa suma 21 serÃa si se hace un número constante de 2 al dÃa... y al ser el 2 par, nunca sumarÃan 21.
Incluso creo que podrÃan relajarse algo más las normas sin obligar a un máximo por semana, sino más bien un máximo de 41 cada 3 semanas.
Pensaba que otra condición serÃa un máximo diario de 20 (ó 21 pero considerando que vale 1 dÃa como "dÃas consecutivos") pero si debe haber al menos uno diario y un máximo de 41, no puede haber un dÃa con 22 porque si no el total serÃa 42 o más.
Si alguna suma es divisible por 21 ya está y si no habrá una parejita cuyo "módulo 21" sea igual, pero entre esos dÃas no puede haber 42 ejercicios (el máximo es 41), asà que debe haber 21 acertijos entre esos dÃas.
En general,
si tienes una secuencia de N números, tales que cada uno de ellos es mayor o igual a 1 y su suma es menos de 2*N-1
habrá una secuencia de números consecutivos cuya suma sea N
Oh! Me dejan boquiabierta! Al parecer, la solución propuesta por Yole es correcta, y por supuesto, no es la que yo pensaba, aunque las ideas son las mismas (yo usé 11 semanas en el enunciado del problema... y 11 semanas en resolverlo!).
Las "palomas" de Yole son los 21 números sx, todos distintos. Y sus "palomares" son las clases de congruencia módulo 21, sabiendo que el "palomar" 0 (cero) está vacÃo. Quedan 20 palomares para ubicar 21 palomas. Entonces: hay dos en el mismo.
En cuanto a las objeciones de ACid... le creo.
En la solución que yo pensaba, el dato del máximo de 12 por semana, se usa sólo para decir que en total no resuelve más de 11*12=132 problemas. Entonces, si relajamos la condición del máximo por semana, y sólo se sabe que no hace más de 132... cómo se demostrarÃa?
QUIERO MÃS ACERTIJOS!!
NO PUEDO PARAR!
Nooo, fotos no! Autógrafos más tarde!
Ahora que ya parece tan obvio, -aplausos para Acid, klatx, klatx, klatx- gracias a esta última generalización veo que era tarea imposible abordar esta cuestión en las dimensiones planteadas.
El "secreto" era reducirlo a su caso más crÃtico, como ha hecho Acid. Bastan 21 dÃas y que en total no haga más de 41.
Asà que si he aprendido bien, el acertijero de Lorena siempre resuelve 77 acertijos en un perÃodo determinado puesto que 12*7=84 es menor que 77*2-1=153.
Entonces, (igual me estoy pasando) se puede extender el razonamiento y decir que siempre habrá un perÃodo de dÃa/s en el que resuelva cualquier número entero de acertijos entre 1 y 77. Si me equivoco en algo corregÃdme rápido, por piedad!
Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 Perdón, perdón, perdón...
Me falló sólo la aritmética. En dónde puse 12*7 < 153 quise decir 12*11=132 < 153
y ahora falló el soporte técnico, que me cortó la frase
Me falló sólo la aritmética. En dónde puse 12*7 quise poner 12*11 = 132, que sigue siendo menor que 153.
Mantengo el resto del razonamiento
¿Sabéis éste? Le dice JuanPablo a Markelo: OÃ, ayer me comà 15 palomas! Responde mkl, ¿mensajeras? y JP, ¡no, que vá, no exagero nada!
Pequeña introducción guasona ;P a lo que querÃa decir: Si le damos un giro colombófilo al enunciado serÃa como tener 77 jaulas en fila en cada una de las cuales meto al menos una paloma, disponiendo, como máximo, de 153 ratitas voladoras.
Siempre habrÃa un número de jaulas con 77 palomas, pero también con 76, 75, ..., 3, 2, 1.
Profesor Acid, su veredicto?
Yo he conseguido una demostración que se parece en principio a la de disinerge, pero no habÃa ningún dato que fuera de adormo.
Me lo miraré con más detenimiento y os lo cuento.
David, que dice Santiago que gracias por los simbolitos.
Yo la verdad me perdà en las 11 semanas. Me gusto mucho la demostración de Yole y cada pichón en su cajón.
HabÃa puesto "Y se cumple 38+51+38 = 77-1 + 51 = 127 &132" pero no me acordé de que el sÃmbolo & se lo traga y hay que poner &
Más cosas: Igual que el contraejemplo que he puesto con el 50, se podrÃan hacer otros contraejemplos con números desde 39 (= 76/2 + 1) hasta 55 (= 132-76-1)
Para números entre 56 y 66 o menores que 39 no podrÃa yo asegurar ni una cosa ni la otra.
Otro caso de contrajemplo serÃa dividiendo el total de dÃas en tres, en lugar de dos. Cada intervalo relleno de unos serÃa de 77/3 = 25 dÃas y habrÃa dos dÃas de atracones. Si N=26, el atracón serÃa de 27 problemas en un dÃa y en total son 25+27+25+27+25 = 75 + 54 = 129
Para N=27, en total son 75 + 56 = 131
(y para N mayor que 27 la suma es mayor que 132)
Otro caso de contrajemplo podrÃa ser dividiendo el total de dÃas en cuatro. Cada intervalo relleno de unos serÃa de 77/4 = 19 dÃas y habrÃa tres dÃas de atracones (el último intervalo de unos no estarÃa completo: 17, no 19). Si N=20, el atracón serÃa de 21 problemas en un dÃa y en total son 19+21+19+21+19+21+17 = 137 !! Asà que este caso no es válido.
Volviendo al caso de 21 dÃas (3 semanas) si no indicamos un máximo de 12 por semana sino 36 en total en las 3 semanas, aseguramos, ademas de N=21 otros casos: N=20 (2*20-1 = 39), N=19 (2*19-1 = 37)
Y para 7 dÃas, con un máximo de 12, aseguramos N=7 y N=6
(pero no 5 ni 4, contraejemplo: [1,1,1,6,1,1,1])
Quise decir:
HabÃa puesto "Y se cumple 38+51+38 = 77-1 + 51 = 127 < 132" pero no me acordé de que el sÃmbolo < se lo traga y hay que poner <
He leÃdo por ahà de congruencias y "módulos" y estoy seguro de perderme algo pero quizá sea posible traducirlo a un lenguaje más popular.
Es lo que estoy intentando con la brillante observación de las sumas de Yole. Solamente me falta entender bien porqué si ninguna de las sumas sk (todas distintas como dice Lorena) es igual al N buscado (21 para nosotros) habrá NECESARIAMENTE una diferencia entre sumas igual al número buscado.
Lo he comprobado para números pequeños y se vé claro pero no soy capaz de gneralizarlo.
Acid, tienes razón o_o, pero utilizando tu propia argumentación no entiendo porqué lo justificas hasta el 66. Quizás hayas mezclado datos, no sé. Porque si el dÃa del atracón hace 77 acertijos, que es el máximo que permiten las normas, sólo se pueden conseguir números hasta 38 además del propio 77 (que aparece siempre).
Esto me lleva a un postulado más "prudente": Dadas N jaulas no vacÃas y un máximo de 2N-1 palomas, siempre se podrán encontrar un número de palomas consecutivas igual a N y a cualquier entero menor que N/2.
De todos modos lo que yo hago no es una demostración sino aprovechar la tesis de las sumas congruentes, créermela y redactar corolarios.
En realidad con la demostración de Yole, las aclaraciones de Santiago y las observaciones de Acid no queda mucho que decir.
Enhorabuena, Lorena.
Sin hablar de módulos, congruencias, etc... en un lenguaje más popular ya lo dijo Yole:
"el resto al dividir por" 21
Llamemos a esta función "Resto" (aunque en matemáticas se le suele llamar módulo y los números con igual módulo se agrupan en relaciones de equivalencia o relaciones de "congruencia"):
Resto(x,21) = resto de dividir x por 21
(es un número que puede valer de 0 a 20)
Y ahora veamos un sencillo problema.
Tenemos dos enteros positivos sk y sl, tales que sk>sl y tales que Resto(sk,21) = Resto(sk,21) = 3
pero sk 132
(67*2 - 1 = 133) y si no se cumple eso, faltarÃa una de las condiciones de mi enunciado general:
"su suma es menos de 2*N-1"
El lÃmite no es N/2 como propones. Para N = 77, N/2 = 38.5
Y el contraejemplo del 50 no es válido para N=39 ni para N=40 .... hasta 55.
El lÃmite del que hablo yo es un lÃmite inferior de tal forma que todos los números mayores sà que lo cumplen.
Pero tu pareces hablar de N/2 como lÃmite superior de forma que todos los números menores inferiores a N/2 también lo cumplirÃan.
Con mi enunciado no se puede asegurar nada sobre eso. (Ni tampoco he sacado conclusiones fuera de los lÃmites de ese enunciado)
Se me olvidó otra vez transformar el <
Quise decir:
"Y ahora veamos un sencillo problema.
Tenemos dos enteros positivos sk y sl, tales que sk>sl y tales que Resto(sk,21) = Resto(sk,21) = 3
pero sk < 42"
Disinerge:
a y b son congruentes módulo m si tienen el mismo resto en la división por m, es decir: si a=q1*m+r, y b=q2*m+r, con 0 r ponés el número a si el resto de dividir a por 21 es r. Todo número podrá ponerse en una y sólo una caja.
Ahora, suponiendo que la caja con la etiqueta 0 está vacÃa, y teniendo que ubicar los 21 números sx en las 20 cajas restantes... necesariamente dos de esos números deberán estar en la misma caja. Es decir, tienen el mismo resto al dividirse por 21... y su diferencia es divisible por 21.
Ups... en el preview se veian los signos "menor que".
A ver si me sale esta vez:
a y b son congruentes módulo m si tienen el mismo resto en la división por m, es decir: si a=q1*m+r, y b=q2*m+r, con 0 < = r < m
Veo que a todos se nos "chispotea" el signo menor o mayor. Creo que se podrÃa agregar el dato de cómo hacer que aparezca < y > en un update del problema
Otra vuelta de tuerca
Hasta ahora, para 77 dÃas con la única condición de un total máximo de 132 acertijos, se asegura que hay secuencias que suman 77,76,... 67
respectivamente.
Pues bien, con las condiciones más estrictas originales (12 máximo por semana), aplicando el enunciado general para 1 semana, 2 semanas... he llegado a que hay secuencias que suman cualquier número menor que 78 exceptuando algunos sobre los que no puedo asegurar nada. Los números sobre los que no puedo asegurar nada son estos: 36, 30,29, 24,23,22, 18,17,16,15, 12,11,10,9,8, 6,5,4,3,2,1
(pero sobre números pequeños como el 2 y el 1 sà es fácil asegurar que lo cumplen. Para el 1 porque debe haber algún 1 en la secuencia y para el 2 porque si no hay ningún 2, debe haber 2 unos seguidos ya que separando los unos con treses se supera el lÃmite)
Gracias Lorena, Markelo! Creo que ahora algunos se habrán convencido de que no estaba loco cuando escribà lo de las palomas...
(Y Yole... no me creÃste que lo habÃa resuelto!!)
De paso, creo que Alejo y Acid entendieron por dónde iba lo de la paridad, que también se puede usar con 11 semanas, y sin que sea para despistar: como cada semana tiene dos dÃas con una sola paloma, hay al menos 22 cambios de paridad en la suma de problemas resueltos en los dÃas previos, y entre un cambio de paridad y otro no se pueden agregar más de 10 problemas (esto sirve para que entre 2 dÃas que cambian la paridad -ya sea por 1's o por otros números-, no pueda haber más de 21 problemas resueltos).
Otro enfoque era ir haciendo las sumas hasta cada dÃa, el primer dÃa hice x problemas, hasta el segundo y, hasta el tercero z... y cuando llego al final, hice A problemas. Ahora bien, hay una sucesión de la forma r, r + 21, r + 42... (otra vez el palomar: ubicar los restos de los 77 números módulo 21, en la jaula que le corresponde a ese resto) en alguna caen al menos A/21 números (si en cada una hubiese menos, en total sumarÃan menos de A...), con lo cual al menos una sucesión está entera, y de un dÃa al otro en ella están los 21 problemas resueltos (esto dice de otra manera que hay más de una solución)
agh. escribà para el @ρτ0 esto último, es 77/21, con lo cual puede haber 14 secuencias que tienen 4 números (si alguna tiene 5 o más, es más fácil), y al menos una empieza con 14 o mas, y si esos 4 números no tuviesen al menos 2 consecutivos, habrÃa al menos 7 elementos en la secuencia, con lo cual el último numero serÃa 6x21+14, mayor que 132.
(a veces es más fácil escribir la cuenta que las ideas...)
Gracias a todos y en especial a Lorena por este problema absolutamente novedoso para mÃ. Aunque todavÃa me falta hincarle el diente de verdad para dominarlo ya puedo decir que he despejado las dudas técnicas.
Asà que la clave era demostrar que dentro de una secuencia de N números naturales distintos de cero siempre hay una igual a N y eso, efectivamente se consigue con el recurso "técnico" del resto. Que por supuesto, sólo nos vale en el caso de que La suma de los N términos sea menor que 2N.
Acid, si revisas lo que dije verás que cambié intencionadamente los datos (no respeté los de Lorena, disculpad) ya que hice un ejemplo menos restrictivo con 153 palomas en 77 jaulas (en vez de 132, la condición inicial y eliminando también que en 7 no pueda haber más de 12). Sólo seguà tus indicaciones. Está claro que 77 es una suma presente y también como tú observas con acierto, que se pueden distribuir poniendo el máximo en la jaula central y una sóla en los laterales.
Lo que digo es que quizás (ni mucho menos lo he demostrado) también se encuentren el resto de secuencias entre 1 y el entero inferior a N/2, que es 38 en este caso. Da igual tener un número impar o par de jaulas, redondeas hacia abajo y ya está.
Se me ocurre apretar un poco más tu tuerca. Esto no vale para nuestro ejercicio por ser el tiempo lineal (bueno, eso es lo que yo percibo ;-)) pero con las jaulas si que valdrÃa: Se trata de ponerlas "en cÃrculo", de modo que la primera y la última también estén conectadas. En ese caso, creo, si aparecerÃan todas las sumas enteras entre 1 y N.
¿O no?
Disinerge: Si ninguna de las 21 sumas deja resto cero al dividir entre 21 (es decir, si ninguna es 21, y como todas son distintas, algún resto se tiene que repetir.
disinerge, este tipo de resultados se prueban más o menos bien usando la teorÃa de Ramsey, te recomiendo este pdf como introducción:
http://www.uam.es/personal_pdi/ciencias/gallardo/ramsey.pdf
(en especial, saltá a la página 6, para hacerte una idea de los resultados, y después leelo en detalle)
Un poco de "cholulismo":
Vamos, chicos, vamos! Un poquito más y mi problema entra entre los 10 post más comentados!
De paso, alguien puede explicar qué es "cholulismo" a la gente no argentina?... a mi no me sale una buena definición.
Juan Pablo,
No me convence tu razonamiento sobre los cambios de paridad...
Supongamos este caso:
(1,1,2,2,2,2,2, 2,2,2,2,2,1,1, 1,1,1,1,1,1,6)
La sucesión de sumas (problemas resueltos hasta hoy):
(1,2,4,6,8,10,12, 14,16,18,20,22,23,24, 25,26, )
dices "entre un cambio de paridad y otro no se pueden agregar más de 10 problemas" pero en este caso entre el 2 y el 22 hay 20, hay más de 10 problemas...
Ahà puede haber una errata pero de todas formas si lo que pretendes decir es que la suma igual a 21 debe estar comprendida entre dÃas que cambian la paridad, creo que no es cierto:
1122222 1122222 1122222
1(122222 112222)2 1122222
Si el inicio de la secuencia (de suma 21) empieza en el primer cambio de paridad, el final cae en un momento que no hay cambio de paridad.
Y si el final cae en un cambio de paridad, entonces es el principio de la secuencia el que no coincide con ese cambio.
Quizá no entendà bien lo que querÃas decir.
¿"cholulismo"?
No tengo ni idea qué es eso. He buscado en google pero solo vi frases donde aparece la palabra...
¿serÃa algo asà como "tirarse flores a uno mismo"? ¿o "presumir tontamente"? (no se si me habré acercado al significado porque no tengo ni idea)
Ah... y gracias Lorena. Debo confesar que esto salió mucho mejor de lo que yo esperaba.
Vaya...
Un par de dÃas sin atender el sitio y ahora me tengo que leer ¡60! comentarios para entender de que están hablando :-)
Dando una mirada rápida, parece que todos están de acuerdo en que el problema ha sido resuelto. Hasta Lorena y el profesor Juan Pablo han dado su bendición.
Felicitaciones pues.
Voy a leerlos con tranquilidad y espero entender algo (no se olviden que mi formación es más acertijera que matemática). Parece que tengo material para divertirme largo rato. Gracias a todos por participar... y por compartir.
Gracias santiago, por fin lo interioricé. A veces no encuentro las palabras mágicas para traducir un concepto matemático y le doy más vueltas de las necesarias.
JP, justo ese enlace ya lo habÃa visitado pero Ramsey se me atraganta un poco. Seguro que algún poso de ciencia me ha dejado en la corteza neuronal. Gracias.
Apasionante post, me ha puesto en órbita.
perdón Acid, tenés razón, quise decir 20. El tema es que al ir saltando, no me 'pase' en más de 21. Y claro, no necesariamente la suma está comprendida ahà adentro, hay que jugar de vuelta con que uno tiene 22 números, entonces alguno se repite 'modulo 21', y lo bueno es que en las puntas de estos cambios de paridad tenés unos.
Por ahà es más enquilombada que la otra versión, mirando todas las sumas parciales, o que la de Yole.
De paso, habÃa otro camino que no exploré mucho: en los 77 dÃas hay 57 bloques de 21 dÃas consecutivos. Si quiero que ninguno de ellos cumpla, con agregar un problema en cada bloque logro 'anularlos'... pero como máximo sólo puedo agregar 55 problemas, con lo cual hay al menos dos tiras de 21 dÃas que comparten un problema como crÃtico para que no pueda resolver 21 en esos dÃas (o 3 tiras que comparten 2, o 4 que comparten 3... hay un lÃmite para ésto dado que en cada semana sólo se pueden agregar 5 problemas)
No se bien como llegar al resultado de esa manera, pero estoy seguro que de ahà viene el planteamiento con 11 semanas (con 10, tendrÃa 50 bloques de 21 y 50 problemas para agregar, puedo evitar que haya tiras de 21 dÃas con 21 problemas (y tal vez salga una versión más fuerte: hay 21 dÃas consecutivos en los que resolvà 21 problemas). La 'paloma sobrecargada', lo llamarÃa a este argumento, por la similitud en ajedrez cuando una pieza tiene que defender dos amenazas.
Falta ya tan poco que voy a postear para que leguemos al "top ten", que Lorena se lo merece.
Me ha espabilado un poco la necesidad de averiguar porqué el enunciado dice lo que dice. Para mà es claro que los contornos no están delimitados "al ras" y que perfectamente se podrÃa postular "demuestra que hay un perÃodo en el que resuelve 77" sin cambiar ningún dato del planteamiento de Lorena.
Voy más allá: razonar para 21 requiere una etapa más de razonamiento que hacerlo para 77 ya que hay que comprobar previamente que la sucesión (21) es menor que la mitad de los dÃas (77/2=38,5).
Con la teorÃa de los restos (tan sobada ya) demostramos de modo genérico que en una serie de N números enteros distintos de cero cuya suma es menor o igual a 2N-1 siempre habrá una serie (o suma si queremos llamarla asÃ) igual a N.
Y yo añado que también igual a 1,2,3,...int(N/2), pero sin demostrarlo. Me estoy repitiendo pero es lo que deduzco después de "digerir" a Ramsey.
LORENA..
EN PRUEBA DE...
DECLARO ESTE POST MIEMBRO DE LOS MAS COMENTADOS
MI ADMIRACION...
Oh!, gracias, gracias! Me siento muy emocionada...
De paso: cholulismo: arte de querer acercarse a la gente de fama (merecida) para contagiarse (inmerecidamente) un poco de esa fama. Se aplica principalmente a la fama farandulesca. El cholulo se siente feliz cuando roza la fama de esa forma.
Mis felicitaciones Lorena por tu impresionante post! (valga la redundancia con los comments anteriores) máxime sabiendo que todos los comments son "racionales", equivocados o no, y no gansadas como el del abecedario que ocupa inmerecidamente el primer lugar.
PD. con este comment quedás adelante del de Anagramando nombres, Cazabobos XX y Cazabobos XVIII. Te hice ganar tres posiciones!
Extiendo las felicitaciones a todos. Sin ustedes, este post no estarÃa donde está! (aún arriba de números en serie).
Reconozco que quedé sorprendida al ver todo lo que daba este problema. Son unos monstruos! (para que no haya malentendidos, "monstruos" en Argentina se usa para calificar a algo de impresionante, grandioso)
Aqui también se dice lo de monstruos en ese sentido. La palabra "cholulo" no se usa por aquà pero te puedo asegurar que de esos hay a montones :(
(sobre todo saliendo en la tele, la presa rosa, etc.)
¡Qué bonito problema!
La verdad es que me gusta mucho cuando se postean problemas matemáticos, y por lo que puedo ver por el número de comentarios que reciben, gozan de mucha popularidad. Este principio de las palomas yo lo ubicaba como principio de los casilleros, y, de hecho, sospeché desde un principio que era el que habÃa que aplicar acá, aunque no llegué a darme cuenta de que se aplicaba con los restos de las sumas acumuladas de la secuencia.
Encuentro una lástima haber llegado tarde para participar en la solución del problema, ya que los de este tipo son los que más disfruto. ¿No has pensado en poner tu propia página, Lorena, dedicada a problemas de olimpiadas matemáticas (sin con esto pretender quitar público a Markelo, por supuesto)?
che... eso de Homero está muy bien...
Durante un tiempo, hubo un blog en Mendoza con info de las OlimpÃadas (aunque sin problemas), pero se cerró.
Yo me ofrezco a participar, ya sea en el armado o lo que venga.
Realmente, no me animo a armar una página. Lo que se podrÃa hacer, es proponer a Markelo más problemas de este tipo. Creo que tiene una audiencia adecuada. Y/o proponerle que abra una sección de problemas de olimpiadas.
Yo disfruto tanto de ver cómo entre todos se descuartiza un problema!
mmmmmmmm.....
Eso de descuartizar problemas... suena como salvaje, Lorena. Mejor desmenuzar, que suena como a pollo
Se ha lanzado una interesante propuesta de un nuevo blog o, al menos, de una nueva categorÃa de acertijos.
Lamentablemente debo desilusionarlos y decirles que no podré satisfacer sus deseos. Basicamente por dos motivos:
1) No soy la persona indicada. Ya comenté por allà que mi formación es más acertijera que matemática y realmente, este tipo de problemas no se me dan muy bien.
2) El objetivo de Pequeños Enigmas es simplemente ser una "puerta de entrada" al gusto por los acertijos. La idea es que aquà encuentren acertijos fáciles y divertidos que puedan ser resueltos por todos de forma tal que se entusiasmen y descubran que hay todo un mundo acertijero allà afuera donde ejercitar las neuronas.
PreferirÃa no elevar demasiado el nivel de los problemas, aunque no me parece mal proponer uno más complejo de vez en cuando.
Si alguno de ustedes (o algunos, que podrÃan ser varios los autores) se decide a abrir su propio blog, cuente con mi apoyo, moral, publicitario y técnico (en lo que pueda)
Y no teman quitarme lectores... Si de este grupo surgiera un nuevo proyecto y todos decidieran ir allà en busca de nuevos desafÃos, me pondrÃa muy feliz de saber que Pequeños Enigmas ha cumplido uno de sus objetivos... Y yo volverÃa a empezar a la "caza" de nuevos acertijeros.
Markelo. Tenés que evitar de usar la frase "puerta de entrada". Se te van a venir todos los que joden en el boogle 4x4 preguntado por el código Da Vinci y como merde abrir las puertas...:)
No, no! a este post no!!!
Eso, contribuyamos al caos:
"pdf del código da vinci"
"pdf del codigo da vinsi" (porque hay cada búsqueda...)
"puerta de entrada a dan brown"
"claves para las puertas de entrada"
acabo de sumarte lectores, markelo... de nada ;)
Como abro la primera puerta?. Es chiste, es chiste!! No te asustes Lorena!!
Hola me gustaria pedirles un faBor muy grande,ya que en ninguna pagina lo puedo encontrar, nesesito que me digan mi nombre en chino es YOLE
me gustaria mucho q me contestaran.muxas grasias por todo.
:(
Ya no vale el número 84 para medir el éxito de este post... (y empatamos a peligro de gol!)
que sean 85. Lorena, las bromas y conversaciones off-topic son parte sana de los comentarios, creo yo, y no demeritan a los demás. Es más, si hay una disgresión aquà es porque la gente se asoma a ver qué más se ha dicho.
Markelo, por cierto, me parece excelente tu puerta de entrada, que ha sido clave para que me vuelva a poner a descifrar códigos :P (ya no digo como qué pintor me siento a veces porque ya ha de ser obvio y no quiero hacer enojar a nadie (:P de nuevo))
lorena puedo sumar uno más (o uno y medio, por la "carga" transportada).
santiago, no sumes tanto que me estás por desbancar.
markelo, quién es el bengador hanónimo? (fuera de tópico, pero soy asÃ)
Asi que son todos graciosos eh?
Ya sabés Juan pablo. si en tu blog empiezan aparecer coments invitando a ver fotos de conocida modelo local, ligera de ropas... yo no fui.
Por ahora los dejo... pero al primer mensaje extraño... los borro a todos (y lo lamento por Lorena :-)
Pini: ¡ Bien vuelta !
El vengador anónimo prefiere mantener el anonimato y no voy a ser yo quien le ande deschavando la IP... aunque te puedo decir que es alguien a quien conocés bastante.
Te debo decir Markelo que nunca pense que me iban a gustar tanto los acertijos. En serio yo solo estaba buscando entretenerme una noche muy aburridora hace como un año cuando encontre esta pagina en google. Me pase toda la noche leyendo los acertijos porque solo tenias como 4 o 5 meses de existencia. Y no se como fui que me acorde el nombre del weblog pero me dio por volver y me gusto muchisimo mas. Como escribistes arriba, Pequeños Enigmas fue la puerta de entrada, me entretuvo, y veame ahorra adicto a esta pagina. Entonces te doy las gracias por haberme introducido al mundo acertijero y por mantenernos a todos tan entretenidos todo este tiempo.
Solo me dio por escribir algo porque con este acertijo no supe ni por donde empezar. Y pues porque ahorra se ha convertido en un post especial tambien felicito a Lorena.
Y hablando un poco mas off-topic, me parece muy bacano como al pasar el tiempo ha crecido tanto la cantidad de gente que comentan aca. Me acuerdo cuando casi siempre comentabamos las mismas personas, pero ahora hay muchos mas y muchos mas comentarios que para mi se hace mucho mas intersante para leer y disfrutar. Aunque yo quiesiera comentar mucho mas como lo hacia antes, pero empeze la universidad y el tiempo libre a veces es muy poco. Pero me sigo entreteniendo bastante con solo leer lo que la gente dice. Bueno ahorra ya no escribo mas aunque espero que siga creciando hasta pasar el abesedario chino. Y perdon Markelo por el comentario tan largo.
Apenas pasaron 48 Hs y ya tuve que borrar el primer comentario.
La broma dio resultado y es bueno descubrir que Google me indexa rápidamente... pero honestamente, no tengo ganas de andar lidiando con gente ignorante y desubicada (ya bastante trabajo me da "boogle 4x4")
Voy a experimentar "tachando" las frases comprometedoras a ver si google capta la semántica. Pero si no... me temo que tendré que borrar los comentarios de los bromistas :-(
Markelo, mi recomendacÃon es que cierres los posts problemáticos a los comentarios, con la explicación del caso. Es lo que se me ocurrió hacer en un post mÃo y funcionó bien, creo que lo voy a hacer en otros.
Solo tengo dos:
Abecedario: Que ya se ha convertido en un Ãcono cultural y no podrÃa borrarlo ni cortarlo
Boogle 4x4: El cual me dedico a borrar prolijamente. No lo clausuro porque tengo curiosidad de ver hasta donde llega la moda del dichoso libro ese.
Singing, como se prepara la polbora vlanca?. (como verás Markelo, estoy tomando las precauciones del caso, igual tenés todo mi apoyo para borrar este mensaje y los que lo preceden) ;)))
Markelo, recorda que el acertijero del problema se estuvo entrenando por 11 semanas, está listo y esperando el segundo torneo!
markelo gracias por tu saludo.
yo quiero un concurso de cocina -no soy muy ducha para resolver acertijos-, y para buenas recetas, las de mi amigo singing.
pini! Yo quiero ir a comer a tu casa, sólo para que te entrenes, e incluso puedo hacer el sacrificio aunque no haya torneo! =)
Hablando de cocina, me dijeron que aquà se puede conseguir el libro de recetas de la hermana Bernarda.
¿Es verdad que también está el pdf del último / hultimo libro / livro de Harry Potter / Jarry / Jarri / Harri / Poter / Porter / Protter?
Ah! Gracias por enviarme los pdf de Bucay / Bucai y de Cohelo / Coelo / Cojelo ! DeberÃas poner un link asà todos los DESCARGA GRATIS! / FREE!
JuanPablo. Esto va a terminar mal, muuy mal...:)
Markelo andá mirando la tecla que está debajo del Insert...
pero por qué! si yo sólo trato de hacerle promoción a su weblog! y con temas de actualidad e interés, sin caer en los triple equis (nótese que no pongo las letras, para no dar falsos positivos)
Markelo, puedes hacer como el que se va (In god we trust). Aunque en su caso no me parece nada ético
Es que lo único que falta es que alguien (no yo) ponga palabras como programas gratis download antivirus tutorial mp3 CD software protector de pantallas archivos gif base de datos, etc.
Eso no se hace...
jaaaaaaa, markelo anda con el supr como yo.
pero de recetas acá ni mu.
(alejo sÃ, dije mu como la vaca, o unos caramelos mumu que comÃa cuando era chica, y vos no conocés).
(jamás imaginé que estarÃamos tan cerca de las mandarinas)
Quisiera por favor que me envien a mi cuenta el ultimo tema de... pero...
oh! oh! recórcholis! si este es el post de mi problema! cómo me manda google aca a encontrar aca el último tema musical de NN?
Pini. Si me habré empachado con los caramelos mumu...
Y ni te cuento de los "media hora"
PQRT 11 amenaza con arrebatar el tercer puesto. Si Cihan Altay publica lo del P7, creo que no hay salvación...
yo te hago el aguante Lorena, de paso te devuelvo la cortesÃa... ;)
Oh, no, no es cortesÃa, es simplemente justo reconocimiento al mérito
lola tiene un puesto de frutas y verdura.
estamañana le han traido 2 cajas de manzana,
5 cajas de peras y 1 caja de melocotones.
¿cuántas cajas de peras y manzanas mas que de melocotones le an traido?
hola no se l afecha de publicacion pero la demostracion esta dada en el en enunciado todos como todos los dias al menos debe resolver un problema y tomamos el espacio tiempo como continuo es imposible que no haya una sucesion de dias consecutivos en los que se resuelvan 21 acertijos
Publicar un comentario