URGENTE!! Questão de Matemática Discreta
Enviado: 26 Mar 2009, 15:41
Esta é uma questão sobre modos de preencher um retângulo n x 2 (uma “caixa n x 2”) com n retângulos 2 x 1 iguais (“dominós”). Vamos usar uma notação com Hs e Vs para representar este preenchimentos:
M3={HV, VVV, VH} ? (não estão em ordem alfabética!)
|M3|=3
a) Diga quais são todos os modos de preencher caixas 1 x 2, 2 x 2, 3 x 2, 4 x 2 e 5 x 2 com dominós, listando estes modos em ordem alfabética; isto é, diga explicitamente quem são os conjuntos M1, M2, M3, M4, M5.
b) Descreva como obter Mn (com seus elementos listados em ordem alfabética!) se já sabemos M1, M2,..., Mn-1. Se quiser usar uma notação mais formal para os conjuntos e funções, use estes nomes:
P={p|p é uma palavra de comprimento finito formada só por Hs e Vs}
P*={p|p é uma palavra de comprimento finito > 0 formada só por Hs e Vs}
pl: P* ?P (“primeira letra”. Ex: pl(HV) = H)
r: P* ?P* (“resto”, ou “remove a primeira letra”. Ex: r(HV) = V)
c: P x P ?P (“concatena”. Ex: c(HH,VV) = HHVV)
c) Diga como obter |Mn| a partir de |M1|,|M2|,...,|Mn-1|. Calcule |M10|.
d) Diga quem é o “elemento número 40” de M10 – isto é, o elemento que aparece na quadragésima posição quando listamos os elementos de M10 em ordem alfabética. Mostre como encontrar o k-ésimo elemento de Mn por um processo recursivo.
e) Mostre que cada palavra de P* pertence exatamente a um Mn.. Encontre uma descrição para Mn da forma :
Mn = {p P|…}
E diga quantas palavras com 4 Hs existem em M10.
O que eu entendi até agora:
V = preenchimento com dominó na vertical (ocupa uma coluna e duas linhas)
H = preenchimento com dominós na horizontal (ocupa duas colunas e duas linhas)
Organização Colunas x Linhas
Então listei na ordem alfabética:
M1?1x2?{V} ?1 elemento
M2?2x2?{H,VV} ?2 elementos
M3?3x2?{HV, VH, VVV} ?3 elementos
M4?4x2?{HH, HVV, VHV, VVH, VVVV} ?5 elementos
M5?5x2?{HHV, HVH, HVVV, VHH, VHVV, VVHV, VVVH, VVVVV} ?8 elementos
M6?6x2 ? 13 elementos (só para efeito de teste, a questão pede para listar até M5)
Sendo assim ficou caracterizada uma subseqüência de Fibonacci:
F(n) = 1, se n = 1;
1, se n = 2;
F(n - 1) + F(n - 2), nos outros casos.
F ou Fib = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...}
Concluindo que |Mn| = Fib(n+1)
Na letra (b) é preciso descrever um padrão para formação das sequências na ordem alfabética, isso eu ainda não consegui, é necessário descrever este padrão para resolver o resto da questão.
Preciso de ajuda urgente para resolver esta questão, preciso entregar amanhã.
- Dominós.JPG (11.86 KiB) Exibido 537 vezes
|M3|=3
a) Diga quais são todos os modos de preencher caixas 1 x 2, 2 x 2, 3 x 2, 4 x 2 e 5 x 2 com dominós, listando estes modos em ordem alfabética; isto é, diga explicitamente quem são os conjuntos M1, M2, M3, M4, M5.
b) Descreva como obter Mn (com seus elementos listados em ordem alfabética!) se já sabemos M1, M2,..., Mn-1. Se quiser usar uma notação mais formal para os conjuntos e funções, use estes nomes:
P={p|p é uma palavra de comprimento finito formada só por Hs e Vs}
P*={p|p é uma palavra de comprimento finito > 0 formada só por Hs e Vs}
pl: P* ?P (“primeira letra”. Ex: pl(HV) = H)
r: P* ?P* (“resto”, ou “remove a primeira letra”. Ex: r(HV) = V)
c: P x P ?P (“concatena”. Ex: c(HH,VV) = HHVV)
c) Diga como obter |Mn| a partir de |M1|,|M2|,...,|Mn-1|. Calcule |M10|.
d) Diga quem é o “elemento número 40” de M10 – isto é, o elemento que aparece na quadragésima posição quando listamos os elementos de M10 em ordem alfabética. Mostre como encontrar o k-ésimo elemento de Mn por um processo recursivo.
e) Mostre que cada palavra de P* pertence exatamente a um Mn.. Encontre uma descrição para Mn da forma :
Mn = {p P|…}
E diga quantas palavras com 4 Hs existem em M10.
O que eu entendi até agora:
V = preenchimento com dominó na vertical (ocupa uma coluna e duas linhas)
H = preenchimento com dominós na horizontal (ocupa duas colunas e duas linhas)
Organização Colunas x Linhas
Então listei na ordem alfabética:
M1?1x2?{V} ?1 elemento
M2?2x2?{H,VV} ?2 elementos
M3?3x2?{HV, VH, VVV} ?3 elementos
M4?4x2?{HH, HVV, VHV, VVH, VVVV} ?5 elementos
M5?5x2?{HHV, HVH, HVVV, VHH, VHVV, VVHV, VVVH, VVVVV} ?8 elementos
M6?6x2 ? 13 elementos (só para efeito de teste, a questão pede para listar até M5)
Sendo assim ficou caracterizada uma subseqüência de Fibonacci:
F(n) = 1, se n = 1;
1, se n = 2;
F(n - 1) + F(n - 2), nos outros casos.
F ou Fib = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...}
Concluindo que |Mn| = Fib(n+1)
Na letra (b) é preciso descrever um padrão para formação das sequências na ordem alfabética, isso eu ainda não consegui, é necessário descrever este padrão para resolver o resto da questão.
Preciso de ajuda urgente para resolver esta questão, preciso entregar amanhã.