Question

Sea $S$ un subconjunto de $\{1,2,3,\ldots,1989\}$ tal que ningún par de elementos de $S$ difiera en $4$ ni en $7.$ ¿Cuál es el mayor número de elementos que puede tener $S$ ?

Let $S$ be a subset of $\{1,2,3,\ldots,1989\}$ such that no two members of $S$ differ by $4$ or $7.$ What is the largest number of elements $S$ can have?

Respuesta

Respuesta: 905

Conceptos:argumento extremal teoría de grafos subconjuntos

Nivel de dificultad: 2930

Pista pequeña:

Entre cualesquiera once enteros consecutivos, el grafo de diferencias prohibidas es un ciclo de $11$ vértices

Within any eleven consecutive integers, the forbidden-difference graph is an $11$ -cycle

Pista grande:

Para una construcción que alcance la cota, busca cinco clases de residuos permitidas módulo $11$

For a matching construction, look for five allowable residue classes modulo $11$

Solución:

Entre cualesquiera once enteros consecutivos, une dos números cuando su diferencia sea $4$ o $7.$ Como $7=11-4,$ este grafo es un ciclo de $11$ vértices, cuyo mayor conjunto independiente tiene tamaño $5.$ Del mismo modo, cualesquiera diez enteros consecutivos inducen un camino de diez vértices y aportan como máximo $5.$ Como $1989=179\cdot11+2\cdot10,$ se obtiene $|S|\leq179(5)+2(5)=905.$

Esta cota se alcanza tomando todos los enteros cuyo residuo módulo $11$ es $1,$ $3,$ $4,$ $6,$ o $9.$ Ningún par de residuos seleccionados difiere en $4$ ni en $7$ módulo $11,$ y cada uno de estos cinco residuos aparece $181$ veces desde $1$ hasta $1989.$ Por tanto, el máximo es $5(181)=905.$

On any eleven consecutive integers, join two numbers when their difference is $4$ or $7.$ Because $7=11-4,$ this graph is an $11$ -cycle, whose largest independent set has size $5.$ Similarly, any ten consecutive integers induce a path on ten vertices and contribute at most $5.$ Since $1989=179\cdot11+2\cdot10,$ this gives $|S|\leq179(5)+2(5)=905.$

This bound is attained by taking every integer whose residue modulo $11$ is $1,$ $3,$ $4,$ $6,$ or $9.$ No two selected residues differ by $4$ or $7$ modulo $11,$ and each of these five residues occurs $181$ times from $1$ through $1989.$ Thus the maximum is $5(181)=905.$

1989 AIME Problema 13

Respuesta: 905

Nivel de dificultad: 2930

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años