Elegir vértices

Elegir vértices

UNREAD_POSTpor Vladislao » Dom 05 Mar, 2017 8:35 pm

Determinar de cuántas formas distintas se pueden elegir $k$ vértices de un $n$-ágono regular de modo que entre los elegidos no haya dos adyacentes.
Sea $\theta = 1,3063778838...$ Para todo entero positivo $k$ se cumple que $\left\lfloor \theta^{3^k}\right\rfloor$ es un número primo.
Avatar de Usuario
Vladislao
 
Mensajes: 768
Registrado: Mar 28 Dic, 2010 3:26 pm
Ubicación: Córdoba
Medals: 5
Colaborador OFO - Jurado OFO - Jurado FOFO 6 años - Jurado
OFO - Jurado
Nivel: Exolímpico

Re: Elegir vértices

UNREAD_POSTpor Emerson Soriano » Lun 06 Mar, 2017 2:08 am

Un buen hint.
Spoiler: Mostrar
Enumeremos los vértices con los números del $1$ al $n$ en sentido horario. Supongamos que los vértices escogidos son los que tienen etiquetas $x_1$, $x_2$, ... , $x_k$, en sentido horario, y sea $d_i$ el número de vértices que se encuentran entre los vértices $x_i$ y $x_{i+1}$, sin considerarlos a ellos, con $x_{k+1}=x_1$. Para que la elección sea la pedida debe ocurrir que $d_i\geq 1$. Además, $d_1+d_2+\cdots +d_k=n-k$. Por biyecciones sabemos que el número de soluciones es $\binom{n-k-1}{k-1}$.
Avatar de Usuario
Emerson Soriano
 
Mensajes: 698
Registrado: Mié 23 Jul, 2014 10:39 am
Medals: 3
OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata


Volver a Combinatoria

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado