Iniciante
Observe que:
n \Leftrightarrow nk-k^2+n-k>n \Leftrightarrow nk-k^2-k>0" /> (como 0" />) 0 \Leftrightarrow n>k+1" />
O que é verdade, pois .
Intermediário
Considere as expressões abaixo:
Temos que e por :
Logo .
Avançado
Veja a soma de todos os segmentos. Agora pegue o pareamento que possui a menor soma possível e suponha que ele possua dois segmentos que se cortam, digamos que e se cortando em , pela desigualdade triangular:
- No triângulo temos AD" />;
- No triângulo temos BC" />.
Portanto AD + BC" /> e a soma dos segmentos diminuí ao trocarmos e por e e logo o pareamento que possui soma mínima não pode ter dois segmentos que se cortem, se não por absurdo sempre haverá um pareamento com soma menor que a mínima. Logo existe um pareamento em que todos os segmentos não se cortam.