Exemplo (Cone Sul 2003)
Editar
Seja $ n=3k+1 $, onde $ k $ é um inteiro, $ k \geq 1 $. Constrói-se um arranjo triangular de lado $ n $a ftermineormad por círculos de mesmo raio como o mostrado na figura para $ n=7 $.
Determinar, para cada $ k $, o maior número de círculos que podem ser coloridos de vermelho de tal modo que não existam dois círculos vermelhos tangentes entre si.
Solução: Para cada $ k $, considere $ a_k $ o maior número de círculos que podem ser coloridos de vermelho de tal modo que não existam dois círculos vermelhos tangentes entre si.
A ideia aqui é escrever uma desigualdade envolvendo $ a_{k+1} $ e $ a_k $. Para isto, devemos entender a diferença entre um triângulo de lados $ 3k+1 $ e $ 3(k+1)+1 $. E diferença entre eles são as três últimas linhas deste último triângulo.
Vamos dividir em casos.
1º Caso: $ k $ é par.
Aqui podemos escrever $ k=2k_0 $, com $ k_0 $ inteiro. Aqui $ n=6k_0+1 $. Vejamos as três últimas linhas do triângulo de lado $ 3(k+1)+1 $.
Vamos dividir estas três linhas da seguinte forma: $ \frac{3k+2}{2} $ peças do tipo $ 1 $ e uma peça do tipo $ 2 $.
Ou seja, Observe que cada peça do tipo $ 1 $ tem no máximo $ 2 $ círculos pintados, enquanto as peças do tipo $ 2 $ tem no máximo $ 1 $ círculo pintado. Desta forma,
$ a_{k+1} \leq a_k + 2(\frac{3k+2}{2})+1 = a_k+3(k+1). $
2º Caso: $ k $ é ímpar.
