martes, 18 de septiembre de 2012
Problema del día. Teoría de Números (18 de septiembre).
En una fila para comprar boletos de cine se encuentran formadas $10,240$ personas. El caprichoso vendedor dice que va a atender uno no, uno sí, uno no, uno sí, etc. Los que no atienda deberán irse al final de la fila (uno por uno, en orden). ¿En qué lugar está formado al principio el último que va a poder comprar su boleto?
Suscribirse a:
Comentarios de la entrada (Atom)
si se numeran las personas segun su lugar en que estaban formadas veo que primero el vendedor atendera a todos los numeros pares, luego atendera al 3, al 7, al 11,...Luego me fijo que son todos los congrientes a 2+1 modulo $2^2$ luego despues de vederles a todos ellos, en la tercera vueltales vendera al 5, luego al 13, al 21,etc.. Esto es a todos los conggruentes a $2^2+1$ modulo 2^3$. Entonces me fijo que en la vuelta n, atendra a todos los congruentes con $2^{n-1}$ modulo $2^n$ Viendo eso como $10240=(2^11)(5) en la vuelta 12 solo quedaran 5 personas, entonces en la ultima vuelta quedaran los numeros que no tengan ninguna de las congruencias anteriores, entonces al ultimo como se van formando en orden estaran el 1,2049,4097,6145 y 8193, entonces me fijo que esos son los numeros congruentes a 1 modulo 2048. Entonces atendera al 1 no, al 2049 si, al 4097 no, y al 6145 si, al 8193 no, y al 1 si, al 4097 no y al 8193 si. Entonces el ultimo en la fila sera el 4097.
ResponderBorrarBueno yo numere a las personas conforme su posicion entonces vi que en la primera parte del problema nos dice primero no, si, no, si entonces comence a eliminar al los pares despues de eso tube del 1 al 10239 despues elimine los que sigen el 1 avanso y el 3 no a si susesivamente despues se borro el 10239 despues de eso me di cuanta de que la primera parte los numeros eran congruente a 1 modulo 2 y la segunda congruente a 1 mod 4 despues sigo a ver si no cambie ese 1 congruente despues note que no cambiaba entonces empese a demostrar que no iba a cambiar comense con los primeros pues para que el uno estuviera el anterior tenia que pasar entonces despues note que la diferencia era contraria a la congruencia 1 dicho el ultimo numero de la recta congruente a -1 mod n entonces pues 1 terminaria siendo el ultimo numero entrar ya que seria congruente a 1 mod n tal que otro no pudiese ser congruente a 1
ResponderBorrarsi bien es correcta tu argmento de la congruencia 1 mod n, no lo es tanto decir que es el unico que cumple eso. Finalmente te quedan otros numeros que cumplen la misma propiedad y que hacen precisamente que la respuesta no sea 1.
BorrarLo primero que hice fue buscar un patron. Lo que note fue que al principio son $10240$ personas separados por $2^0$. Cuando pasan el primer filtro, quedan $5120$ personas que tenian sus lugares originales separados por $2^1$. Tambien me fijo en que $10240=2^1^1*5$ Asi que la primer persona va a seguir quedando al principio hasta que solo queden $5$ personas. Despues de pasar ese filtro, quedan la primera, la tercera y la quinta persona pero como eran solo 5, la primera ahora si pasa y la quinta tambien. Por lo tanto la ultima persona en pasar sera la 3er persona del grupo final de $5$ donde la primera era $1$. Bueno, ahora estan $5120$ personas cuyos numeros estan separados por $2^1$. Al pasar el filtro de nuevo, quedan $2560$ separadas por $2^2$. Pasamos otro filtro y quedan $1280$ separados por $2^3$. Pasamos uno mas y quedan $640$ separados por $2^4$. Pasan otro filtro y quedan $320$ separadas por $2^5$. Otro mas y quedan $160$ separados por $2^6$. Otro mas y quedan $80$ separados por $2^7$. Pasan otro y quedan $40$ separados por $2^8$ Despues de otro filtro quedan $20$ separados por $2^9$. Pasan otro y quedan 10 separados por $2^1^0$. Despues de otro quedan $5$ separados por $2^1^1$. Podemos asegurar que el 1 sigue en frente porque siempre se ha estado formando en una posicion impar porque hasta el momento siempre habian quedado una cantidad par de personas. Ahora que solo quedan $5$ personas las llamaremos $A,B,C,D,E$ siendo $A=1$, $B=2^1^1+1$, $C=2*2^1^1$, $D=3*2^1^1$, y $E=4*2^1^1$. Como habia 10 personas formadas y se formaron detras de ellas, $A$ quedo en una posicion impar, por lo tanto aun no entra. En este filtro los unicos que entran son $B$ y $D$. Lo que ocurre cuando se forman es $A,B,C,D,E,A,C,E,C$ entonces se forman de nuevo $A$, $C$, y $E$. $A$ y $E$ se quedan en una posicion par porque como $A$ habia sido la primera en la formacion anterior, y habia una cantidad impar de personas, le toca formarse justo despues y $A$ entra junto con $E$ en el siguiente filtro. Para entonces ya solo queda $C$. Por lo tanto $C$ es la ultima persona y la posicion original de $C$ era $2*2^1^1+1$ que es igual a $2^1^2+1$ que es igual a $4097$
ResponderBorrar$\text{Nos fijamos en que cada ronda se va a eliminar a exactamente la mitad}$
ResponderBorrar$\text{de las personas que queden hasta el momento,}$
$\text{ya que } 10,240=5\times 2048=5\times 2^{11} \text{, lo cual va a suceder hasta la ronda 11.}$
$\text{Luego, van a pasar almenos 11 rondas antes de que pase la ultima persona.}$
$\text{Sabemos que, como despues de cada ronda, hasta la 11, va a quedar}$
$\text{un numero par de personas,todas las rondas van a empezar con NO.}$
$\bullet\text{Primera ronda: SI a todos los pares, quedan los impares.}$
$\text{Luego, quedan }5120$
$\bullet\text{Segunda ronda: SI a todos los numeros congruentes a }3\mod{4}$
$\text{Luego, quedan los }1\mod{4}\text{, o sea que quedan} 1280$
$\bullet\text{n-esima ronda ,}n\le 11 \text{: SI a todos los numeros congruentes a }2^{n-1}+1\mod{2^n}$
$\text{Quedan los }1\mod{2^n}\text{, o sea que quedan, en total:}$
$\frac{10,240}{2^n}=\frac{5\times 2^{11}}{2^n}=5\times 2^{11-n}$
$\bullet\text{Decimoprimera ronda: SI a todos los }1025\mod{2048}$
$\text{Quedan los }1\mod{2048}$
$\text{Despues de esta ronda solo quedaran 5 numeros:}$
$1,2049,4097,6145,8193\text{ en ese orden.}$
$\text{Luego, como terminamos en SI, se atendera a la } 2049\text{, y a la }6145$
$\text{Luego, como esta vez era un numero impar de personas, entonces terminamos}$
$\text{en NO, y ahora comenzaremos con SI, por lo cual se atendera a la}$
$1\text{, y a la }8193$
$\therefore\boxed{\text{La ultima persona habra estado en el lugar }4097\text{ en un principio.}}$
$\text{*Dato curioso: Ademas de ser la ultima persona, antes de ser atendida}$
$\text{sera rechazada siendo la unica en la fila.}$
:)
BorrarY así es. Aparte, algo no tan bonito como tu argumento, es que $4097\equiv 2 \pmod 7$ y $4097\equiv 2 \pmod 13$, siendo 7 y 13 dos números cabalísticos notables :)
Bye.
Nos fijamos que en la primer ronda, como se empieza con NO a los impares, Y como $10240 = 2^11 * 5$ Siempre se quitará exactamente la mitad de personas, hasta que sólo haya 5 al final.
ResponderBorrarTodos los pares serán atendidos, por lo cual los números congruentes con $0$ (mod) $2$
Luego empezará diciendo que NO, por lo cual atenderá al 3, 7, 11... Los cuales son congruentes a $3$ (mod) $4$
Empezará de nuevo diciendo NO, entonces se atenderá al 5, 13, 21...
Los cuales son congruentes a $5$ (mod) $8$
En general, tenemos un patrón determinado por el número de vuelta, tal que se pasan a los números dee persona que cumplen:
$2^{n-1}$ (mod) $2^n$
Por lo cual vemos todos los números que no pertenecerán a esas congruencias, que son:
$1 , 2049, 4097, 6145, 8193$ Que son los números finales que habiamos dicho en la proposición inicial.
Al 1 le diran que no, a 2049 que si, a 4097, que no, a 6145 que si, a 8193 que no. Luego a 1 que no, a 4097 que si, a 8193 que no , a 1 que si, a 8193 que no y luego que si.
Por lo cual, la persona formada en el lugar 8193 será la última en ser atendida.
Q.E.D.
:)
BorrarTe daré una carita feliz porque todo tu procedimiento fue correcto hasta el error del final, si cuando quedan solamente 5 personas, a la 5ta le dicen que no, entonces ya cuando vuelven a intercalar gente, al siguiente, es decir, al 1, le diran que si, al 4097 que no y al 8193 que si. Siendo la 4097 la ultima en ser atendida.
Saludos!
Lo primero que hice fue factorizar $10240$, $10240=2^11*5$ esto nos dice que vamos a poder dividir $11$ veces por dos al numero $10240$ y en esas $11$ veces siempre nos quedara la cantidad igual en ambas divisiones. Nos fijamos en los que no son escogidos hasta la division numero $11$:
ResponderBorrar$2n-1={1,3,5...10239}$
$4n-3={1,5,9...10237}$
$8n-7={1,9...10233}$
$16n-15={1,17,33...10225}$
$32n-31={1,33,65...10209}$
$64n-63={1,65,129...10177}$
$128-127={1,129,257...10113}$
$256n-255={1,257,513...9985}$
$512n-511={1,513,1025...9729}$
$1024n-1023={1,1025,2049...9217}$
$2048n-2047={1,2049,4097...8193}$
Hasta este punto tenemos $5$ valores: a $1$ le dice que no y $8193$ le dice que si
$1,2049,4097,6145,8193$
Luego quedaran formados: $1$ y a $8193$ les dice que si
$1,4097,8193$
Finalmente solo quedara
$4097$
:)
Borrarte falto poner el 6145 en tu ultimo renglon de operacioncitas... pero supondré que no lo pusiste por flojera :p
rumbo al nacional
ResponderBorrarprimero tengo que van a ser puros impares por lo tanto conguente con 1 mod 2 entonces si seguimos con lo que tenemos que hacer segun el caprichoso sabemos que quedan 3,7,11......10239conguentes a 3 mod 4, y si hacemos lo del caprichoso tenemos 7,15,23.....10239 conguentes a 7 mod 8 entonces vemos un patron que los numeros conguentes a
ResponderBorrarn-1 mod n
Tu idea inicial es correcta. Si la continúas estaría estupendo :p
BorrarNotamos que $10,240 = 2^{11}\times5$ .
ResponderBorrarYa que $10,240$ tiene $11$ factores $2$ , por $11$ rondas, va a empezar en NO, y acabar en SI. En la Ronda $12$ ya no se puede porque quedan cantidad impar de números.
En la Ronda $0$ , los números se pueden expresar asi:
$n \equiv 1 \pmod 2 , n \equiv 0 \pmod 2 , n \equiv 1 \pmod 2 , n \equiv 0 \pmod 2 , \cdots$
Eliminamos todos los $n \equiv 0 \pmod 2$ y quedan los $n \equiv 1 \pmod 2$ .
En la Ronda $1$ , los números se pueden expresar asi:
$n \equiv 1 \pmod 4 , n \equiv 3 \pmod 4 , n \equiv 1 \pmod 4 , n \equiv 3 \pmod 4 , \cdots$
Eliminamos todos los $n \equiv 3 \pmod 4$ y quedan los $n \equiv 1 \pmod 4$ .
Repitiendo este procedimiento, tenemos los valores para cada ronda:
$\bullet$ Ronda $1$ : $n \equiv 1 \pmod 2$
$\bullet$ Ronda $2$ : $n \equiv 1 \pmod 4$
$\bullet$ Ronda $3$ : $n \equiv 1 \pmod 8$
$\bullet$ Ronda $4$ : $n \equiv 1 \pmod {16}$
$\bullet$ Ronda $5$ : $n \equiv 1 \pmod {32}$
$\bullet$ Ronda $6$ : $n \equiv 1 \pmod {64}$
$\bullet$ Ronda $7$ : $n \equiv 1 \pmod {128}$
$\bullet$ Ronda $8$ : $n \equiv 1 \pmod {256}$
$\bullet$ Ronda $9$ : $n \equiv 1 \pmod {512}$
$\bullet$ Ronda $10$ : $n \equiv 1 \pmod {1024}$
$\bullet$ Ronda $11$ : $n \equiv 1 \pmod {2048}$
En la Ronda $11$ , los números que quedan son:
$1 , 2049 , 4097 , 6145 , 8193$
En la Ronda $12$ , los números que quedan son:
$1 , 4097 , 8193$
En la Ronda $12$ comezamos con SI y los números que quedan son:
$\boxed{4097}$
Como atiende uno no, uno sí, uno no, uno sí,... mientras haya una cantidad par va a atender al último de la fila (hasta antes de que vuelva a empezar).
ResponderBorrarPrimero va a atender a todos los pares y quedan los congruentes a 1 mod 2, que son los congruentes a 1,3 mod 4. Como al principio hay una cantidad par, atiende al 10240, luego se saltea al 1, atiende al 3, se salta al 5,... y atiende a todos los congruentes a 3 mod 4, quedan los congruentes a 1 mod 4 que son los congruentes a 1, 5 mod 8,...
Si hacemos una ronda hasta que vuelve a pasar alguien (por ejemplo el 1), vemos que las primeras 11 rondas va a haber una cantidad par de personas y en cada una va a atender a la mitad ($10240=2^{11}5$), y en cada ronda al inicio van a estar los congruentes a $1,2^{k-1}+1 \pmod{2^k}$ donde k es el número de la ronda, además como en la ronda k-1 había una cantidad par sabemos que va a atender al último de la fila y se va a saltear al 1, entonces atiende a todos los que tienen una congruencia $2^{k-1}+1 \pmod{2^k}$ y quedan los congruentes a $1 \pmod{2^k}$.
Después de la ronda 11 ya no se puede hacer lo mismo porque ya no hay una cantidad para (ya se dividió 10240 11 veces entre 2 que eran todas las veces que se podía), y quedan los congruentes a $1 \pmod{2^{11}}$ que son 1,2049,4097,6145,8193; se saltea al 1, atiende a 2049, se saltea a 4097, atiende a 6145, se saltea a 8193, atiende a 1, se saltea 4097, atiende a 8193 y queda solo 4097, entonces es el último al que atiende.
Se comienza en: uno "no", uno "sí", ..., etc., por lo que va quedando la mitad de la gente respecto a la "ronda" anterior, si $10240=2^{11}*5$ entonces tendremos cantidad par de personas hasta la ronda $11$ (incluyendo esa ronda completa). Notamos que siempre rechazan a quienes estén en posición impar, respecto a la ronda en la que están,de aquí que en la ronda $1$ no atienden a la gente en posición $p\equiv{1}\pmod{2^{1}}$, donde $p$ es la posición respecto al orden inicial.
ResponderBorrarEn la ronda $2$ quedan aquellos que satisfacen: $p\equiv{(1, 3)}\pmod{2^{2}}$, como aun queda cantidad par de personas, comenzamos en no y terminamos en sí, así que no se atienden a aquellos que estén en posición impar, de aquí que no se atienden a:
En la ronda $2$ a aquellos que satisfacen: $p\equiv{1}\pmod{2^{2}}$
En la ronda $3$ a aquellos que satisfacen: $p\equiv{1}\pmod{2^{3}}$
...
...
...
En la ronda $11$ a aquellos que satisfacen: $p\equiv{1}\pmod{2^{11}}$
Antes de comenzar la ronda $12$ los restantes son: $1, 2049, 4097, 6145, 8193$ aquí comenzamos en "no" y terminamos en "no" (ya que en la ronda anterior terminamos en "sí" y por haber cantidad impar de personas de termina también en "no"), por lo que antes de comenzar la ronda $13$ quedan las posiciones: $1, 4097, 8193$, esta ronda comienza en "sí" y termina en "sí" por lo que antes de empezar la ronda $14$ solo quedará: $4097$, no lo atienden y en la ronda $15$ lo atienden, siendo así el último en ser atendido.
http://www.facebook.com/photo.php?fbid=4649947730930&set=a.4586100454788.189149.1360331970&type=3&theater
ResponderBorrar:)
Borrarhttp://www.facebook.com/photo.php?fbid=392819470788853&set=a.384382948299172.87730.100001824112299&type=3&theater
ResponderBorrares facil ver que a los que no atienden en la pasada 1 son a los impares luego en la pasada dos son a los n con $n\equiv1 mod 4$ ya que se gvan quitando la mitad en cada pasada pero luego nos fijamos en que $10240=2^11*5$ y tambein nos fijamos en que en cada pasada el modulo que vamos a utilizar es por ejemplo en la pasada $n$ con $n\le11$ el modulo seria $mod2^n$ entonces cuando hagamos la pasada 11 dejaremos los que sean $\equiv1mod2^11$ y los unicos son $1,2049,4097,6145,8193$ entonces si hacemos las pasadas en este peqeño caso nos daremos cuenta que el ultimo sera el numero $4097$
ResponderBorrar:)
BorrarCarita feliz dudosa, pero sigue feliz :p
Prácticamente te saltas toda la talacha del final, pero ok.
http://s739.photobucket.com/albums/xx34/leo0_9506/Ommch/?action=view¤t=CAM000941_zps5b9b58ad.jpg
ResponderBorrar