viernes, 28 de septiembre de 2012
Problema del día. Combinatoria (28 de Septiembre)
En una Olimpiada de Matemáticas los concursantes están ocupando todos
los asientos de un salón rectangular donde los asientos están alineados
en filas y columnas de tal manera que hay más de dos filas y en cada
fila hay más de dos asientos. Al inicio del examen un profesor les
sugiere que se deseen suerte dándose la mano; cada uno de los
concursantes estrecha la mano de los concursantes que están junto a él
(adelante, atrás, a los lados y en diagonal) y sólo a éstos. Alguien
observa que se dieron 1020 apretones de manos ¿Cuántos concursantes hay?
Suscribirse a:
Comentarios de la entrada (Atom)
Separamos en $3$ "casos" para contar los saludos:
ResponderBorrar$\bullet$ No orilla:
$*$ Saludos por persona: $8$
$*$ Pesonas: $(f-2)(c-2) = fc-2(f+c)+4$
$*$ Saludos: $8 \times fc-2(f+c)+4 = 8fc-16(f+c)+32$
$\bullet$ Orilla pero no esquina:
$*$ Saludos por persona: $5$
$*$ Personas: $2((f-2)+(c-2)) = 2(f+c)-8$
$*$ Saludos: $5 \times 2(f+c)-8 = 10(f+c)-40$
$\bullet$ Esquina:
$*$ Saludos por persona: $3$
$*$ Personas: $4$
$*$ Saludos: $3 \times 4 = 12$
Saludos Totales: $8fc-6(f+c)+4$
Pero estamos contando dos veces cada saludos, asi que dividimos entre $2$ :
$4fc-3(f+c)+2=1020$
$4fc-3(f+c)=1018$
$4fc-3f-3c=1018$
$4fc-3c=1018+3f$
$c(4f-3)=1018+3f$
Entonces $1018+3f$ es un multiplo de $4f-3$ :
$1018+3f \equiv 0 \pmod 4f-3$
Restamos $4f-3$:
$1018-f+3 \equiv 0 \pmod 4f-3$
$1021-f \equiv 0 \pmod 4f-3$
Para poder quitar la $f$ , multiplicamos por $4$ :
$4084-4f \equiv 0 \pmod 4f-3$
Sumamos $4f-3$ :
$4084-3 \equiv 0 \pmod 4f-3$
$4081 \equiv 0 \pmod 4f-3$
Entonces: $4f-3 \mid 4081$
Sabemos que $4081=7*11*53$ .
Entonces los valores $4f-3$ pueden ser:
$*1 \quad *7 \quad *11 \quad *53$
$*77 \quad *371 \quad *583 \quad *4081$
Y los posibles valores de $4f$ son:
$*4 \quad *10 \quad *14 \quad *56$
$*80 \quad *374 \quad *586 \quad *4084$
Ya que $f$ es entero, $4f$ debe ser múltiplo de $4$ , entonces eliminamos algunos casos:
$*4 \quad *56 \quad *80 \quad *4084$
Con esos casos, $f = \cdots$ :
$*1 \quad *14 /quad *20 \quad *1021$
Sabemos que $f>2$ asi que $f \neq 1$ .
Teniamos esto:
$4fc-3(f+c)=1018$
Y lo usamos para obtener $c$ :
$\bullet f=14$
$4(14)c-3(14+c)=1018$
$56c-42-3c=1018$
$53c=1060$
$c=20$
$\bullet f=14$
$4(20)c-3(20+c)=1018$
$80c-60-3c=1018$
$77c=1078$
$c=14$
$\bullet f=1021$
$4(1021)c-3(1021+c)=1018$
$4084c-3063-3c=1018$
$4081c=4081$
$c=1$
Sabemos que $c>2$ asi que $c \neq 1$ .
$\Rightarrow$ Nos quedan $2$ casos:
$\bullet f=14 , c=20$
$\bullet f=20 , c=14$
Y obviamente en ambos casos el producto es el mismo; $280$ .
$\therefore$ Hay $280$ concursantes.
$\text{No son muchas personas en un salon para un examen?}$
:) ... y no, simplemente ha de ser un salón lo suficientemente grande n_n
Borrar$\text{Pero si es un salon muy grande} \Rightarrow \text{Se pueden copiar o hacer trampa los que estan hasta atras} \cdots$
BorrarDepende de donde esten los ojos
Borrarlo dividimos en casos que son los que estan en esquinas, en orillas y en medio
ResponderBorrarcaso 1 esquinas
tienes que los 4 que estan en las esquinas saludan alos 2 de sus lados y al de la diagonal y poreso tienes que saluda a 3 personas pero son 4 por lo tanto hay 12 saludos
caso 2
tienes que ellos saludan a 3 de los lados y 2 de las diagonales que son cinco saludos y tienes que saludos son $5((2)(x-2)+(2)(y-2))=10(x+y)-40$ donde $x$ y $y$ son los lados del rectangulo que forman los alumnos
caso 3
tienes que ellos si saludan a todos por lo tanto dan 8 saludos y tienes que son $(x-2)(y-2)=xy-2(x+y)+4$ y eso por $8$ que sereia $8(xy-2(x+y)+4=8xy-16(x+y)+32$
y tienes que en total se dieron $8xy-6(x+y)+4$ pero estamos contando 2 veces los saludos por lo tanto se divide entre 2 y nos queda $4xy-3(x+y)+2=1020$ y tenemos que $4xy-3x-3y=1018$ por lo tanto $4xy-3y=1018+3x=y(4x-3) por lo tanto 1018+3x es multiplo de 4x-3
y hasta ahi llevo
Bueno, eso esta bien jeje ... pero termina el resto n_n
Borrarhttp://www.facebook.com/photo.php?fbid=395465403857593&set=a.384382948299172.87730.100001824112299&type=1&theater
ResponderBorrarPues lo que llevas esta bien, lo último no se si sirve de algo... que te quede 1/2 en la ecuación, quizas es más util ver que 4 divide a 3(k+l)-2 todo junto que separarlo.
Borraryo lo unico qu levo es esto :
ResponderBorrarprimero me fije en el caso de un rectangulo de $2*n$ me fijo que el de la esquina superior izquierda solo puede agarrar 3 luego el que esta a su derecha solo puede saludar 4(estoy contando a los que ya no puede saludar) y asi hasta el ultimo que solo puede agarrar 2 pero nos fijamos que a los de la fila de abajo ya los abran saludado todas sus opciones etnonces me fijo que una sola fila de k elementos solo va a dar $3+(k-2)4+2 =4k-5$ saludos entonces si tomamos un rectangulo de $k*n$ podriamos agarrar todas las filas excepto la ultima como si fueran la primer fila de un rectangulo de $2*k$ y utilizando la formula de arriba con lo que acabamos de desir la cantidad total de saludos seria $(4k-5)(n-1)=4kn-4k-5n+5$ entonces ya nomas seri busacr numero $k,n$ que cumplieran que $4kn-4k-5n+5=1020$
Mmm interesante... esta bien lo que llevas, pero te falló poquito en el álgebra... resulta que los saludos por renglón son 4k-3 (lo anterior esta bien asi que intuyo que solo fueron las cuentitas) ... y al ultimo te falta sumar los saludos de las personas en el ultimo renglon, osea las que se dan entre solamente ellos... corrigiendo estos detallitos ya puedes proseguir :)
Borrar$\text{Nos fijamos en tres casos:}$
ResponderBorrar$\bullet\text{Caso 1: personas en las esquinas}$
$\text{Cada una de las }4{ personas saluda a otras }3$
$\text{Total: }12$
$\bullet\text{Caso 2: personas en las orillas}$
$\text{Cada una de las } 2((n-2)+(m-2))\text{ saluda a otras }5$
$\text{Total: }10(n+m-4)$
$\bullet\text{Caso 3: personas en la parte de enmedio}$
$\text{Cada una de las } (n-2)(m-2)\text{ saluda a otras }8$
$\text{Total: }8((n-2)(m-2))$
\text{(Donde }m,n\text{ son las dimensiones del salon.)}
$\text{El total nos queda como }12+10(n+m-4)+8((n-2)(m-2))$
$\text{pero estamos contando cada saludo dos veces, por lo cual el total es:}
$\frac{1}{2}(12+10(n+m-4)+8(n-2)(m-2))$
$=6+5(n+m-4)+4((n-2)(m-2))$
$=6+5(m+n)-20+4mn-8(m+n)+16$
$=4mn-3(m+n)+2=1020$
$\Rightarrow 4mn-3(m+n)=1018$
$\Rightarrow m(4n-3)=1018+3n$
$\Rightarrow 4n-3|1018+3n,\; m|1018+3n$
$\text{Vemos que }1018+3n\equiv 1 \mod{3}$
$\Rightarrow m\equiv 4n-3\equiv 1,2\mod{3}$
$\text{Hasta aqui he llegado, despues sigo intentandolo.}$
:S ... pues esta bien hasta donde pude entenderle... que es donde dice El total nos queda blablabla... de ahi en adelante no entiendo nadaaaa jaja
BorrarSeparo a las personas por la cantidad de personas que van a saludar.
ResponderBorrarCaso 1: Personas de las esquinas
Hay 4 personas en total y cada una de ellas saludara a otras 3. Entonces las personas de las esquinas dan $12$ saludos en total.
Caso 2: Personas de las orillas
Supongamos que es un rectangulo de $n*k$. Entonces habra $2(n-2)+2(k-2)$ personas en las orillas sin contar a los de las esquinas. Estas personas saludaran a 5 mas. Entonces los de las orillas dan $5*2(n-2)+5*2(k-2)=10(n-2)+10(k-2)=10(n+k)-40$
Caso 3: Personas del centro
Estas personas saludaran a 8 cada uno. Como son $(n-2)(k-2)$ personas, habra $8(n-2)(k-2)$ saludos. Esto es igual a $8nk-16n-16k+32$ saludos.
Sumamos todos los saludos y nos debe de dar 2040 saludos porque contamos cada uno 2 veces
Entonces $8nk-16n-16k+32+10n+10k-40+12=2040$
$8nk-6n-6k+4=2040$
$4nk-3n-3k=1018$
$4nk-3n=1018+3k$
$n(4k-3)=1018+3k$
Y hasta ahi es a donde he llegado.
Bueno, pues hasta ahí esta bien xD
BorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarVeamos que las personas de las esquinas solo saludan a 3 personas, las personas en los lados (que no estan en las esquinas) saludan a 5 personas y el resto saluda a 8 personas, ahora vemos los saludos en función de las dimensiones del rectángulo (las dimensiones del rectángulo son las personas que estan en cada lado del salon) Sean $n$ y $m$ las dimensiones del rectángulo:
ResponderBorrarPersonas en las esquinas.- Siempre serán 4, cada una saluda a 3 personas, aquí tenemos:
$4(3)=12 \text{saludos}$
Personas en los lados.- Serán 2(n+m) a lo cual le restamos la gente en las esquinas, cada uno saluda a 5 personas por lo que son:
$5(2(n+m)-4)=5(2n+2m-4)=10n+10m-20 \text{saludos}$
Resto de las personas.- Serán (n-2)(m-2) personas, cada una saluda a 8 personas que estan a su alrededor, por lo que serán:
$8(n-2)(m-2)=8(nm-2m-2n+4)=8mn-16m-16n+32 \text{saludos}$
Sumamos todo y lo dividimos entre 2, pues un saludo lo estamos contando 2 veces, de aquí que:
$\frac{12+10n+10m-20+8mn-16m-16n+32}{2}=\frac{24+8mn-6m-6n}{2}=1020\Rightarrow 24+8mn-6m-6n=2040\Rightarrow 16mn-12m-12n=4032$
Se tiene que:
$(4m-3)(4n-3)=16mn-12m-12n+9\Rightarrow 4041=(3-4m)(3-4n)$
La factorización en primos de 4041 es: $4041=3^{2}(449)$ por lo que los productos que nos dan 4041 son:
$1*4041, 3*1347, 9*449$
Caso 1.- $SPDG 4m-3=1, 4n-3=4041\Rightarrow m=1$ lo cual es una contradicción pues hay al menos 2 filas y 2 columnas.
Caso 2.- $SPDG 4m-3=3\Rightarrow 4m=6$ lo cual es una contradicción pues m no sería entero.
Caso 3.- $SPDG 4m-3=9 , 4n-3=449 \Rightarrow 4m=12\Rightarrow \boxed{m=3} , 4n=452\Rightarrow \boxed{n=113}\therefore\text{son:}$
$\boxed{3(113)=339 \text{concursantes}}$
mmm pues mira... la idea esta muy bien!! peeero jaja .. mmm .. lamento informarte que tienes un error como muy al principio...
Borrarmira, en el segundo caso tienes que son 2(n+m)-4 personas en las orillas (sin contar esquinas) ... pero la verdad ahí si estas contando esquinas, si te fijas estas contando doble las esquinas al sumar 2(n+m) por lo cual debes restar 8 y no solo 4.
Corrigiendo esto, las ideas para terminar de resolverlo son mas o menos iguales n_n
Sean n y m las dimensiones del salon rectangular, me fijo que los saludos los puedo contar en 3 casos
ResponderBorrarCaso 1: los saludos que dan las personas que estan en las esquinas son 3 cada una y por las 4 esquinas en este caso hay 12 saludos.
Caso 2: LAS personas de las orillas saludan a 5 personas cada una y veo que estas personaas son 2n+2m-4-4=2n+2m-8=2(n+m-4) y el total de saludos son 10(n+m-4).
Caso 3: las personas que estan en el centro todas saludan a 8 personas y me fijo que este numero de personas son: (n-2)(m-2) entonces los saludos en este caso son 8(n-2)(m-2).
Entonces el total de saludos son $\frac{12+10(n+m-4)+8((n-2)(m-2))}{2}$ el entre dos es porque estamos contando los saludos dos veces mas entonces 4((n-2)(m-2))+5(n+m-4)+6=1020=4nm-8m-8n+16+5n+5m-20+6.
Entonces 4nm-3m-3n=1018.
Hasta ahora eso es lo q llevo, tambien he intentado dividir el rectangulo en cuadriculas de 3x3 y dejar los asientos sobrantes, y me fijo que en cada cuadricula de 3x3 hay 20 saludos y que al dividir el rectangulo las dimensiones me quedan (3k+x) y (3j+y) con (3k+x) y (3j+y)=m y n. Entonces viendo nomas la cuadricula de 3k*3j es facil contar los saludos que hay en ella y ya con ello aproximarme a los valores de m y n.
Ok, pues esta bien lo que llevas, falta terminarlo... no se si esa idea funcione pero puede servir, sigue tratando n_n
BorrarRumbo al nacional
ResponderBorrarLa expresión está bien, y ya de ahí puedes trabajar con ella para intentar sacar los valores.
BorrarPero a pesar de que esta bien a lo que llegaste, tienes que explicar que el patrón se va a cumplir siempre, si solo es porque se ve pues no es una demostración jeje n_n
Hacemos la cantidad de filas $x$, y a la de columnas $y$. Vemos que los 4 de las esquinas saludan cada uno a 3, los $2(x-2+y-2)$ de cada orilla (sin contar las esquinas) saludan a 5 y los $(x-2)(y-2)$ que están en medio saludan a 8, entonces su suma es $3(4)+5(2(x+y-4))+8(x-2)(y-2)=12+10x+10y-40+8xy-16y-16x+32=8xy-6x-6y+4=2(1020)=2040$ porque contamos dos veces cada saludo.
ResponderBorrarEntonces $8xy-2040+4=6(x+y)$ $\Rightarrow 4xy-1018=3(x+y)$
$\Rightarrow 4xy \equiv 1018 (\pmod{3})$ $\Rightarrow xy \equiv 1 (\pmod{3})$.
Entonces $xy=3k+1$ (lo que buscamos es el valor de xy), además $xy>255$ porque $4xy-1018$ es positivo.
Aquí ya no sé cómo terminar...
Bueno, esta bien todo lo que llevas, quizas podrías encontrar una cota superior o utilizar otros modulos n_n
Borraruse un método raro y lo hice como entendí :s no se si este mal
ResponderBorrarSON 5 hojas, que traen poquito cada una
http://www.facebook.com/photo.php?fbid=4695062578773&set=a.4586100454788.189149.1360331970&type=1&theater
http://www.facebook.com/photo.php?fbid=4695062978783&set=a.4586100454788.189149.1360331970&type=1&theater
http://www.facebook.com/photo.php?fbid=4695063698801&set=a.4586100454788.189149.1360331970&type=1&theater
http://www.facebook.com/photo.php?fbid=4695065978858&set=a.4586100454788.189149.1360331970&type=1&theater
http://www.facebook.com/photo.php?fbid=4695067098886&set=a.4586100454788.189149.1360331970&type=1&theater
en el problema 5 deje un comentario para si puedes leerlo :l y saber si mi idea es la correcta o no
A ver, como que medio entiendo la idea pero no estoy segura.. entiendo que partes de un caso pequeño y manejable y vas haciendo más grande el rectangulo, vas encontrando un patrón... no lo he hecho.. pero pudiera servir... sin embargo no te vas a ir haciendo como 1000 casos para llegar a la respuesta... la idea es que si ya encontraste un patrón puedes sacar una forma general y tratar de demostrarlo, lo cual seguramente se debe poder hacer con inducción.
BorrarGracias, ya corregí mi solución:
ResponderBorrarVeamos que las personas de las esquinas solo saludan a 3 personas, las personas en los lados (que no están en las esquinas) saludan a 5 personas y el resto saluda a 8 personas, ahora vemos los saludos en función de las dimensiones del rectángulo (las dimensiones del rectángulo son las personas que están en cada lado del salón) Sean $n$ y $m$ las dimensiones del rectángulo:
Personas en las esquinas.- Siempre serán 4, cada una saluda a 3 personas, aquí tenemos:
$4(3)=12 \text{saludos}$
Personas en los lados.- Serán 2(n+m) a lo cual le restamos la gente en las esquinas 2 veces pues las estamos contando al doble ya que pertenecen tanto a $m$ como a $n$, cada uno saluda a 5 personas por lo que son:
$5(2(n+m)-8)=5(2n+2m-8)=10n+10m-40 \text{saludos}$
Resto de las personas.- Serán (n-2)(m-2) personas, cada una saluda a 8 personas que estan a su alrededor, por lo que serán:
$8(n-2)(m-2)=8(nm-2m-2n+4)=8mn-16m-16n+32 \text{saludos}$
Sumamos todo y lo dividimos entre 2, pues un saludo lo estamos contando 2 veces, de aquí que:
$\frac{12+10n+10m-40+8mn-16m-16n+32}{2}=\frac{4+8mn-6m-6n}{2}=1020\Rightarrow 4+8mn-6m-6n=2040\Rightarrow 16mn-12m-12n=4072$
Se tiene que:
$(4m-3)(4n-3)=16mn-12m-12n+9\Rightarrow 4081=(3-4m)(3-4n)$
La factorización en primos de 4081 es: $4081=7*11*53$ por lo que los productos que nos dan 4041 son:
$1*4081, 7*583, 53*77$
Caso 1.- $SPDG 4m-3=1, 4n-3=4081\Rightarrow m=1$ lo cual es una contradicción pues hay almenos 2 filas y 2 columnas.
Caso 2.- $SPDG 4m-3=7\Rightarrow 4m=10$ lo cual es una contradicción pues m no sería entero.
Caso 3.- $SPDG 4m-3=53 , 4n-3=77 \Rightarrow 4m=56\Rightarrow \boxed{m=14} , 4n=80\Rightarrow \boxed{n=20}\therefore\text{son:}$
$\boxed{14(20)=280 \text{concursantes}}$
Pues falta el caso de 11*371 pero pues basicamente esta terminado... pero igual.. en un examen puede ser importante ese caso jeje ... :)
Borrar