22/04/2019, 11:02:09 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Collar tricolor  (Leído 742 veces)
0 Usuarios y 1 Visitante están viendo este tema.
martiniano
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 721


Ver Perfil
« : 14/01/2019, 07:23:51 am »

Hola chicos. A ver si me podéis echar un cable con este enunciado, que llevo unos días con él en la cabeza y no llego a nada definitivo.

¿De cuántas maneras diferentes se pueden ensartar 99 cuentas de tres colores diferentes (azul, rojo y verde) en una cuerda de manera que haya como mínimo tres seguidas del mismo color?

A lo más que he llegado ha sido a ver que esto es lo mismo que tres veces el número de cadenas ternarias (con sólo ceros, unos y doses) de 98 caracteres con dos ceros seguidos.

Es decir, me preocupo de los cambios de color que hay al pasar de una bola a la siguiente y en la cadena pongo:

Un cero si no hay cambio de color.
Un uno si cambio de rojo a verde, de verde a azul o de azul a rojo.
Un dos si hago otro cambio.

Parece que esto simplifica el problema pero tampoco estoy seguro.

Un saludo y gracias a todos de antemano.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 44.093


Ver Perfil
« Respuesta #1 : 14/01/2019, 07:59:16 am »

Hola

 Antes de nada. ¿En qué contexto te ha surgido el problema?
 
 El mero hecho de contar collares distintos de longitud [texx]n[/texx] y dada usando [texx]k[/texx] cuentas no es tan obvio, por el hecho de ser circular cerrado el collar:

https://en.wikipedia.org/wiki/Necklace_(combinatorics)

Saludos.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 44.093


Ver Perfil
« Respuesta #2 : 14/01/2019, 08:15:39 am »

Hola

 Ahora que lo releeo no se si me dejé llevar por el título:

Cita
¿De cuántas maneras diferentes se pueden ensartar 99 cuentas de tres colores diferentes (azul, rojo y verde) en una cuerda de manera que haya como mínimo tres seguidas del mismo color?

 ¿Cuerda o collar? Es decir, ¿circular o lineal?.

Saludos.
En línea
martiniano
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 721


Ver Perfil
« Respuesta #3 : 14/01/2019, 08:24:40 am »

Hola Luis, gracias por tu respuesta.

El ejercicio es un apartado de un problema que han propuesto en un tema llamado combinatoria que es uno de los temas de una asignatura llamada matemática discreta en la carrera de informática. En la teoría se explican variaciones, permutaciones y combinaciones con y sin repetición y números de Stirling.

El problema pregunta por las maneras en las que se pueden ensartar cuentas en un collar pero abierto por sus extremos, es decir, como si fuera una cuerda lineal. ¿Mejora esto la esperanza de conseguir una solución?

Saludos y gracias.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 44.093


Ver Perfil
« Respuesta #4 : 14/01/2019, 08:42:16 am »

Hola

El problema pregunta por las maneras en las que se pueden ensartar cuentas en un collar pero abierto por sus extremos, es decir, como si fuera una cuerda lineal. ¿Mejora esto la esperanza de conseguir una solución?

Si, mucho.  :cara_de_queso:

Puedes contar las formas de ensartar las cuentas de forma que a lo sumo haya dos seguidas del mismo color y restárselas del total.

Ahora si llamas [texx]f(n)[/texx] al número de formas de colocar [texx]n[/texx] cuentras de tres colores con a lo sumo dos seguidas del mismo color tienes la siguiente ecuación de recurrencia:

[texx]f(n)=2f(n-1)+2f(n-2)[/texx]

Se basa el lo siguiente. Distinguimos dos tipos de collares:

- El que comienza con una sola cuenta de un mismo color (la siguiente distinta). Se construye tomando un collar de longitud de [texx]n-1[/texx] con a lo sumo dos seguidas del mismo color y le añadimos al principio una  cuenta de color distinto a la primera del collar de longitud [texx]n-1[/texx] (hay dos posibilidades).

- El que comienza con DOS cuentas de un mismo color (la siguiente distinta). Se construye tomando un collar de longitud de [texx]n-2[/texx] con a lo sumo dos seguidas del mismo color y le añadimos al principio DOS  cuentas de color distinto a la primera del collar de longitud [texx]n-2[/texx] (hay dos posibilidades).

La ecuación de recurrencia se resuelve de manera estandar.

Saludos.
En línea
martiniano
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 721


Ver Perfil
« Respuesta #5 : 14/01/2019, 10:48:34 am »

Hola. Gracias otra vez, Luis.

Ahora si llamas [texx]f(n)[/texx] al número de formas de colocar [texx]n[/texx] cuentras de tres colores con a lo sumo dos seguidas del mismo color tienes la siguiente ecuación de recurrencia:

[texx]f(n)=2f(n-1)+2f(n-2)[/texx]

Se basa el lo siguiente. Distinguimos dos tipos de collares:

- El que comienza con una sola cuenta de un mismo color (la siguiente distinta). Se construye tomando un collar de longitud de [texx]n-1[/texx] con a lo sumo dos seguidas del mismo color y le añadimos al principio una  cuenta de color distinto a la primera del collar de longitud [texx]n-1[/texx] (hay dos posibilidades).

- El que comienza con DOS cuentas de un mismo color (la siguiente distinta). Se construye tomando un collar de longitud de [texx]n-2[/texx] con a lo sumo dos seguidas del mismo color y le añadimos al principio DOS  cuentas de color distinto a la primera del collar de longitud [texx]n-2[/texx] (hay dos posibilidades).

¡Buena idea lo de la ecuación de recurrencia! Aunque lo de hallar el término general de relaciones de recurrencia lineales se escapa al temario de la asignatura, pero bueno. Tal vez se les halla traspapelado el enunciado.

Lo he hecho a ver si viendo la expresión resultante conseguía un argumento sencillo a base de combinaciones, variaciones y cosas de esas, pero me parece que va a ser que no. He impuesto las condiciones iniciales:

[texx]f(2)=3^2=9[/texx] (el número total de cadenas de dos cuentas)
[texx]f(3)=3^3-3=24[/texx] (el número total de cadenas de tres cuentas menos las tres cadenas que tienen todas las cuentas iguales)

Después de hacer cuentas me sale:

[texx]f(n)=\displaystyle\frac{3}{2}\displaystyle\sum_{k=0}^n[/texx][texx]\left(\displaystyle\binom{n}{k}\cdot{}3^{E\left(\displaystyle\frac{k}{2}\right)}\right)[/texx]

Donde [texx]E(x)[/texx] significa parte entera de [texx]x[/texx].

Llegados a este punto es cuando pienso que ha habido un error proponiendo esto en esta asignatura. Ciertamente, lo de dentro del sumatorio se puede ver como un producto de una combinación por una variación sin repetición un tanto estrambótica, pero creo que es una idea demasiado enrevesada para lo que andan haciendo.

Saludos  :sonrisa:
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!