Dicas dos problemas:
- Veja o que acontece quando temos um ciclo
- Se temos um grafo com $$2n$$ vértices, prove que podemos dividir ele em dois grafos de $$n$$ vértices, e juntá-los com apenas uma cor a mais.
- Seja $$2m$$ o maior clique do grafo.Divida o grafo em dois outros grafos $$A, B$$, onde o maior clique de $$A$$ tem tamanho $$2m$$. Enquanto o maior clique de $$A$$ for maior que o maior clique de $$B$$, passe um vértice de $$A$$ para $$B$$.
- Primeiro troque $$1776$$ por $$a$$ e $$2016$$ por $$b$$, e vamos usar apenas o fato de que $$a < b$$. Veja que os conjuntos históricos são da forma $$ \{ x, x+a, x+a+b \} $$ e $$ \{ x, x+b, x+a+b \}$$. Agora, tente montar o algoritmo guloso onde sempre pegamos o menor número que ainda não está num conjunto, e colocamos ele, e tente provar que esse algoritmo sempre funciona.
- Tente fazer um algoritmo indutivo, retirando uma folha de $$T$$.
- Veja que podemos mudar a ordem das colunas sem nenhum problema, então, ordene-as pelos elementos da primeira linha em ordem crescente. Então, prove que o seguinte algoritmo funciona: Começando pelo primeiro elemento, vá escolhendo os elementos de cima, até chegar num $$a_k$$ de modo que a soma atual é menor que $$\frac{n+1}{4}$$ e a soma atual mais $$a_k$$ é maior. A partir de $$a_k$$, pegue os elementos de baixo.
- Veja que $$1 \le i-a_i \le n$$. Construa um grafo que leva $$i$$ para $$i-a_i$$. Prove que se o grafo tem um ciclo, o problema acabou, e ache esse ciclo.