Copa Matemática Europea 2023 Problema 3
3 Sea $n$ un entero positivo. Sea $B_n$ el conjunto de todas las cadenas binarias de longitud $n$. Para una cadena binaria $s_1\hdots s_n$, definimos su twist de la siguiente manera. Primero, contamos cuántos bloques de dígitos consecutivos tiene. Denotemos este número por $b$. Luego, reemplazamos $s_b$ con $1-s_b$. Se dice que una cadena $a$ es descendiente de $b$ si $a$ se puede obtener de $b$ mediante un número finito de twists. Un subconjunto de $B_n$ se llama dividido si no hay dos de sus miembros que tengan un descendiente común. Encuentra la cardinalidad máxima posible de un subconjunto dividido de $B_n$. Observación. Aquí hay un ejemplo de un twist: $101100 \rightarrow 101000$ porque $1\mid 0\mid 11\mid 00$ tiene $4$ bloques de dígitos consecutivos. Viktor Simjanoski
0
0
Inicia sesión para agregar soluciones y pistas