{"id":824,"date":"2018-10-06T18:26:24","date_gmt":"2018-10-06T18:26:24","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=824"},"modified":"2018-10-11T20:09:05","modified_gmt":"2018-10-11T20:09:05","slug":"solucion-a-tableros-y-dominos","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2018\/10\/06\/solucion-a-tableros-y-dominos\/","title":{"rendered":"Soluci\u00f3n a tableros y domin\u00f3s"},"content":{"rendered":"
Problema 4 de la Olimpiada Matem\u00e1tica Femenina Europea (EGMO 2018)\r\nSe dirige a una edad de: 17 a\u00f1os<\/pre>\n
Un domin\u00f3 es una ficha de 1 x 2 o de 2 x 1 cuadrados unitarios.<\/p>\n
Sean n un entero mayor o igual que 3. Se ponen domin\u00f3s en un tablero de n x n casillas de tal manera que cada domin\u00f3 cubre exactamente dos casillas del tablero sin superponerse (en otras palabras, sin traslaparse).<\/p>\n
El valor de una fila o columna es el n\u00famero de domin\u00f3s que cubren al menos una casilla de esta fila o columna.<\/p>\n
Una configuraci\u00f3n de domin\u00f3s se llama balanceada si existe alg\u00fan entero k mayor o igual que 1 tal que cada fila y cada columna tiene valor k.<\/p>\n
Demuestre que existe una configuraci\u00f3n balanceada para cada n mayor o igual que 3, y encuentre el m\u00ednimo n\u00famero de domin\u00f3s necesarios para una tal configuraci\u00f3n.
\n\"\"
\nSoluci\u00f3n:
\n
\nMe ha parecido un problema precioso, con una dificultad adecuada y que permite ensayar muchas estrategias e ideas interesantes.<\/p>\n
Lo normal es manipular tableros peque\u00f1os hasta comprender los conceptos implicados y lanzarse despu\u00e9s a demostrar.<\/p>\n
El tablero 3 x 3 lo he trabajado mucho, intentando (y logrando de forma muy sencilla) configuraciones balanceadas de valor 1 y de valor 2. Como se pide la de menor k, evidentemente es 1. Pero es muy interesante ver que tambi\u00e9n existe la de valor 2, por razones que luego desvelar\u00e9.<\/p>\n
Antes de empezar, observamos que el n\u00famero total de filas y columnas que hay es 6 (los valores que hay que tener en cuenta).<\/p>\n
En el primer caso he hecho una animaci\u00f3n que explica c\u00f3mo buscar la configuraci\u00f3n. Hay un detalle muy importante que debemos observar. Cada vez que a\u00f1adimos un nuevo domin\u00f3, siempre aumenta en 3 unidades la suma de todos los valores de las filas y las columnas, ya que el lado que tiene 2 unidades est\u00e1 en dos filas o dos columnas (por lo que aumenta en 1 cada uno de los valores) y el lado que s\u00f3lo tiene 1, aumenta el valor de una \u00fanica fila o columna. As\u00ed, la configuraci\u00f3n balanceada de valor 1, como tiene que tener como suma de valores 6, s\u00f3lo tiene 2 domin\u00f3s.
\n\"\"<\/p>\n
Para lograr la configuraci\u00f3n balanceada de valor 2, debemos tener una suma de valores 6\u00b72 = 12, usaremos 4 domin\u00f3s, es decir, s\u00f3lo dejamos un hueco vac\u00edo del tablero. He hecho otra animaci\u00f3n para que se vea c\u00f3mo lograrlo a partir de la configuraci\u00f3n anterior. Evidentemente, es imposible lograr configuraciones balanceadas con valores mayores.\"\"<\/p>\n
Veamos ahora el tablero de lado 4. Aqu\u00ed tenemos 8 filas y columnas, de forma que es imposible lograr una configuraci\u00f3n balanceada de valor 1 (8 no es m\u00faltiplo de 3) y tambi\u00e9n es imposible lograrla de valor 2 (16 tampoco es m\u00faltiplo de 3). Para buscar una de valor 3, tenemos que lograr una suma de los valores de filas y columnas de 24, por lo que necesitaremos 8 domin\u00f3s, que tapar\u00e1n las 16 casillas del tablero completo.<\/p>\n
Tanteando un poco c\u00f3mo tapar el tablero completo, de forma muy sencilla, encontramos una configuraci\u00f3n balanceada, y, claro, de valor 3 (hay dos opciones).
\n\"\"
\nDe forma similar, en el tablero de lado 5, con 10 filas y columnas, puesto que 10 y 20 no son m\u00faltiplos de 3, tenemos que llegar a valor 3. Necesitamos que la suma de valores llegue a 30, por lo que hay que usar 10 fichas de domin\u00f3 y tapar 20 de las 25 casillas. Aqu\u00ed tenemos muchas opciones, yo he optado por partir de la configuraci\u00f3n para el tablero de lado 4, a\u00f1adir una fila y una columna, y hacer algunos cambios, como se puede ver en la animaci\u00f3n correspondiente.
\n\"\"<\/p>\n
Entonces, para un tablero de lado 5 usamos 10 domin\u00f3s, y el tablero balanceado tiene valor 3.<\/p>\n
Pasemos al tablero de lado 6. Aqu\u00ed podemos lograr un tablero balanceado de valor 1, ya que 12 es m\u00faltiplo de 3. La idea podr\u00eda ser usar dos tableros de lado 3 balanceados en diagonal, ya que cada fila y cada columna s\u00f3lo tendr\u00edan fichas en la diagonal.
\n\"\"<\/p>\n
Luego es posible lograr una configuraci\u00f3n balanceada de valor 1, usando 4 domin\u00f3s.<\/p>\n
Sin embargo, por razones que luego entenderemos, necesitamos tambi\u00e9n una configuraci\u00f3n balanceada de valor 3, que podemos lograr f\u00e1cilmente combinando configuraciones de lado 3 de valores 1 y 2 de forma sencilla.
\n\"\"<\/p>\n
Evidentemente, para esta configuraci\u00f3n necesitaremos 3\u00b712\/3 = 12 domin\u00f3s, que tapar\u00e1n 24 de los 36 cuadrados.<\/p>\n
El \u00faltimo caso particular que necesitamos trabajar es el tablero de lado 7, con 14 filas y columnas. Por no ser m\u00faltiplo de 3, no puede tener configuraciones balanceadas de valores 1 y 2, y la de valor 3 necesita 14\u00b73\/3 = 14 domin\u00f3s. Mi idea, de nuevo, ha sido lograrla a partir del tablero de lado 6 con pocas modificaciones (que tambi\u00e9n hago como una peque\u00f1a animaci\u00f3n).\"\"<\/p>\n
Despu\u00e9s de trabajar estos casos individuales, vamos con la demostraci\u00f3n propiamente dicha.<\/p>\n
Si n es un n\u00famero m\u00faltiplo de 3, de la forma 3p, entonces existe una configuraci\u00f3n balanceada de valor 1, un ejemplo de la cual se puede encontrar llenando una diagonal con p configuraciones de tableros de lado 3 (como en el ejemplo correspondiente al 6) de valor 1. Usamos 2p domin\u00f3s (2n\/3).<\/p>\n
Si n no es m\u00faltiplo de 3, entonces es mayor o igual que que 4 (recordemos que en el problema ya era mayor o igual que 3). No puede tener configuraciones balanceadas de valor 1 ni de valor 2, porque 2n y 4n no ser\u00edan m\u00faltiplos de 3. Para ver que en efecto tiene una configuraci\u00f3n balanceada de valor 3, vamos restando 4 unidades hasta llegar a un resultado menor o igual que 7 (ser\u00e1 4, 5, 6 o 7). En una esquina pondremos una configuraci\u00f3n balanceada de valor 3, y llenamos la diagonal de configuraciones de tama\u00f1o 4 de valor 3. As\u00ed logramos una configuraci\u00f3n de tama\u00f1o n de valor 3, usando 2n\u00b73\/3 = 2n domin\u00f3s.<\/p>\n
Por ejemplo, para n = 21, usamos 7 tableros 3×3 balanceados de valor 1, los ponemos en la diagonal y ya est\u00e1, una balanceada de valor 1.<\/p>\n
Otro ejemplo, para n = 22 = 4\u00b74 + 6, ponemos una balanceada de 6×6 de valor 3 en una esquina, y el resto de la diagonal la tapamos con 4 tableros 4×4 balanceados de valor 3, obteniendo una configuraci\u00f3n m\u00ednima con 8\u00b74 + 12 = 44 domin\u00f3s (tambi\u00e9n 44\u00b73\/3).<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 4 de la Olimpiada Matem\u00e1tica Femenina Europea (EGMO 2018) Se dirige a una edad de: 17 a\u00f1os Un domin\u00f3 es una ficha de 1 x 2 o de 2 x 1 cuadrados unitarios. Sean n un entero mayor o igual que 3. Se ponen domin\u00f3s en un tablero de n x n casillas de […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2242015,1738,2849,3303],"tags":[],"class_list":["post-824","post","type-post","status-publish","format-standard","hentry","category-egmo","category-olimpiadas","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/824","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=824"}],"version-history":[{"count":4,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/824\/revisions"}],"predecessor-version":[{"id":842,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/824\/revisions\/842"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=824"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=824"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=824"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}