Olimpiada Nacional de Kazajistán 2015 Problema 5
5 Un árbol binario completo consta de $n+1$ niveles, donde de cada vértice salen dos aristas hacia abajo y una arista proviene de arriba (el vértice superior del nivel $1$ no tiene arista entrante, y los vértices del último nivel $(n+1)$ - ésimo no tienen aristas salientes). En la figura siguiente se da un ejemplo con $n=3$ . ¿De cuántas maneras se pueden colorear las aristas de este árbol con $2^{n}$ colores dados (cada arista se colorea con un color) de modo que, para cada color, todas las aristas de ese color formen un camino desde algún vértice hasta un vértice del último nivel? (Un camino es una sucesión de vértices en la que cada par consecutivo está unido por una arista, y cada vértice siguiente se encuentra en un nivel inferior.) [asy] size(6cm); real H=0; int n=3, k=0, l=1; while(k<n+1){ for(int i=2^k; i<2^(k+1); ++i){ while(k>l-1){ if(floor(i/2^(l-1))%2==0){ H=H-0.5^l;} else{ H=H+0.5^l;} ++l;} dot((H,-k/3)); if(k!=n){ draw((H-0.5^l,-(k+1)/3)--(H,-k/3)--(H+0.5^l,-(k+1)/3));} l=1; H=0;} ++k;} [/asy]
0
0
Inicia sesión para agregar soluciones y pistas