A estratégia é (i) estabelecer uma cota inferior para an (mostrar que k cores não bastam), e (ii) exibir uma coloração com k cores (mostrar que k cores bastam). Quando (i) e (ii) coincidem, encontramos o mínimo. Cota inferior: an ≥ 3 para n ≥ 32. Lema. Se n ≥ 32, não conseguimos colorir {2,...,n} com apenas 2 cores respeitando a regra. Prova. Suponha que exista uma 2-coloração válida. Consideramos os cinco números 2,4,8,16,32, todos presentes em {2,...,n} quando n ≥ 32. Digamos que 2 tem cor X. Produto Raciocínio Conclusão 2 · 2 = 4 Se 4 fosse X, a 4 tem cor Y tríade (2,2,4) seria monocromática 4 · 4 = 16 Se 16 fosse Y, a 16 tem cor X tríade (4,4,16) seria monocromática 2 · 8 = 16 Como 2 e 16 são X, a 8 tem cor Y tríade (2,8,16) não pode ter 8 em X 4 · 8 = 32 Como 4 e 8 são Y, a 32 tem cor X tríade (4,8,32) não pode ter 32 em Y 2 · 16 = 32 Mas agora 2,16,32 têm Contradição! todos cor X Logo, 2 cores não bastam quando n ≥ 32. Assim a45 ≥ 3 e a2025 ≥ 3. ■ Item (a): a45 = 3, colorindo por intervalos. Exibimos uma coloração com 3 cores: pinte cada número x ∈ {2,...,45} conforme o intervalo: cor 1: [2,3] cor 2: [4,15] cor 3: [16,45]. Verificamos que nenhuma tríade (a,b,ab) com a · b = ab ≤ 45 fica monocromática: • Se a,b ∈ [2,3]: então ab ≥ 2 · 2 = 4 > 3, logo ab não está em [2,3]. • Se a,b ∈ [4,15]: então ab ≥ 4 · 4 = 16 > 15, logo ab não está em [4,15]. • Se a,b ∈ [16,45]: então ab ≥ 16·16 = 256 > 45, logo ab não pertence a {2,...,45}. Em todos os casos, (a,b,ab) usa cores diferentes (ou ab nem existe no intervalo). Portanto, 3 cores bastam. Combinando com a cota inferior, a45 = 3. Item (b): a2025 = 3, colorindo por blocos de potências de 2. Para n = 2025, intervalos simples como em (a) não funcionam: começando em [2,3], [4,15], chegamos a no máximo [16,255], que não cobre 2025. A ideia é reutilizar cores em blocos não consecutivos. Para cada x ∈ [2,2025], defina e(x) = ⌊log2x⌋, o expoente do “bloco diádico” de x. Assim 2e(x) ≤ x < 2e(x)+1. Por exemplo: x [2,3] [4,7] [8,15] [16,31] [32,63] ··· [1024,2047] e(x) 1 2 3 4 5 ··· 10 Propriedade-chave: se e(a) = e e e(b) = f, então e(ab) ∈ {e+f,e+f+1} (pois 2e+f ≤ ab < 2e+f+2). Particionamos os expoentes {1,2,...,10} em três classes: A = {1,4,10}, B = {2,3,9}, C = {5,6,7,8}. Colorimos x com a cor da classe de e(x). A coloração é: cor 1: [2,4) ∪ [16,32) ∪ [1024,2025], cor 2: [4,16) ∪ [512,1024), cor 3: [32,512). Verificação: para que uma tríade (a,b,ab) fosse monocromática, precisaríamos que todos três pertençam à mesma classe de expoentes. Mas isso exigiria e,f,e + f ∈ mesma classe (ou ambos ∈ mesma classe). Conferindo manualmente: nenhuma classe tem essa propriedade (por exemplo, 1+4 = 5 ∈/ A, 2+3 = 5 ∈/ B, etc.). Logo não existe tríade monocromática, e 3 cores bastam até n = 2047. Combinando com a cota inferior, a2025 = 3. Resposta: (a) a45 = 3; (b) a2025 = 3.