{"id":2743,"date":"2023-02-04T19:30:02","date_gmt":"2023-02-04T19:30:02","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=2743"},"modified":"2023-02-04T19:30:02","modified_gmt":"2023-02-04T19:30:02","slug":"solucion-a-numeros-de-colores","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2023\/02\/04\/solucion-a-numeros-de-colores\/","title":{"rendered":"Soluci\u00f3n a n\u00fameros de colores"},"content":{"rendered":"
Problema 1 de la Fase Local de la Olimpiada Espa\u00f1ola de Matem\u00e1ticas 2023 (viernes ma\u00f1ana)\r\nSe dirige a una edad de: 16-17 a\u00f1os<\/pre>\n
Sea n un entero positivo.<\/p>\n
Cada uno de los n\u00fameros 1, 2, 3, \u2026, 2023 se pinta de un color a escoger entre n distintos.<\/p>\n
Una vez coloreados, se observa que cualquier par (a, b) con a < b y de manera que a | b (a divide a b), satisface que a y b son de distinto color.<\/p>\n
Encuentra el menor valor de n para el cual esta situaci\u00f3n es posible.
\n\"\"<\/p>\n
Soluci\u00f3n:
\n
\nLa idea clave es que debemos construir cadenas de n\u00fameros en la que cada n\u00famero sea divisible por todos los de la izquierda de esa cadena, y estudiar cu\u00e1l es m\u00e1s larga. Esta situaci\u00f3n se puede ensayar escribiendo los 10 n\u00fameros del 1 al 10, tratando de colorearlos seg\u00fan las reglas, y viendo que necesitamos al menos 4 colores.<\/p>\n
Es evidente que 1 debe ser de un color diferente a todos los dem\u00e1s, pues 1 divide a cualquier n\u00famero. Sin embargo, todos los n\u00fameros primos pueden ser del mismo color, ya que ninguno divide al otro.<\/p>\n
Una idea muy b\u00e1sica es que si descomponemos un n\u00famero en factores primos, y presenta una cierta cantidad de n\u00fameros primos en su descomposici\u00f3n (posiblemente varios de ellos repetidos), le pintemos de color que est\u00e9 marcado con la cantidad de primos de su descomposici\u00f3n + 1.<\/p>\n
As\u00ed, por ejemplo, si ponemos un color 1, s\u00f3lo aparecer\u00e1 en el 1.<\/p>\n
El color 2 aparecer\u00e1 \u00fanicamente en los primos, cuyo \u00fanico divisor inferior a ellos mismos es el 1.<\/p>\n
Los n\u00fameros con 2 factores, como el caso del 4, el 6, el 9, se pintan del color 3.<\/p>\n
Si seguimos este procedimiento necesitaremos un n\u00famero n de 11 colores, el \u00faltimo de los cuales servir\u00e1 para pintar el 2\u00b9\u2070 y el 2\u2079\u00b73, que est\u00e1n en la lista. No hay n\u00fameros con m\u00e1s factores, ya que el primero que tiene 11 factores es 2\u00b9\u00b9, que vale 2048, por ser 2 el menor n\u00famero primo.<\/p>\n
Es evidente que una tal distribuci\u00f3n de colores cumple el enunciado, ya que si a < b y a | b, los primos de la descomposici\u00f3n de a son algunos de la descomposici\u00f3n de b, no todos, por ser menor y divisible, por lo que est\u00e1n pintados de diferente color.<\/p>\n
Para ver que es el menor valor posible de n, basta constatar que la cadena 1 < 2 < 4 < 8 < 16 < 32 < 64 < 128 < 256 < 512 < 1024 hay 11 n\u00fameros, y no puede haber 2 con el mismo color seg\u00fan el enunciado, as\u00ed que debe ser 11, ya que hay una distribuci\u00f3n con 11 y no puede darse con menos.<\/p>\n
Otro m\u00e9todo de coloreado que puede probarse f\u00e1cilmente que es v\u00e1lido (y usa 11 colores) es pintar del mismo color todos los n\u00fameros entre una potencia de 2 (incluida) hasta la siguiente. Es decir, 1 de un color, 2 y 3 de otro, del 4 al 7 de otro, y as\u00ed sucesivamente. As\u00ed, nunca un n\u00famero y su doble o los n\u00fameros siguientes son del mismo color.<\/p>\n
con este coloreado, si dos n\u00fameros diferentes a y b tienen la relaci\u00f3n de a < b y a|b, entonces 2a <= b, cosa que impide que sean del mismo color.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 1 de la Fase Local de la Olimpiada Espa\u00f1ola de Matem\u00e1ticas 2023 (viernes ma\u00f1ana) Se dirige a una edad de: 16-17 a\u00f1os Sea n un entero positivo. Cada uno de los n\u00fameros 1, 2, 3, \u2026, 2023 se pinta de un color a escoger entre n distintos. Una vez coloreados, se observa que cualquier […]<\/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-2743","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\/2743","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=2743"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/2743\/revisions"}],"predecessor-version":[{"id":2744,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/2743\/revisions\/2744"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=2743"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=2743"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=2743"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}