Alfa-barras
León-Sotelo
de igual tamaño l. Tenemos n barras y las utilizamos todas.¿Cuantas
palabras diferentes podemos escribir?.Aplicación para n=12
Saludos
León-Sotelo
jhn...@gmail.com
x(1)=1, x(2)=3,
y si n>2, x(n) = x(n-1) + 2x(n-2)
solución:
x(n) = ((-1)^n + 2^{n+1})/3
x(12) = (1 + 2^15)/3 = 10923.
Saludos,
jhn
Ignacio Larrosa Cañestro
x(12) = (1 + 2^13)/3 = 2731
--
Saludos,
Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUIT...@mundo-r.com
jhn...@gmail.com
<ilarrosaQUITARMAYUSCU...@mundo-r.com> wrote:
Correcto!
jhn
Marko Riedel
Suponese que cada palabra representa un numero en el sistema de numeración
romana, es decir, que las letras son cifras romanas.
¿Entonces, cual es el valor esperado de una palabra de n barras (visto como
número)?
Salve. ;-)
Ojo: XX = VVVV etc.
--
+-------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, markor...@yahoo.de |
| http://www.geocities.com/markoriedelde/index.html |
+-------------------------------------------------------------+
Marko Riedel
> "León-Sotelo" <francisc...@gmail.com> writes:
>
> > Un alfabeto se compone de tres letras I,X,V que se escriben con barras
> > de igual tamaño l. Tenemos n barras y las utilizamos todas.¿Cuantas
> > palabras diferentes podemos escribir?.Aplicación para n=12
> >
> > Saludos
> > León-Sotelo
>
> Suponese que cada palabra representa un numero en el sistema de numeración
> romana, es decir, que las letras son cifras romanas.
>
> ¿Entonces, cual es el valor esperado de una palabra de n barras (visto como
> número)?
>
> Salve. ;-)
>
> Ojo: XX = VVVV etc.
>
Lenguas extranjeras ... supongo que ha de ser "vist_a_ como número".
Marko Riedel
> Marko Riedel <markor...@yahoo.de> writes:
>
> > "León-Sotelo" <francisc...@gmail.com> writes:
> >
> > > Un alfabeto se compone de tres letras I,X,V que se escriben con barras
> > > de igual tamaño l. Tenemos n barras y las utilizamos todas.¿Cuantas
> > > palabras diferentes podemos escribir?.Aplicación para n=12
> > >
> > > Saludos
> > > León-Sotelo
> >
> > Suponese que cada palabra representa un numero en el sistema de numeración
> > romana, es decir, que las letras son cifras romanas.
> >
> > ¿Entonces, cual es el valor esperado de una palabra de n barras (visto como
> > número)?
> >
> > Salve. ;-)
> >
> > Ojo: XX = VVVV etc.
> >
>
Me refiero a un sistema de numeración simplificado donde el valor de una
palabra es la suma de sus cifras. Sería todo un reto solucionar el problema
para el verdadero sistema de numeración romana, incluyendo el caso donde se
resta el valor de una cifra del valor de la cifra que la sigue.
Un saludo.
jhn...@gmail.com
> Marko Riedel <markoriede...@yahoo.de> writes:
> > Marko Riedel <markoriede...@yahoo.de> writes:
>
> > > "León-Sotelo" <francisco.lsot...@gmail.com> writes:
>
> > > > Un alfabeto se compone de tres letras I,X,V que se escriben con barras
> > > > de igual tamaño l. Tenemos n barras y las utilizamos todas.¿Cuantas
> > > > palabras diferentes podemos escribir?.Aplicación para n=12
>
> > > > Saludos
> > > > León-Sotelo
>
> > > Suponese que cada palabra representa un numero en el sistema de numeración
> > > romana, es decir, que las letras son cifras romanas.
>
> > > ¿Entonces, cual es el valor esperado de una palabra de n barras (visto como
> > > número)?
>
> > > Salve. ;-)
>
> > > Ojo: XX = VVVV etc.
>
> Me refiero a un sistema de numeración simplificado donde el valor de una
> palabra es la suma de sus cifras. Sería todo un reto solucionar el problema
> para el verdadero sistema de numeración romana, incluyendo el caso donde se
> resta el valor de una cifra del valor de la cifra que la sigue.
Si v(n) es el valor esperado entonces
v(1) = 1, v(2) = (2+5+10)/3 = 17/3,
y si n>2,
v(n) = (1+v(n-1))/3 + (5+v(n-2))/3 + (10+v(n-2))/3,
v(n) = (v(n-1) + 2v(n-2))/3 + 16/3
sol. gral. A + B(-2/3)^n + (16/5)n
y usando las condiciones iniciales queda
v(n) = (33/25)((-2/3)^n - 1) + (16/5)n
Saludos,
jhn
Marko Riedel
Bueno, y ¿que tal la varianza y los primeros cinco momentos factoriales?
;-)
Luis
<jhn...@gmail.com> escribió en el mensaje
news:d702c85c-aac9-4e0c...@d70g2000hsb.googlegroups.com...
Saludos,
jhn
Muy bonito. ¿ Puedes explicar brevemente cómo has dado con la recurrencia ?
Yo he intentado encontrar un orden separando el caso "n" par y "n" impar,
pero no acabo de dar con ello.
Ahora la pista te la pido yo.
Saludos,
jhn...@gmail.com
> <jhni...@gmail.com> escribió en el mensajenews:d702c85c-aac9-4e0c...@d70g2000hsb.googlegroups.com...
Las palabras que usan n barras y comienzan con I son x(n-1), porque
quedan n-1 barras para completar la palabra. De igual modo las que
comienzan con V son x(n-2), y las que comienzan con X son también
x(n-2). Por tanto
x(n) = x(n-1) + x(n-2)+ x(n-2)
= x(n-1) + 2x(n-2).
Por cierto, como dijo Ignacio, calculé x(14) en vez de x(12), lo que
se pedía es
x(12) = (1 + 2^13)/3 = 2731.
jhn
León-Sotelo
>
> - Mostrar texto de la cita -
Aunque la forma mas elegante desde mi punto de vista es la que te ha
enviado jhn este problema es de las Olimpadas catalanas de Diciembre
de 2007 y aqui tienes dos soluciones mas:
http://www.xtec.cat/recursos/mates/aqui/olimp44/olimp44.pdf
Saludos
León-Sotelo
Marko Riedel
Estimado señor JHN,
le pido ayuda a Vd. con algunas dudas que tengo con este problema. Primero,
¿no le parece muy raro que el término dominante de su valor esperado sea
lineal? Algo no cuadra, porque al mirar la recurrencia se ve que la solución
debe tener un crecimiento exponencial.
Usando la funcion generatriz G(z, u), donde el exponente de z es el número de
barras y el exponente de u, el valor de la palabra, obtengo la siguiente
ecuación:
G-u*z-(u^2+u^5+u^10)*z^2 = u*z*(G-u*z) + (u^5+u^10)*z^2*G.
cuya solución es
4 9
u z (1 + z u + z u )
G(z, u) = - -------------------------
2 5 2 10
-1 + u z + z u + z u
Luego d/dz G(z, u)_{u=1} da
17 14 31 62
------------ + ---------- - ---------- + ------------.
2 2 27 (z + 1) 27 (2 z - 1)
9 (2 z - 1) 9 (z + 1)
Finalmente, el valor esperado es
/17 n 11\ n /14 n 11\ n
|---- - --| 2 + |---- + --| (-1)
\ 9 27/ \ 9 27/
Me gustaría saber dónde está el error, si error hay.
Marko Riedel
Marko Riedel
Hola de nuevo,
me doy cuenta ahora que olvidé el último paso de esta computación, es decir,
calcular el número de palabras. Dado que no se trata de una función generatriz
probabilística, el valor esperado es
[z^n] d/du G(z, u)_{u=1} / [z^n] G(z, u)_{u=1}
donde [z^n] G(z, u)_{u=1} es el numero de palabras de n barras.
El valor de G(z, u)_{u=1} es
z (1 + 2 z)
- -------------
2
-1 + z + 2 z
o sea
1 2
-1 + --------- - -----------.
3 (z + 1) 3 (2 z - 1)
Entonces el número de palabras es (n>=1)
2/3 2^n + 1/3 (-1)^n,
que es el resultado que obtuvo Vd.
Finalmente, para el valor esperado obtenemos
/17 n 11\ n /14 n 11\ n
|---- - --| 2 + |---- + --| (-1)
\ 9 27/ \ 9 27/
E(n) = ----------------------------------.
n n
2 2 (-1)
---- + -----
3 3
De esto se deduce que el valor esperado es de hecho lineal asintóticamente:
E(n) ~ 17/6 n.
jhn...@gmail.com
Por el contrario, lo razonable es que sea
asintóticamente lineal en n, ya que una palabra
con n barras tiene en promedio 3n/5 caracteres,
y su valor andará cerca entonces de (3n/5)17/3 = 17n/5. Esto no es
exacto porque los caracteres I, V y X no son equiprobables.
Mi cálculo adolece precisamente de ese error, supuse que el primer
caracter podía ser I, V o X con igual probabilidad, y no es así. La
probabilidad de que sea I es x(n-1)/x(n), la de que sea V es
x(n-2)/x(n) y la de que sea X lo mismo. La recurrencia
correcta para el valor esperado es entonces
v(n) = (x(n-1)/x(n))(1 + v(n-1))
+ (x(n-2)/x(n))(5 + v(n-2)) + (x(n-2)/x(n))(10 + v(n-2))
= (x(n-1)/x(n))(1 + v(n-1)) + (x(n-2)/x(n))(15 + 2v(n-2))
o bien
v(n)x(n) = x(n-1)(1 + v(n-1)) + x(n-2)(15 + 2v(n-2))
= x(n-1)v(n-1) + 2x(n-2)v(n-2) + x(n-1) + 15x(n-2)
= x(n-1)v(n-1) + 2x(n-2)v(n-2) + (14(-1)^n + 17 2^{n-1})/3,
cuya solución es
v(n)x(n) = (14(-1)^n + 17 2^n)n/9 + (11/27)((-1)^n - 2^n)
y finalmente
v(n) = ((14(-1)^n + 17 2^n)n/3 + (11/9)((-1)^n - 2^n))/((-1)^n - 2^(n
+1))
que asintóticamente es 17n/6 - 11/18.
jhn
>
> Usando la funcion generatriz G(z, u), donde el exponente de z es el número de
> barras y el exponente de u, el valor de la palabra, obtengo la siguiente
> ecuación:
>
> G-u*z-(u^2+u^5+u^10)*z^2 = u*z*(G-u*z) + (u^5+u^10)*z^2*G.
>
> cuya solución es
>
> 4 9
> u z (1 + z u + z u )
> G(z, u) = - -------------------------
> 2 5 2 10
> -1 + u z + z u + z u
>
> Luego d/dz G(z, u)_{u=1} da
>
> 17 14 31 62
> ------------ + ---------- - ---------- + ------------.
> 2 2 27 (z + 1) 27 (2 z - 1)
> 9 (2 z - 1) 9 (z + 1)
>
> Finalmente, el valor esperado es
>
> /17 n 11\ n /14 n 11\ n
> |---- - --| 2 + |---- + --| (-1)
> \ 9 27/ \ 9 27/
>
> Me gustaría saber dónde está el error, si error hay.
>
> Un saludo.
>
> --
> +-------------------------------------------------------------+
> | Marko Riedel, EDV Neue Arbeit gGmbH, markoriede...@yahoo.de |
> |http://www.geocities.com/markoriedelde/index.html |
> +-------------------------------------------------------------+- Ocultar texto de la cita -
Marko Riedel
Me alegra que hayamos podido encontrar la misma solución por dos métodos
diferentes. Gracias por la explicación de por qué el valor esperado tiene que
ser lineal asintóticamente.
Un saludo.
--
+-------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, markor...@yahoo.de |
| http://www.geocities.com/markoriedelde/index.html |
+-------------------------------------------------------------+