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.

No hay comentarios: