jueves, 9 de octubre de 2008

Olimpiada Matemática

Enunciado

Vamos a tratar de representar y estudiar un caso concreto y probaremos después a ampliarlo y, si es necesario, generalizarlo.

Ejemplo

Ejemplo

El caso mínimo que cumple todas las condiciones, salvo la cantidad de apretones de manos, sería el que tiene siete filas y tres asientos en cada fila, 21 participantes en total. Para contar los apretones (ver imagen) habrá que tener en cuenta que los cuatro participantes de las esquinas sólo dan la mano a tres participantes (líneas azules), los que están situados en los lados, que en este caso son 12, dan la mano a 5 participantes cada uno (líneas rojas), y que los que se sientan en uno de los asientos restantes, 5 en este caso, dan la mano a 8 (lineas verdes).

En total, podríamos decir que si sumamos las manos tendidas que dan todos los participantes, tendríamos 4*3 + 12*5 + 5*8 = 12 + 60 + 40 = 112 manos. Sin embargo, hay un pequeño detalle que hay que tener en cuenta, y es que en cada apretón de manos intervienen dos personas, de forma que sólo se dan 56 apretones, en realidad.

Este cálculo está muy lejos de los 1020 de los que nos habla el problema, así que con toda probabilidad hay más filas, o columnas, o ambas cosas.

Supongamos que añadimos una columna de asientos (es decir, una más en cada fila). Si la añadimos al final o al principio, habrá cambios en la cantidad de manos tendidas que tendrá que ofrecer la gente que ya estaba situada, de forma que la añadiremos entre la primera y la segunda columna, es decir, que añadiremos 2 asientos de primera y última fila y 5 de los asientos interiores, es decir, 2*5 + 5*8 = 50 manos tendidas, o 25 apretones más. Cada columna que añadamos aporta, por tanto, 25 apretones de manos, con lo que nunca llegaríamos a 1020 (56 + n*25 nunca puede ser 1020 para ningún n, como es fácil comprobar).

Si aumentamos el número de filas de la cantidad inicial, sólo podemos hacerlo de 7 en 7, es decir, que añadiríamos 14 asientos de principio o final de fila y 7 interiores (de nuevo se supone que no las añadimos al final o al principio, para simplificar los cálculos). En total, serían 14*5 + 7*8 = 126 manos tendidas, o 63 apretones. En total, tendríamos ahora 119 apretones. Ahora, aumentando columna a columna, añadimos 2*5 + 12*8 = 106 manos, o 53 apretones. Por tanto, el número sería 119 + n*53, con n el número de columnas. Si planteamos 1020 = 119 + n*53, tenemos que n = (1020 - 119)/53 = 901/53 = 17. Es decir, que con 14 filas y 20 asientos por fila (columnas) tendríamos 1020 apretones.

¿Habrá más soluciones? Podemos aumentar el número de filas a 21, y eso añadirá 63 apretones más a la cantidad inicial, subiendo a 182. Además, cada columna que añadamos ahora pondrá 2*5 + 19*8 = 162 manos, de forma que la fórmula sería 182 + n*81, de donde n tendría que ser (1020 - 182)/81, que no es entero.

Aumentando a 28, tendríamos una fórmula igual a 245 + n*109, y de nuevo n no sale entero. Es sencillo calcular a partir de ahora, ya que la siguiente sería, para 35, 308 + n*137, y de nuevo no da entero.

Y, claro, te habrás dado cuenta de que la fórmula para las filas k*7, sería (63*k - 7) + n*(28*k - 3), donde k es el resultado de dividir las filas entre 7, y n el número de columnas que pasa de 3.

Para 35, sería 371 + n*165, por lo que tendría que dar entero (1020 - 371)/165, que no lo es (es algo inferior a 4).

Para 42, sería 434 + n*193, y (1020 - 434)/193 da casi 3, pero no es exacto.

Para 49, sería 497 + n*281, y (1020 - 497)/281 da por debajo de 2, pero no da entero.

Para 56, sería 560 + n*309, y (1020 - 560)/309 da bastante más de 1.

Para 63, sería 623 + n*337, y (1020 - 623)/337 da casi 1.

Para 70, sería 686 + n*365, y (1020 - 623)/365 da casi 1.

Para 77, sería 749 + n*393, y (1020 - 749)/393 da por debajo de 0.

La única posibilidad que queda es que n fuese 0, es decir, que se alcanzase 1020 sólo sumando filas, pero entonces 56 + m*63 = 1020 para algún valor de m, y por eso 1020 - 56 sería divisible por 63, pero no puede ser porque ni siquiera es divisible por 3.

También es posible hacer un razonamiento sobre la fórmula general basado en divisibilidad, pero es complejo y al final debemos también dar ciertos valores. No se me ocurre un método más directo. Este tipo de ecuaciones, llamadas Diofánticas, requieren métodos parecidos al que hemos visto para su solución.

Así pues, la única solución es la que hemos encontrado, con 14 filas y 20 asientos por fila.

No hay comentarios: