{"id":183,"date":"2017-10-06T20:47:09","date_gmt":"2017-10-06T20:47:09","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=183"},"modified":"2017-10-07T07:15:49","modified_gmt":"2017-10-07T07:15:49","slug":"aviones-y-ciudades-s","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2017\/10\/06\/aviones-y-ciudades-s\/","title":{"rendered":"Soluci\u00f3n a aviones y ciudades"},"content":{"rendered":"<pre>Olimpiada All-Russian, primer problema del primer d\u00eda del grado 9\r\n<\/pre>\n<p>En un pa\u00eds, algunas ciudades est\u00e1n conectadas por vuelos en avi\u00f3n, no necesariamente en los dos sentidos (no hay m\u00e1s que un vuelo entre dos ciudades determinadas).<\/p>\n<p>Decimos que una ciudad A est\u00e1 disponible desde una ciudad B, si podemos volar de B hasta A, tal vez haciendo varias escalas.<\/p>\n<p>Se sabe que para cada par de ciudades P y Q, existe una ciudad R desde la que tanto P como Q est\u00e1n disponibles.<br \/>\nPrueba que existe una ciudad A desde la que todas las ciudades est\u00e1n disponibles.<br \/>\n<img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-179\" src=\"https:\/\/blogs.ua.es\/dimates\/files\/2017\/10\/13.avionesyciudades.png\" alt=\"\" width=\"300\" height=\"300\" srcset=\"https:\/\/blogs.ua.es\/dimates\/files\/2017\/10\/13.avionesyciudades.png 300w, https:\/\/blogs.ua.es\/dimates\/files\/2017\/10\/13.avionesyciudades-150x150.png 150w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><br \/>\n<!--more--><br \/>\nSoluci\u00f3n:<\/p>\n<p>La respuesta es sencilla, una vez que se entiende bien.<\/p>\n<p>Veamos que es cierto en casos peque\u00f1os. Debe tratarse de, al menos, tres ciudades, puesto que para menos casos no es aplicable el razonamiento.<\/p>\n<p>Con tres ciudades, est\u00e1 claro que si tomamos dos de ellas, existe una desde las que ambas son accesibles, es decir, desde esa tercera ciudad, diferente de las otras dos, ambas son accesibles, luego desde esa ciudad todas las restantes son accesibles.<\/p>\n<p>En este caso, ni siquiera es necesario aplicar inducci\u00f3n estrictamente. Supongamos que M es una ciudad desde la que el n\u00famero de ciudades accesibles es lo mayor posible (en lenguaje matem\u00e1tico, este elemento se denomina maximal).<\/p>\n<p>A partir de ahora se razona por reducci\u00f3n al absurdo, esto es, suponemos que algo es cierto y llegamos a una situaci\u00f3n imposible. Como conclusi\u00f3n, lo que hemos supuesto no es cierto.<\/p>\n<p>Veamos que es imposible que haya una ciudad inaccesible desde M (la ciudad maximal). <\/p>\n<p>Si existiera esa ciudad, llam\u00e9mosla X, inaccesible desde M, al tomar P y Q como M y X respectivamente, sabemos que existe una ciudad R desde la que X y M son accesibles, pero eso significa que desde R es accesible cualquier ciudad que lo fuese desde M, ya que podr\u00edamos hacer transbordo en M y tambi\u00e9n es accesible X, cosa que es imposible, pues se supone que no es posible tener m\u00e1s ciudades accesibles que M (recuerda que M era maximal).<\/p>\n<p>Luego desde M todas las ciudades son accesibles, y es la que busc\u00e1bamos para probar el enunciado.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Olimpiada All-Russian, primer problema del primer d\u00eda del grado 9 En un pa\u00eds, algunas ciudades est\u00e1n conectadas por vuelos en avi\u00f3n, no necesariamente en los dos sentidos (no hay m\u00e1s que un vuelo entre dos ciudades determinadas). Decimos que una ciudad A est\u00e1 disponible desde una ciudad B, si podemos volar de B hasta A, [&hellip;]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3303],"tags":[],"class_list":["post-183","post","type-post","status-publish","format-standard","hentry","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/183","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=183"}],"version-history":[{"count":2,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/183\/revisions"}],"predecessor-version":[{"id":185,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/183\/revisions\/185"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}