sábado, 27 de julio de 2013

Páginas de un libro

Enunciado

Hay una forma de solucionar el problema muy sencilla, aunque algo larga de llevar a cabo.

La idea es sumar los números empezando por el 1 (1 + 2 = 3, 1 + 2 + 3 = 6, ...), obteniendo los llamados números triangulares, hasta llegar a sobrepasar el 2013. El exceso desde 2013 será el número de página que nos hemos dejado.

A partir de aquí, para estudiar si hay más soluciones, probar si al añadir alguna página más podemos llegar a otro valor que pudiésemos alcanzar también con una única página, aunque es claro que no, ya que a un valor mayor que 2013 le añadiremos el número de la última página del libro, y el resultado, por tanto, guardará una distancia con 2013 más grande que el número de la última página del libro.

Pero sumar hasta 2013 no es una tarea fácil, para abreviarla, podemos usar un truco muy sencillo, ya que sumar 1 + 2 + 3 + 4 + .... + 15, por ejemplo, es igual que sumar 15 + 14 + 13 + ... + 1, y si emparejamos los sumandos, todos dan 16 (1 + 15, 2 + 14, 3 + 13, etc). Eso significa que sumar 1 + 2 + 3 + 4 + .... + 15 es lo mismo que multiplicar 16*15 y dividirlo por 2, ya que lo estaremos sumando dos veces.

Es decir, que podemos hacer una fórmula para sumar los n primeros números con una multiplicación y una división, n*(n + 1)/2. Así podremos sumar más rápidamente, o empezar tanteando números altos, como 40 o 60, y sumando a partir de ahí

Incluso, si hemos estudiado ya ecuaciones de segundo grado, observamos que si queremos que n*(n + 1)/2 = 2013 (en realidad, queremos que sea mayor, lo que pasará para valores aún más grandes de n), tenemos que n*(n + 1) = 4026, por lo que n2 + n - 4026 = 0, y de aquí tendremos que n debe valer, con la fórmula de la ecuación de segundo grado, (-1 + √(1 + 4*4026))/2 = (-1 + √(1 + 16104))/2 = (-1 + √(16105))/2. Calcular la raíz exacta es complicado, pero estaría por encima de 120, por lo que el valor de n sería superior a 61.

Tanteando, obtenemos que 61*62/2 = 1891, 62*63/2 = 1953, 63*64/2 = 2016, de forma que el número de páginas sumadas será 63, y la página que se ha dejado es la tercera, ya que ha obtenido una cifra tres unidades menor.

Evidentemente, si tuviese una página más, la suma debería dar 2080, y no es posible que Sofía obtenga 2013 olvidando una única página, ya que hay una diferencia de 67 y la página mayor tiene el 65.

Como siempre, la solución de Pablo Sussi es correcta, aunque comenta que el libro debería tener un número par de páginas. Tal vez la última estaba sin numerar, pero era más importante que la suma coincidiese con el año en que se hace la pregunta que el resultado sea tan meditado.

domingo, 21 de julio de 2013

Saludos en el patio

Enunciado

Debido al trabajo, he ido retrasando la publicación en el blog. Espero que vuelva la regularidad.

Este problema ha causado un gran debate en la web, a pesar de que la explicación de Pablo Sussi ha sido casi perfecta.

Voy a añadir un pequeño dibujo que aclare los saludos.

Dos personas sólo se deben saludar una vez, así que si contamos los saludos en los que participa cada persona, deberemos dividir al final por dos, ya que cada saludo lo habremos contado dos veces.

Otra alternativa es contar saludo a saludo según su dirección, en cuyo caso contaremos los saludos hacia la izquierda y no hacia la derecha, y hacia delante y no hacia atrás, para evitar contar dos veces cada saludo.

En el dibujo, hemos pintado de dos colores los saludos, para distinguir unos de otros. Observa que, visto de esa forma sólo se cuentan la mitad de los 8 saludos por persona, si se trata de una persona que está totalmente rodeada.

De esta forma, podemos contar los saludos de dos formas, contando todos los que da cada persona, o clasificándolos por tipos.

Si los contamos por persona, deberemos finalmente dividir entre dos, pues cada saludo se habrá contado dos veces.

De esta manera, como se afirmaba en los comentarios, tendremos cuatro personas, en las esquinas, que sólo saludan a tres, todas las de los laterales que no ocupan las esquinas, que saludan a 5, y las centrales, que saludan a ocho.

Como las de los laterales serán dos filas de 8 y dos de 5, serán un total de 26 personas, y las centrales serán 40, por lo que el número de saludos así contados será de 40*8 + 26*5 + 4*3 = 320 + 130 + 12 = 462. Como hemos dicho, en realidad estamos contando cada saludo dos veces, por lo que en realidad serán 231 los saludos que se harán.

Si contamos los saludos por tipo, vamos a contar sólo los que están pintados de color azul en el dibujo. Así, los saludos que se dan hacia arriba los podrán hacer todos los alumnos excepto los de la fila superior, es decir, 63. De la misma forma, los saludos en diagonal hacia arriba y la derecha los podrán hacer todos menos los de la fila superior y la columna lateral, que son un total de 54. El saludo lateral hacia la derecha lo podrán hacer 60 personas del cuadro y el diagonal hacia abajo y la derecha otras 54 personas. En total, cuento 63 + 54 + 60 + 54 = 231. Observa que en esta ocasión no se divide entre dos, pues evitamos contar saludos repetidos.

La fórmula que obtenemos de generalizar el proceso se puede observar que es esencialmente la misma.

En el primer caso, tenemos [4*3 + 2*(n - 2)*5 + 2*(m - 2)*5 + (n - 2)*(m - 2)*8]/2, contando por un lado los saludos de las cuatro esquinas, los de la las dos columnas (observa que le restamos dos individuos a los extremos, que son los de las esquinas), los de las dos columnas (igualmente), y los centrales, que será un rectángulo en el que quitaremos los bordes. Al final, hemos de dividir entre dos.

Simplificar esta fórmula se hace quitando paréntesis, de forma que queda: [12 + 10n - 20 + 10m - 20 + 8*(nm -2m - 2n + 4)]/2 = [8mn + 10m -16m + 10n - 16n + 12 - 20 - 20 + 32]/2 = [8mn -6m -6n + 4]/2 = 4mn - 3m - 3n + 2, que en el caso de substituir m por 7 y n por 10 da, en efecto, 231.

A raíz de un comentario, hay que recalcar que la fórmula sólo es válida cuando n y m son mayores que 1, ya que en caso contrario no hay cuatro esquinas, y la fórmula deja de ser teóricamente válida.

Si decidimos contar sólo los saludos por su tipo, como hemos hecho en el segundo caso, conseguimos la fórmula siguiente: n*(m - 1) + (n - 1)*m + (n - 1)*(m - 1) + (n - 1)*(m - 1), ya que serían los cuatro tipos de saludo "azules". Desarrollando, tenemos que es igual a nm - n + nm - m + nm - n - m + 1 + nm - n - m + 1 = 4mn - 3m - 3n + 2.

La validez de esta fórmula es mayor, ya que puede darse el caso de que m o n (o ambos) valga uno sin que pierda sentido.

Observa que la simplificación ocasiona la misma fórmula.