{"id":742,"date":"2018-09-15T06:57:34","date_gmt":"2018-09-15T06:57:34","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=742"},"modified":"2018-09-15T06:57:34","modified_gmt":"2018-09-15T06:57:34","slug":"solucion-a-los-mayores-de-los-16","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2018\/09\/15\/solucion-a-los-mayores-de-los-16\/","title":{"rendered":"Soluci\u00f3n a los mayores de los 16"},"content":{"rendered":"
Problema 2 del segundo nivel de la Olimpiada de Mayo (2018)\r\nSe dirige a una edad de: 14 a\u00f1os<\/pre>\n
En un tablero 4×4 est\u00e1n escritos los n\u00fameros del 1 al 16, uno en cada casilla.<\/p>\n
Andr\u00e9s y Pablo eligen cuatro n\u00fameros cada uno.<\/p>\n
Andr\u00e9s elige el mayor de cada fila, y Pablo el mayor de cada columna.<\/p>\n
Un mismo n\u00famero puede ser elegido por ambos.<\/p>\n
Luego, se eliminan del tablero todos los n\u00fameros elegidos.<\/p>\n
\u00bfCu\u00e1l es el mayor valor que puede tener la suma de todos los n\u00fameros que quedan en el tablero?\"\"
\n
\nSi pensamos en lo que se nos propone, es lo mismo intentar que la suma de los que quedan sea lo mayor posible, que intentar que la suma de los que quitas sea lo menor posible, as\u00ed que vamos a abordarlo por ese lado.<\/p>\n
Veamos primero un ejemplo, distribuyendo al azar los 16 n\u00fameros y viendo lo que sucede.
\n\"\"
\nEst\u00e1 claro que alguno de los n\u00fameros que ambos marcar\u00e1n ser\u00e1 el 16, y por lo tanto no elegir\u00e1n 8 n\u00fameros, si no a lo sumo 7.<\/p>\n
Uno de los dos elegir\u00e1 el 15, ya que aunque est\u00e9 en la misma fila que el 16, no puede estar tambi\u00e9n en la misma columna, por lo que el 15 ser\u00e1 elegido. Ser\u00eda buena idea que lo eligiesen los dos, ya que evitamos que elijan uno de los otros valores. Ahora bien, el 14 y el 13, si elegimos bien su posici\u00f3n (misma fila y columna que el 15 y el 16, podremos evitar que sean escogidos. De nuevo, es inevitable que el 12 lo escojamos, por lo que podemos tratar de que lo elijan ambos, y eso puede tapar una buena cantidad de n\u00fameros (11, 10, 9 y 8). De nuevo, el 7 lo elegiremos (mejor si son los dos), y as\u00ed tenemos la cantidad m\u00e1s baja posible, que ser\u00eda 16 + 15 + 12 + 7 = 50.<\/p>\n
Un ejemplo de esa tabla ser\u00eda la siguiente distribuci\u00f3n de n\u00fameros, lograda alterando un poco el ejemplo anterior.
\n\"\"
\nAhora, hay que ver que nuestra intuici\u00f3n funciona, y que no hay una distribuci\u00f3n mejor.<\/p>\n
La clave es que, si suponemos que tenemos seleccionados los n\u00fameros que marcan los dos amigos de nuestro problema, podemos determinar el tama\u00f1o m\u00ednimo de los cuatro n\u00fameros m\u00e1s grandes, y ya s\u00f3lo esos deben sumar m\u00e1s de 50.<\/p>\n
Veamos. El mayor, claramente, es el 16. El segundo mayor es el 15, ya que o bien no est\u00e1 en la misma fila o en la misma columna que el 16.<\/p>\n
Despu\u00e9s, el tercero no puede estar en los dos cuadrados que est\u00e1n en la misma fila y columna en la que est\u00e1n el 15 y el 16. Hay 16 \u2013 4 = 12 n\u00fameros fuera de esta condici\u00f3n, y claramente el mayor de todos ser\u00e1 elegido, por uno o por otro, y ser\u00e1 mayor o igual que 12.<\/p>\n
A\u00f1adir\u00e1 otra fila u otra columna, en la que no se podr\u00e1 elegir ninguno. En el peor caso, quedar\u00e1 una fila o una columna en la que estar\u00e1 el cuarto, que no ser\u00e1 ninguno de los dos anteriores. Por lo tanto, el mayor de esa fila o bien el mayor de la columna ser\u00e1 el m\u00e1s grande de los dos, y ser\u00e1 mayor que los 6 n\u00fameros restantes (los tres de su misma fila o columna, y los cuatro de la otra, aunque debe coincidir que un valor est\u00e1 en ambas), por lo que valdr\u00e1 al menos 7.<\/p>\n
Por lo tanto, los cuatro n\u00fameros mayores ser\u00e1n, con toda seguridad, mayores o iguales que 16, 15, 12 y 7, por lo que la suma total ser\u00e1 al menos tan grande como el valor que hemos calculado previamente, 50.<\/p>\n
Lo que pregunta el problema es cu\u00e1nto suman los que quedan, y como en total siempre sumar\u00e1 lo mismo, basta restarle 50, o sumar los n\u00fameros restantes.<\/p>\n
Para sumar los n\u00fameros del 1 al 16 (adem\u00e1s de usar la conocida f\u00f3rmula), podemos aplicar la estrategia de ir sumando por pares (1 + 16, 2 + 15, etc.) que nos da 8 pares que suman 17, luego la suma de los 16 ser\u00eda 17*8 = 136.<\/p>\n
Luego la suma de los que quedan ser\u00e1, en el caso mayor, 136 \u2013 50 = 86 (podemos comprobarlo en el segundo ejemplo propuesto).<\/p>\n
Para terminar, te dejo la encuesta para que eval\u00faes la dificultad del problema.
\n[polldaddy poll=10107872]<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 2 del segundo nivel de la Olimpiada de Mayo (2018) Se dirige a una edad de: 14 a\u00f1os En un tablero 4×4 est\u00e1n escritos los n\u00fameros del 1 al 16, uno en cada casilla. Andr\u00e9s y Pablo eligen cuatro n\u00fameros cada uno. Andr\u00e9s elige el mayor de cada fila, y Pablo el mayor de […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1738,2849,3303],"tags":[],"class_list":["post-742","post","type-post","status-publish","format-standard","hentry","category-olimpiadas","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/742","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/users\/4267"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/comments?post=742"}],"version-history":[{"count":2,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/742\/revisions"}],"predecessor-version":[{"id":746,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/742\/revisions\/746"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=742"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=742"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=742"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}