{"id":29,"date":"2017-07-08T16:14:11","date_gmt":"2017-07-08T16:14:11","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=29"},"modified":"2018-09-22T08:30:56","modified_gmt":"2018-09-22T08:30:56","slug":"coloreado-minimo-en-5-x-5-s","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2017\/07\/08\/coloreado-minimo-en-5-x-5-s\/","title":{"rendered":"Soluci\u00f3n a Coloreado m\u00ednimo en 5 x 5"},"content":{"rendered":"
Segundo nivel de la Olimpiada de Mayo 2016\r\n\r\nSe dirige a una edad de: 14\/15 a\u00f1os<\/pre>\n
\u00bfCu\u00e1ntas casillas se deben pintar como m\u00ednimo en un tablero 5 x 5 de tal modo que en cada fila, en cada columna y en cada cuadrado de 2 x 2 haya al menos una casilla pintada?<\/p>\n
\"\"<\/p>\n
La respuesta requiere que se d\u00e9 una coloraci\u00f3n de ejemplo, para mostrar que es posible y explicar de forma clara que es imposible encontrar una coloraci\u00f3n v\u00e1lida pintando menos casillas.<\/p>\n
<\/p>\n
Una de las estrategias para saber c\u00f3mo buscar es dividir el tablero en zonas como las que nos piden (filas, columnas, o cuadrados 2 x 2) para saber d\u00f3nde tenemos que pintar al menos una de las casillas.<\/p>\n
La forma m\u00e1s eficaz es combinar un poco todas las figuras: utilizar cuatro cuadrados 2×2, una fila y una columna. De esta forma, encontramos varias divisiones, y nos centramos en una de ellas para tratar de encontrar una coloraci\u00f3n.<\/p>\n
\"\"<\/p>\n
Si tenemos en cuenta esta divisi\u00f3n, podemos pensar que hacen falta como m\u00ednimo colorear cinco casillas, una por cada cuadrado y una para pintar una casilla tanto de la fila como de la columna. Sin embargo, veremos que eso es imposible, porque para usar cinco casillas, ser\u00e1 necesario que la de la fila y la de la columna ocupe la casilla com\u00fan (gris), dejando el resto de la fila y de la columna vac\u00eda.<\/p>\n
Pero como s\u00f3lo queremos colorear cinco casillas, debe haber una en cada fila y una en cada columna, por lo que en los cuadrados de tama\u00f1o 2 s\u00f3lo una casilla de cada fila debe estar ocupada, y si en uno de los cuadrados de la parte superior (verde y azul) no hay ninguna casilla coloreada de la fila superior, se puede formar un cuadrado 2×2 con estos dos cuadrados de arriba y los dos de la fila superior (amarilla), que s\u00f3lo tiene coloreada la casilla com\u00fan. Y en ese cuadrado no habr\u00eda ninguna casilla coloreada.<\/p>\n
Como hemos visto, no puede colorearse usando s\u00f3lo cinco casillas. Y esto nos da una pista de cu\u00e1les son las que tenemos que colorear para nuestro ejemplo con 6. En los cuadrados, no repetir fila ni columna, y en la fila y la columna que est\u00e1 vac\u00eda procurar que no se pueda dejar un cuadrado de tama\u00f1o 2.<\/p>\n
\"\"<\/p>\n
Se puede ver que ning\u00fan cuadrado 2×2 queda sin al menos una casilla pintada, y que tambi\u00e9n est\u00e1n cubiertas las cinco filas y las cinco columnas.<\/p>\n
As\u00ed que la respuesta es que como m\u00ednimo es necesario pintar 6 casillas.<\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Segundo nivel de la Olimpiada de Mayo 2016 Se dirige a una edad de: 14\/15 a\u00f1os \u00bfCu\u00e1ntas casillas se deben pintar como m\u00ednimo en un tablero 5 x 5 de tal modo que en cada fila, en cada columna y en cada cuadrado de 2 x 2 haya al menos una casilla pintada? La respuesta […]<\/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-29","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\/29","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=29"}],"version-history":[{"count":2,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/29\/revisions"}],"predecessor-version":[{"id":33,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/29\/revisions\/33"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}