{"id":2151,"date":"2021-07-31T06:39:47","date_gmt":"2021-07-31T06:39:47","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=2151"},"modified":"2021-07-31T06:43:13","modified_gmt":"2021-07-31T06:43:13","slug":"solucion-a-dos-filas-de-bombillas","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2021\/07\/31\/solucion-a-dos-filas-de-bombillas\/","title":{"rendered":"Soluci\u00f3n a dos filas de bombillas"},"content":{"rendered":"<pre>Problema 5 de la fase nacional de la 57 Olimpiada Matem\u00e1tica Espa\u00f1ola (2021)\r\nSe dirige a una edad de: 16-17 a\u00f1os<\/pre>\n<p>Disponemos de 2n bombillas colocadas en dos filas (A y B) y numeradas del 1 al n en cada fila.<\/p>\n<p>Algunas (o ninguna) de las bombillas est\u00e1n encendidas y el resto, apagadas; decimos que esto es un \u201cestado\u201d.<\/p>\n<p>Dos estados son distintos si hay una bombilla que est\u00e1 apagada en uno de ellos y encendida en el otro.<\/p>\n<p>Diremos que un estado es \u201cbueno\u201d si hay la misma cantidad de bombillas encendidas en la fila A que en la B.<\/p>\n<p>Demuestra que el n\u00famero total de estados buenos (EB) dividido por el n\u00famero total de estados (ET), es: EB\/ET = (1\u00b73\u00b75\u00b7&#8230;\u00b7(2n \u2013 1))\/(2<sup>n<\/sup>\u00b7n!).<img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-2132\" src=\"https:\/\/blogs.ua.es\/dimates\/files\/2021\/07\/206.dosfilasbombillas.png\" alt=\"\" width=\"300\" height=\"300\" srcset=\"https:\/\/blogs.ua.es\/dimates\/files\/2021\/07\/206.dosfilasbombillas.png 300w, https:\/\/blogs.ua.es\/dimates\/files\/2021\/07\/206.dosfilasbombillas-150x150.png 150w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><br \/>\nSoluci\u00f3n:<br \/>\n<!--more--><br \/>\nEn el ejemplo que se ve en la imagen, se aprecian los 20 estados buenos de los 64 totales en el caso de n = 3, donde se confirma que 20\/64 = 5\/16 = (1\u00b73\u00b75)\/(2\u00b3\u00b73!) = 15\/48 = 5\/16.<\/p>\n<p>En estos problemas de combinatoria, se suele aplicar uno de los siguientes tres m\u00e9todos de ataque: inducci\u00f3n sobre uno de los elementos, aunque en este caso no he visto la manera de abordarlo as\u00ed, simplificaci\u00f3n a partir de f\u00f3rmulas conocidas, o bien manipulaci\u00f3n de propiedades.<\/p>\n<p>Tras una primera revisi\u00f3n de los casos m\u00e1s sencillos, se aprecia que para n = 1 se da la igualdad (hay en total 4 estados, de los que 2 son buenos), y para n = 2 tambi\u00e9n (hay 16 estados, de los que 6 son buenos, uno con cero bombillas encendidas, otro con todas encendidas y 4 con dos bombillas encendidas).<\/p>\n<p>El n\u00famero total de estados diferentes es muy sencillo justificar que es 2<sup>2n<\/sup>, ya que cada bombilla de las 2n puede estar independientemente en dos estados.<\/p>\n<p>No me pareci\u00f3 sencillo calcular la cifra general de estados buenos, aunque es r\u00e1pido llegar a la conclusi\u00f3n de que es igual a sumar los cuadrados de los n\u00fameros combinatorios de n elementos, no conoc\u00eda ninguna f\u00f3rmula que me permitiese simplificarlo (despu\u00e9s de hacer el problema, descubr\u00ed que hay una f\u00f3rmula que garantiza que la suma de los cuadrados de todos los n\u00fameros combinatorios de n elementos es igual al n\u00famero combinatorio resultado de tomar n elementos de un total de 2n, pero no fue as\u00ed como lo resolv\u00ed realmente).<\/p>\n<p>Despu\u00e9s de pelearme con el problema de las formas m\u00e1s evidentes (combinatoria b\u00e1sica e inducci\u00f3n) de forma infructuosa, resolv\u00ed tratar de reformular la igualdad para ver si me suger\u00eda algo.<\/p>\n<p>Puesto que el n\u00famero de estados es 2<sup>2n<\/sup>, el que la f\u00f3rmula sea v\u00e1lida es equivalente a probar que EB = 2<sup>2n<\/sup>\u00b7(1\u00b73\u00b75\u00b7&#8230;\u00b7(2n \u2013 1))\/(2n\u00b7n!) = 2<sup>n<\/sup>\u00b7(1\u00b73\u00b75\u00b7&#8230;\u00b7(2n \u2013 1))\/(n!).<\/p>\n<p>Para intentar expresar el producto de n\u00fameros impares como un \u00fanico factorial, puedo introducir todos los factores pares necesarios entre 1 y 2n, y, puesto que dispongo de n factores 2 y eso coincide con un factor 2 para cada n\u00famero par, s\u00f3lo tendr\u00e9 que introducir la mitad de cada n\u00famero par, es decir, que esa fracci\u00f3n coincide con 2<sup>n<\/sup>\u00b7n!\u00b7(1\u00b73\u00b75\u00b7&#8230;\u00b7(2n \u2013 1))\/(n!\u00b7n!) = (1\u00b72\u00b73\u00b74\u00b75\u00b76\u00b7&#8230;\u00b7(2n \u2013 2)(2n \u2013 1)(2n))\/(n!\u00b7n!) = (2n)!\/(n!\u00b7n!), que es exactamente el n\u00famero combinatorio que representa la cantidad de formas de tomar n elementos de un total de 2n.<\/p>\n<p>Es decir, que demostrar la validez de la f\u00f3rmula equivale a ver que el n\u00famero de estados buenos coincide con la cantidad de formas de tomar n elementos de un total de 2n.<\/p>\n<p>Basta, pues, establecer una correspondencia entre una elecci\u00f3n tal y un estado bueno y ver que es una correspondencia biun\u00edvoca, es decir, que a estados buenos distintos corresponden elecciones diferentes y viceversa.<\/p>\n<p>La clave est\u00e1 en elegir n posiciones de las 2n bombillas y, por ejemplo, en la fila A, encender las bombillas elegidas y dejar apagadas las no elegidas, y en la fila B actuar al contrario, dejando apagadas las elegidas y encendiendo las no elegidas.<\/p>\n<p>Puesto que la elecci\u00f3n es de n bombillas, el n\u00famero de bombillas no elegidas coincide con las elegidas, por lo que la cantidad de bombillas encendidas ser\u00e1 el mismo en las dos filas, as\u00ed que cada elecci\u00f3n corresponde a un estado bueno, y si tenemos un estado bueno, diremos que est\u00e1n elegidas las bombillas encendidas de la fila A y las apagadas de la fila B, que ser\u00e1n un total de n, por lo que cada estado bueno corresponde a una elecci\u00f3n de n bombillas.<\/p>\n<p>Por lo tanto, as\u00ed completamos la demostraci\u00f3n.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problema 5 de la fase nacional de la 57 Olimpiada Matem\u00e1tica Espa\u00f1ola (2021) Se dirige a una edad de: 16-17 a\u00f1os Disponemos de 2n bombillas colocadas en dos filas (A y B) y numeradas del 1 al n en cada fila. Algunas (o ninguna) de las bombillas est\u00e1n encendidas y el resto, apagadas; decimos que [&hellip;]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2242021,1738,2849,3303],"tags":[],"class_list":["post-2151","post","type-post","status-publish","format-standard","hentry","category-olimpiada-matematica-espanola","category-olimpiadas","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/2151","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=2151"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/2151\/revisions"}],"predecessor-version":[{"id":2154,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/2151\/revisions\/2154"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=2151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=2151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=2151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}