tag:blogger.com,1999:blog-61240864734675463622024-03-14T09:20:51.825+01:00AbuhardilladosA la sombra de la La Buhardilla 2.0Cartesianohttp://www.blogger.com/profile/03151539196944757863noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6124086473467546362.post-45682452440270801392012-09-27T01:09:00.002+02:002012-09-27T01:09:40.458+02:00Coloreando vérticesAquí os dejo la solución que mandé al Desafío nº5 de Gaussianos.com<br />
<br />
Dado que preguntaban por los errores que habíamos cometido algunos en nuestras soluciones, aquí podéis comprobar el mío.<br />
<br />
En concreto, se pedía en el 2º apartado: <b>¿Cuántos segmentos que unan dos vértices
de un polígono se han de añadir <span style="color: blue;"><i>(de alguna forma concreta a determinar)</i></span> a dicho polígono</b> (dejaría de serlo) <b>para
<span style="color: blue;">(asegurar)</span> que necesitemos más colores de los obtenidos en 1)?</b><br />
Y yo lo interpreté como: <b>¿Cuántos segmentos que unan dos vértice<b>s
de un polígono se han de añadir <span style="color: blue;"><i>(de cualquier forma)</i></span> a dicho polígono</b> (dejaría de serlo) <b>para
<span style="color: blue;">(asegurar) <span style="color: black;">que</span></span> necesitemos más colores de los obtenidos en 1)?</b></b><br />
<br />
La verdad es que no presté atención a las explicaciones que se dieron en
los comentarios, y malinterpreté el enunciado. Aunque para ser sincero,
creo que lo que yo resolví es aún más interesante, aunque por supuesto
erróneo.<b><b> </b></b>El primer paso en un problema consiste en entender que se pide, así que a partir de ahí todo lo que hice no vale. Pero ... siempre está bien ver alguna variación.<br />
<br />
Pondré un par de ejemplos para mejor comprensión:<ul>
<li>Si tenemos un cuadrado, hacen falta 2 colores, y 1 sólo segmento más para obligar a usar 3 colores.</li>
</ul>
<ul>
<li>Si tenemos un pentágono, hacen falta 3 colores, y según mi solución harían falta 4 segmentos más para que los pongas como los pongas hagan falta 4 colores. Sin embargo, en la solución correcta para el pentágono bastarían 3 segmentos.</li>
</ul>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-vjdY3PXTwdc/UGN9sgyFFfI/AAAAAAAAABY/q05237c2U1U/s1600/ejemplo.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="302" src="http://4.bp.blogspot.com/-vjdY3PXTwdc/UGN9sgyFFfI/AAAAAAAAABY/q05237c2U1U/s320/ejemplo.PNG" width="320" /></a></div>
<br />
----------<br />
Esta fue mi solución:<br />
<br />
<div style="text-align: left;">
1) Coloreamos los vértices de un polígono de tal forma que dos vértices no pueden tener el mismo color si son los extremos de una arista. <b>¿Cuántos colores son necesarios para colorear un polígono de n lados? </b></div>
<br />
Llamamos ‘<b>c</b>’ al número de colores necesarios.<br />
<br />
<ul>
<li>Caso par: Si <b>n = 2p</b> , con <b>p </b><b>€ N</b> → <b>c = 2</b></li>
</ul>
<b> </b>
<br />
Los n vértices se pueden ordenar de forma consecutiva partiendo de uno cualquiera
al que le asignamos el ‘1’ y numerando el siguiente de forma ordenada siguiendo
las agujas del reloj arista por arista.<br />
<br />
Dado que n es par, el primero es impar (es el ‘1’) y el último es par (es el n = 2p), bastan 2 colores para colorear los vértices pares e impares.<br />
<br />
Sólo existe una distribución posible con 2 colores: ( p, p ) es decir, ‘p’
vértices de un color y ‘p’ de otro.<br />
<br />
<ul>
<li>Caso impar: Si <b>n = 2p + 1</b> , con <b>p </b><b> € N</b> → <b>c = 3</b></li>
</ul>
<b> </b>
<br />
Ordenando los n vértices de la misma forma que antes, llegamos a la ordenación de pares e impares, pero en este caso la última arista uniría dos vértices impares. Por
tanto no es posible usar sólo 2 colores.<br />
<br />
Podemos colorear los ‘p’ primeros impares de un color, y los ‘p’ primeros pares de otro color, mientras que el vértice <i style="mso-bidi-font-style: normal;">2p+1</i>
será de un tercer color<br />
<br />
En este caso existe más de una distribución posibles con 3 colores: ( a , b , n-a-b )
<b> </b><br />
<br />
<b>2) ¿Cuántos segmentos que unan dos vértices
de un polígono se han de añadir a dicho polígono</b> (dejaría de serlo) <b>para
que necesitemos más colores de los obtenidos en 1)?</b><br />
<br />
Llamamos ‘s’ el número de segmentos necesarios.<br />
<br />
<ul>
<li>Caso par: Si <b>n = 2p</b> , con <b>p</b><b> € N</b> → <b>c = 2</b></li>
</ul>
<br />
Teníamos una única distribución de colores ( p , p )<br />
<br />
El número total de uniones entre vértices de distinto color es p<sup>2</sup><br />
<br />
El número de uniones del polígono original es 2p<br />
<br />
Por tanto el número necesario de segmentos será s = ( p<sup>2</sup> ) – ( 2p ) +1 = ( p – 1 )<sup>2</sup><br />
<br />
Si <b>n = 2p</b> entonces <span style="background-color: yellow;">s = ( n/2 – 1 )<sup>2</sup></span><br />
<br />
<ul>
<li>Caso impar múltiplo de 3: Si <b>n = 2p + 1 = 3q</b> , con <b>p,q </b><b>€ N</b> → <b>c = 3</b></li>
</ul>
<b> </b>
<br />
Teníamos varias distribuciones posibles de colores ( a , b
, n-a-b )<br />
<br />
El número total de uniones entre vértices de distinto color es ab + a(n-a-b) + b(n-a-b)<br />
<br />
El número de uniones del polígono original es 2p+1<br />
<br />
Por tanto el número necesario de segmentos será s
= ( ab + an – a<sup>2</sup> – ab + bn – ab – b<sup>2</sup> ) – ( 2p + 1 ) + 1 =
an + bn – ab – a<sup>2</sup> –
b<sup>2</sup> – n + 1<br />
<br />
Derivando respecto a ‘a’ y ‘b’ e igualando a 0, obtenemos:<br />
<br />
n – b – 2a = 0<br />
n – a – 2b = 0<br />
<br />
Y se obtiene la solución a = b = n/3<br />
<br />
Es decir, la distribución
de colores ( n/3 , n/3, n/3 )<br />
<br />
Las derivadas segundas respecto a ‘aa’,
‘ab’ y ‘bb’ son: -2, -1, -2<br />
<br />
D = (-2) * (-2) – (-1)<sup>2</sup> = 3 > 0<br />
<br />
Dado que D > 0 y la derivada segunda respecto a ‘a’ es < 0 tenemos que la solución obtenida es un máximo. (El máximo nos garantiza el mínimo número de segmentos paracualquier distribución de colores que puedo escoger).<br />
<br />
Si n = 2p + 1 = 3q entonces el
valor de <span style="background-color: yellow;">s = ( n<sup>2</sup>
– 3n + 3 ) / 3</span><br />
<br />
Caso impar no múltiplo de 3:<br />
<br />
Si <b>n = 2p + 1 = 3q
1 , con <b>p,q </b> → <b>c = 3</b> </b><br />
<br />
Razonando de la misma
forma que antes llegamos a la misma solución, pero n/3 no es un valor entero,
por lo que la distribución de colores sería (
a , a , b ) = ( a , a , n-2a ).
<br />
Viendo las derivadas de s se observa que es convexa y existe un
único máximo, y dado que la solución no puede escogerse no entera, la solución
será el punto más próximo.<br />
<br />
<a href="http://4.bp.blogspot.com/-z0-cMD_Pwjk/UGNs_eXV1uI/AAAAAAAAABI/OYM1HHxejS0/s1600/convexo.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="302" src="http://4.bp.blogspot.com/-z0-cMD_Pwjk/UGNs_eXV1uI/AAAAAAAAABI/OYM1HHxejS0/s320/convexo.PNG" width="320" /></a>
En la figura se observa un ejemplo
gráfico que representa el número de segmentos en función de las distintas
distribuciones para n=19, donde se observa que la gráfica es convexa.
El número total de uniones entre vértices de distinto color es a<sup>2</sup> + 2ab<br />
<br />
El número de uniones del polígono original es 2p+1<br />
<br />
Por tanto el número necesario de segmentos será s
= ( a<sup>2</sup> + 2ab ) – ( 2p + 1 ) + 1 = a<sup>2</sup> + 2ab – n + 1<br />
<br />
Si n = 3q + 1 entonces a = (n-1)/3 y b = a+1
Entonces s = ( n<sup>2</sup> – 3n + 2 ) / 3<br />
<br />
Y si n = 3q – 1 entonces a = ( n+1 )/3 y
b = a – 1<br />
<br />
Entonces s = ( n<sup>2</sup> – 3n + 2 ) / 3, igual que antes<br />
<br />
Si n = 2p + 1 = 3q+-1 entonces el valor de <span style="background-color: yellow;">s = ( n<sup>2</sup> – 3n + 2 ) / 3</span>Cartesianohttp://www.blogger.com/profile/03151539196944757863noreply@blogger.com0tag:blogger.com,1999:blog-6124086473467546362.post-8886560045408309522012-08-01T19:41:00.001+02:002012-08-01T21:44:57.255+02:00La tarta de la discordiaAquí os dejo la solución que propuse en <a href="http://gaussianos.com/desafio-gaussianosyguijarro-n%c2%ba-3-la-tarta-de-la-discordia-solucion-y-ganador/">Gaussianos.com</a> para el:<br />
<h2 id="post-8592">
<a href="http://gaussianos.com/desafio-gaussianosyguijarro-n%c2%ba-3-la-tarta-de-la-discordia-solucion-y-ganador/" rel="bookmark" title="Desafío GaussianosyGuijarro nº 3 “La tarta de la discordia” – Solución y ganador">Desafío GaussianosyGuijarro nº 3 “La tarta de la discordia” – Solución y ganador</a></h2>
<div id="post-8592">
Por si a alguien le resulta útil :)</div>
<div id="post-8592">
Se aceptan críticas :)</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-aIUCpyjuszY/UBlp7NbYykI/AAAAAAAAAA0/ekiqzhiOBH0/s1600/tarta.GIF" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="153" src="http://3.bp.blogspot.com/-aIUCpyjuszY/UBlp7NbYykI/AAAAAAAAAA0/ekiqzhiOBH0/s320/tarta.GIF" width="320" /></a></div>
<div id="post-8592">
<br />
Lo cierto es que indiqué para que valores se alcanza el mínimo, o sea que ambos comensales coman lo mismo, pero no di todas las soluciones posibles, me faltaron la "mitad". ¿Alguien sabe cuáles son? </div>Cartesianohttp://www.blogger.com/profile/03151539196944757863noreply@blogger.com0tag:blogger.com,1999:blog-6124086473467546362.post-19322319944648518852012-08-01T19:35:00.003+02:002012-08-01T19:35:55.810+02:00El recorrido de la hormigaAquí dejo mi solución al problema propuesto en <a href="http://gaussianos.com/">Gaussianos.com</a><br />
<h2 id="post-8790">
<a href="http://gaussianos.com/desafio-gaussianosyguijarro-n%c2%ba-4-el-recorrido-de-la-hormiga-solucion-y-ganador/" rel="bookmark" title="Desafío GaussianosyGuijarro nº 4 “El recorrido de la hormiga” – Solución y ganador">Desafío GaussianosyGuijarro nº 4 “El recorrido de la hormiga” – Solución y ganador</a></h2>
<div id="post-8790">
Por si a alguien le resulta de interés :)</div>
<div id="post-8790">
Se aceptan comentarios :) </div>
<div id="post-8790">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-L2d2eFP_f9c/UBloUmq25JI/AAAAAAAAAAs/Dp5NrohaHJY/s1600/desafio4hormiga.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="220" src="http://2.bp.blogspot.com/-L2d2eFP_f9c/UBloUmq25JI/AAAAAAAAAAs/Dp5NrohaHJY/s320/desafio4hormiga.PNG" width="320" /></a></div>
<div id="post-8790">
<br /></div>Cartesianohttp://www.blogger.com/profile/03151539196944757863noreply@blogger.com0tag:blogger.com,1999:blog-6124086473467546362.post-59780933692974367172012-06-10T20:06:00.000+02:002012-06-20T23:06:23.459+02:00Un agujero en la BuhardillaLos chicos de La Buhardilla 2.0 hablaban en su podcast sobre el comportamiento que tendría un objeto que tirásemos por un agujero que atravesara la Luna de un punto a otro del satélite. Tras la descripción correcta por parte de Kike, indicando que se produciría un movimiento periódico haciendo que el objeto viajara de uno a otro extremo eternamente, Abraham se opone firmemente indicando que el objeto se quedará en el centro. Por su parte Javi no se aclara y le da la razón a ambos por turnos. Tras dejarlo sin aclarar, aseguran que lo estudiarían, pero en el siguiente programa, y a pesar de los comentarios de sus oyentes, lejos de aclararlo lo dejan igual y vuelven a asegurar que lo consultarán a un físico. Les facilitaremos la tarea, ahí dejo la solución.<br />
<a href="http://cartesianocaotico.blogspot.com/p/el-agujero-de-la-luna.html">El agujero de la Luna</a>Cartesianohttp://www.blogger.com/profile/03151539196944757863noreply@blogger.com0