==include(page="agm2016/solutii/pscarb")==

Solutie PScArb
 
Nu exista solutie pentru K > 2 si vom demonstra asta. Fie un nod aleator care nu e frunza si il vom considera radacina. Presupunem ca radacina nu e colorata R (celalalt caz se trateaza analog). Notam 3 frunze cu a, b si c. Fie R[x] = numarul de noduri colorate R de la radacina pana la nodul x. Daca R[a] + R[b] si R[a] + R[c] sunt impare atunci R[b] + R[c] + 2 * R[a] e par, deci si R[b] + R[c] e par. Deci, nu exista solutie.
 
Ramane cazul K = 2. In acest caz, arborele va fi un lant. Deoarece fiecare dintre cele 3 culori trebuie sa apara de un numar impar de ori, exista solutie doar daca N este impar. O posibila colorare este RGBBB...