Nacional 2000 N2 P1

[Ivan]

Laura debe elegir números naturales, sin repetir, desde [math]1 hasta [math]2000, inclusive, de modo que ninguno de los elegidos sea igual al triple de otro de los elegidos. Determinar cuál es la mayor cantidad de números que puede elegir Laura.

[bruno]

Empecemos viendo el intervalo [math][667;2000] porque podemos elegir todos los [math]n que no sean multiplos de [math]3 ya que no me impediria elegir el numero [math]\frac{n}{3} y ademas [math]3n>2000.

Por otro lado en el intervalo [math][1;666] no es conveniente elegir los numeros de la forma [math]3k ya que me impede elegir tanto el [math]k como el [math]9k. Luego nos quedamos con los numeros que tienen resto [math]1 y [math]2 en la division por [math]3 y si los observamos vemos que los triples de esos numeros desde [math]1 hasta [math]221 son los multiplos de [math]3 en el intervalo [math][1;666] que no elegi y desde [math]223 hasta [math]665 son los multiplos de [math]3 en el intervalo [math][667;2000].

Por lo tanto la mayor cantidad de numeros se obtiene eligiendo todos los numeros del intervalo [math][667;2000] y los no multiplos de [math]3 en el intervalo [math][1;221]. En total son [math]1482 numeros.

[ésta]

Pero por ejemplo podría agregar el [math]9 a tu eleccion y no habría ningún problema porque no se eligió ni el [math]3 ni el [math]27.

[jhn]

Spoiler: mostrar

Si se escogen los números [math]k no divisibles entre 3 y los de la forma [math]3^2k, [math]3^4k y [math]3^6k, en el intervalo de 1 a 2000, resultan

[math]2000-\lfloor\frac{2000}{3}\rfloor+\lfloor\frac{2000}{9}\rfloor-\lfloor\frac{2000}{27}\rfloor+\lfloor\frac{2000}{81}\rfloor-\lfloor\frac{2000}{243}\rfloor+\lfloor\frac{2000}{729}\rfloor

[math]=2000-666+222-74+24-8+2=1500,

de los cuales ninguno es triple de otro. No puede haber más, pues si [math]X=\{1,2,\ldots,2000\} y [math]3\nmid k entonces de cada conjunto [math]\{k,3k\}\cap X, [math]\{3^2k,3^3k\}\cap X, [math]\{3^4k,3^5k\}\cap X, [math]\{3^6k\}\cap X a lo sumo se puede seleccionar un elemento.

[tuvie]

Este no es igual al 2 del provincial de nivel 1? Solo que con un rango mayor y en lugar del triple, 10 veces.

[Agusanso]

Jaja estaba por comentar lo mismo, es bastante parecido.

[Peznerd]

Spoiler: mostrar

Si se escogen los números $k$ no divisibles entre 3 y los de la forma $3^2k$, $3^4k$ y $3^6k$, en el intervalo de 1 a 2000, resultan

$2000-\lfloor\frac{2000}{3}\rfloor+\lfloor\frac{2000}{9}\rfloor-\lfloor\frac{2000}{27}\rfloor+\lfloor\frac{2000}{81}\rfloor-\lfloor\frac{2000}{243}\rfloor+\lfloor\frac{2000}{729}\rfloor$

$=2000-666+222-74+24-8+2=1500$,

de los cuales ninguno es triple de otro. No puede haber más, pues si $X=\{1,2,\ldots,2000\}$ y $3\nmid k$ entonces de cada conjunto $\{k,3k\}\cap X$, $\{3^2k,3^3k\}\cap X$, $\{3^4k,3^5k\}\cap X$, $\{3^6k\}\cap X$ a lo sumo se puede seleccionar un elemento.

Sip, me había dado mal pero conté tres números de más.