Category Archive

You are currently browsing the category archive for the 'Combinatória' category.

Princípio de indução matemática aplicado a uma relação combinatória

Março 15, 2009 in Combinatória, Indução matemática, Matemática, Problema, Teoria dos Números | Tags: Matemática, Problema | Leave a comment

Prove que existe apenas um número natural que verifica a relação

$^{n\!}C_{n-2}=2^{n-2}-1$

Sugestão: utilize o princípio de indução para provar que a relação não é satisfeita por nenhum natural superior a seis.

Esta ideia é devida a Vishal Lama (neste comentário em inglês).

Exercícios algébricos simples de Combinatória

Fevereiro 28, 2009 in Combinatória, Exercício, Matemática, Matemática-secundário, Problema | Tags: Exercícios, Matemática, Matemática-secundário, Problema | 2 comments

1. Diga se existe algum número natural menor que $10$ tal que:

$^{n\!}C_{n-2}=2^{n-2}-1.$

Justifique.

2. Prove que

$^{n\!}C_{k}=\dfrac{n-k+1}{k}\times ^{n\!}C_{k-1}$

3. Determine $n$ de modo a que se tenha

$^{n+3\!}C_{n}-^{n+2\!}C_{n-1}=15(n+1)$

4. Determine $n$ de modo a que se tenha

$^{n\!}C_{2}=136$

Resolução

A fórmula das combinações $^{n\!}C_{k}$ é $^{n\!}C_{k}=\dfrac{n!}{k!(n-k)!}$

1. Neste caso tem-se

$^{n\!}C_{n-2}=\dfrac{n!}{(n-2)!(n-(n-2))!}=\dfrac{n(n-1)}{2}$

Então

$\dfrac{n(n-1)}{2}=2^{n-2}-1$

é equivalente a

$n(n-1)=2^{n-1}-2\Leftrightarrow n^{2}-n=2^{n-1}-2\Leftrightarrow n^{2}=2^{n-1}-2+n$

Por tentativas chegamos à solução inteira $n=6$ (por sinal a única). Os primeiros casos, começando em $n=9$ e continuando no sentido descendente são:

$9^{2}=81$ e $2^{9-1}-2+9=263$

$8^{2}=64$ e $2^{8-1}-2+8=134$

$7^{2}=49$ e $2^{7-1}-2+7=69$

que são valores diferentes. Mas

$6^{2}=36$ e $2^{6-1}-2+6=36$

$6^{2}=2^{6-1}-2+6=36$

Verificação:

$^{n\!}C_{n-2}=2^{n-2}-1$

$^{6\!}C_{6-2}=\dfrac{6(6-1)}{2}=15$

$2^{6-2}-1=15$

Os restantes, também diferentes, são

$5^{2}=25$ e $2^{5-1}-2+5=19$

$4^{2}=16$ e $2^{4-1}-2+4=10$

$3^{2}=9$ e $2^{3-1}-2+3=5$

$2^{2}=4$ e $2^{2-1}-2+2=2$

$1^{2}=1$ e $2^{1-1}-2+1=0$

2. Como

$^{n\!}C_{k}=\dfrac{n!}{k!(n-k)!}$

$^{n\!}C_{k-1}=\dfrac{n!}{(k-1)!(n-(k-1)!}=\dfrac{n!}{(k-1)!(n-k+1)!}$

vem

$\dfrac{^{n\!}C_{k}}{^{n\!}C_{k-1}}=\dfrac{\dfrac{n!}{k!(n-k)!}}{\dfrac{n!}{(k-1)!(n-k+1)!}}$

$=\dfrac{(k-1)!(n-k+1)(n-k)!}{k(k-1)!(n-k)!}=\dfrac{n-k+1}{k}$

Logo

$^{n\!}C_{k}=\dfrac{n-k+1}{k}\times ^{n\!}C_{k-1}$

3. Como

$^{n+3\!}C_{n}=\dfrac{(n+3)!}{n!(n+2-n)!}$

$=\dfrac{(n+3)(n+2)(n+1)}{2!}=\dfrac{(n+3)(n+2)(n+1)}{2}$

$^{n+2\!}C_{n-1}=\dfrac{(n+2)!}{(n-1)!(n+2-(n-1))!}=\dfrac{(n+2)(n+1)n}{6}$

a igualdade indicada é equivalente, sucessivamente, a

$\dfrac{(n+3)(n+2)(n+1)}{2}-\dfrac{(n+2)(n+1)n}{6}=15(n+1)$

$3(n+3)(n+2)-(n+2)n=90$

$2n^{2}+13n-72=0$

As duas soluções são:

$\dfrac{-13+\sqrt{745}}{4},\dfrac{-13-\sqrt{745}}{4}$

Como nenhuma é inteira, não tem solução nos naturais, pelo que não há nenhum valor de $n$ que verifique a condição indicada.

4. Como

$^{n\!}C_{2}=\dfrac{n!}{2!(n-2)!}=\dfrac{n(n-1)(n-2)!}{2\times 1\times (n-2)!}=\dfrac{n(n-1)}{2}$

$\dfrac{n(n-1)}{2}=136$

$\Leftrightarrow n(n-1)=2\times 136\Leftrightarrow n(n-1)=272\Leftrightarrow n^{2}-n-272=0$

A solução positiva é

$n=\dfrac{1+\sqrt{1+4\times 272}}{2}=17$

A negativa exclui-se por esse facto.

Verificação:

$^{17\!}C_{2}=\dfrac{17\times 16}{2}=136$ .

Observação de 1-3-2009: comentário suprimido.

Nota de 15-3-2008: nesta entrada pode ver um problema de nível um pouco mais avançado que prolonga o exercício 1 a todos os naturais, aproveitando o 1º. comentário.

Probabilidades do Euromilhões

Julho 23, 2008 in Combinatória, Exercício, Matemática, Matemática-secundário, Probabilidades, Problema | Tags: Exercícios, Matemática, Matemática-secundário, Problema | Leave a comment

O blogue A MATEMÁTICA ANDA POR AÍ publicou uma tabela onde se pode ler que as probabilidades de obter o 1º (5 números e 2 estrelas), 2º (5 números e 1 estrela) ou 3º (5 números e 0 estrelas) prémios são, respectivamente

$\dfrac{\dbinom{45}{0}\dbinom{5}{5}\dbinom{7}{0}\dbinom{2}{2}}{\dbinom{50}{5}\dbinom{9}{2}}$ ,

$\dfrac{\dbinom{45}{0}\dbinom{5}{5}\dbinom{7}{1}\dbinom{2}{1}}{\dbinom{50}{5}\dbinom{9}{2}}$

$\dfrac{\dbinom{45}{0}\dbinom{5}{5}\dbinom{7}{2}\dbinom{2}{0}}{\dbinom{50}{5}\dbinom{9}{2}}$ .

NOTAÇÃO: $\dbinom{p}{q}$ é o chamado coeficiente binomial que é, noutra notação, o mesmo que as combinações de $p$ , $q$ a $q$ : $^{p}C_{q}$

$\displaystyle\dbinom{p}{q}=^{p}C_{q}=\frac{p!}{q!\left( p-q\right) !}=\frac{p\left( p-1\right)\left( p-2\right) \cdots \left( p-q+1\right) }{p!}$

Verificação

O número total de casos possíveis $CP$ é dado pelo produto do número de casos possíveis relativamente à extracção dos cinco números ( $N$ ) pelo número de casos possíveis relativamente à das duas estrelas ( $E$ ). Ora, como podem sair cinco números em 50, sem interessar a ordem da extracção, há $N=\dbinom{50}{5}$ possibilidades distintas. Quanto às estrelas escolhem-se duas entre nove, pelo que $E=\dbinom{9}{2}$ .

$N=\dbinom{50}{5}=\dfrac{50\times 49\times 48\times 47\times 46}{5\times 4\times 3\times 2\times 1}=2118760$

$E=\dbinom{9}{2}=\dfrac{9\times 8}{2\times 1}=36$

conclui-se que o número de casos possíveis é

$CP=N\times E=\dbinom{50}{5}\times \dbinom{9}{2}=2118760\times 36=76275360$

Sobre o de casos favoráveis, vejamos o caso do 1.º prémio. O apostador deve acertar em 5 números e 2 estrelas. Se
separarmos o conjunto dos números 1 a 50 em dois conjuntos, $A$ o do 5 números que foram extraídos e $B$ o dos 45 restantes, o apostador deverá ter acertado em todos os números de $A$ e em nenhum de $B.$ Há apenas uma forma de acertar em todos os números de $A$ , que se pode exprimir por $\dbinom{5}{5}=1$ . E igualmente uma única forma de não acertar em é então

$CFN=\dbinom{5}{5}\times \dbinom{45}{0}=1\times 1=1$

Raciocinando de forma idêntica em relação às estrelas, chegamos ao número de casos favoráveis de acertos nas estrelas

$CFE=\dbinom{2}{2}\times \dbinom{7}{0}=1$

Assim o número de casos favoráveis de acertos nos números e nas estrelas é apenas um:

$CF=CFN\times CFE=\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{2}\times\dbinom{7}{0}=1$

A probabilidade respectiva é pois

$P=\dfrac{CF}{CP}=\dfrac{\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{2}\times \dbinom{7}{0}}{\dbinom{50}{5}\times \dbinom{9}{2}}=\dfrac{1}{76275360}$

Em relação ao 2.º prémio, mantém-se o número de 5 acertos nos números e em vez de 2 o apostador passa a acertar em 1 estrela. Do conjunto de 2 estrelas que saíram acerta em uma e em outra das restantes 7:

$CFE=\dbinom{2}{1}\times \dbinom{7}{1}=14$

Os casos favoráveis passam a

$CF=CFN\times CFE=\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{1}\times\dbinom{7}{1}=14$

e a probabilidade a

$P=\dfrac{CF}{CP}=\dfrac{\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{1}\times \dbinom{7}{1}}{\dbinom{50}{5}\times \dbinom{9}{2}}=\dfrac{14}{76275360}$

Finalmente, no 3.º prémio o apostador acerta em todos os números, mas em nenhuma estrela, ou seja as duas estrelas em que apostou fazem parte das 7 que não saíram, logo

$CFE=\dbinom{2}{0}\times \dbinom{7}{2}=1\times \dfrac{7\times 6}{2\times 1}=21$

O número de casos favoráveis passa a ser

$CF=CFN\times CFE=\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{0}\times \dbinom{7}{2}=21$

e a probabilidade

$P=\dfrac{CF}{CP}=\dfrac{\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{0}\times \dbinom{7}{2}}{\dbinom{50}{5}\times \dbinom{9}{2}}=\dfrac{21}{76275360}$ .

25-5-2009: corrigido erro no denominador das fórmulas e acrescentada verificação

Fórmulas de Apéry

Maio 16, 2008 in Combinatória, Exercício, Matemática, Problema, Teoria dos Números | Tags: Exercícios, Matemática, Problema | 2 comments

Prove as seguintes fórmulas

$\displaystyle\sum_{k=1}^{K}\dfrac{a_{1}a_{2}...a_{k-1}}{(x+a_{1})(x+a_{2})...(x+a_{k})}=\dfrac{1}{x}-\dfrac{a_{1}a_{2}...a_{K}}{x(x+a_{1})(x+a_{2})...(x+a_{K})}$
$\bigskip$
Caso particular para $x=n^{2}$ e $a_{k}=-k^{2}$
$\displaystyle\sum_{k=1}^{n-1}\dfrac{\left( -1\right) ^{k-1}\left( k-1\right) !^{2}}{\left( n^{2}-1^{2}\right) ...\left( n^{2}-k^{2}\right) }=\dfrac{1}{n^{2}}-\frac{\left( -1\right) ^{n-1}\left( n-1\right) !^{2}}{n^{2}\left( n^{2}-1^{2}\right) ...\left[ n^{2}-\left( n-1\right) ^{2}\right] }$

$\bigskip$
$\displaystyle\sum_{n=1}^{N}\displaystyle\sum_{k=1}^{n-1}(-1)^{k}\left( \varepsilon _{n,k}-\varepsilon_{n-1,k}\right) =2\left( \displaystyle\sum_{n=1}^{N}\dfrac{1}{n^{3}}-\dfrac{2\left( -1\right) ^{n-1}}{n^{3}\dbinom{2n}{n}}\right)$
em que
$\displaystyle\varepsilon _{n,k}=\dfrac{1}{k^{3}\dbinom{n}{k}\dbinom{n+k}{k}}$

$\bigskip$
$\displaystyle\sum_{n=1}^{N}\displaystyle\sum_{k=1}^{n-1}\left( -1\right) ^{k}\left( \varepsilon_{n,k}-\varepsilon _{n-1,k}\right)=\displaystyle\sum_{k=1}^{N}\displaystyle\sum_{n=k+1}^{N}\left( -1\right) ^{k}\left( \varepsilon _{n,k}-\varepsilon _{n-1,k}\right)=$ $=\displaystyle\sum_{k=1}^{N}\left( -1\right) ^{k}\left( \varepsilon _{N,k}-\varepsilon_{k,k}\right)$
$\bigskip$
$\displaystyle\sum_{k=1}^{N}\left( -1\right) ^{k}\left( \varepsilon _{N,k}-\varepsilon_{k,k}\right)=\displaystyle\sum_{k=1}^{N}\dfrac{\left( -1\right) ^{k}}{k^{3}\dbinom{N}{k}\dbinom{N+k}{k}}-\displaystyle\sum_{k=1}^{N}\dfrac{\left( -1\right) ^{k}}{k^{3}\dbinom{2k}{k}}$
$\bigskip$
$\displaystyle\sum_{n=1}^{N}\dfrac{1}{n^{3}}+\displaystyle\sum_{k=1}^{N}\dfrac{\left( -1\right) ^{k-1}}{2k^{3}\dbinom{N}{k}\dbinom{N+k}{k}}=$ $\dfrac{5}{2}\displaystyle\sum_{k=1}^{N}\frac{\left( -1\right) ^{k-1}}{k^{3}\dbinom{2k}{k}}$

Resolução: veja a secção 3 deste artigo de Alf van der Poorten

http://www.ift.uni.wroc.pl/~mwolf/Poorten_MI_195_0.pdf,

A proof that Euler Missed …

(também disponível aqui).

Probabilidades com cartas

Dezembro 14, 2007 in Combinatória, Exercício, Matemática, Matemática-secundário, Probabilidades, Problema | Tags: Matemática, Problema | 3 comments

De um baralho de 52 cartas, correctamente baralhado, tiram-se cartas à sorte. Calcular a probabilidade de ao extrair:

duas cartas serem ambas de Copas;
duas cartas serem uma Dama e um Valete;
três cartas serem todas de Ouros e entre elas figurar o Ás.

Respostas

1 / 17
8 / 663

Resolução do 3.

Há 13 Ouros no baralho, pelo que a probabilidade de sair um Ouro ao extrair uma carta é 13 / 52. Como ficam 51 cartas, ao extrair a 2ª carta, a probabilidade de ser um Ouro é 12 / 51; e na 3ª extracção 1 / 50, uma vez que só há um Ás de Ouro. Logo, a probabilidade será

$\displaystyle\frac{13}{52}\displaystyle\frac{12}{51}\displaystyle\frac{1}{50}=\displaystyle\frac{11}{11050}$

No entanto, o Ás poderá ser extraído na 1ª, 2ª ou 3ª tiragem. Por isso a probabilidade pedida é tripla da anterior:

$\displaystyle\frac{33}{11050}$ $\qquad\blacktriangleleft$

NOTA: A extracção de 3 cartas de uma só vez é equivalente a 3 tiragens sucessivas sem reposição.

	Eduardo Lazarini no Matemática, papel e caneta, e …
	mario dumbo hossi no Descobrir a Moeda Falsa
	Américo Tavares no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	anonimo no Dodecaedro e outros poliedros…
	Elias_Brasil no Probabilidades com cartas
	Pedro Cunha no Caderno
	Andrea no Matemática, papel e caneta, e …
	alessandro no Caderno

Category Archive

Princípio de indução matemática aplicado a uma relação combinatória

Exercícios algébricos simples de Combinatória

Probabilidades do Euromilhões

Fórmulas de Apéry

Probabilidades com cartas

Américo Tavares

Bem-vindo(a)!

Últimos Comentários e respostas

Arquivos

Últimos Artigos

Categorias (Temas)

Acompanhamento via RSS de Blogues com Matemática

… em português

A MATEMÁTICA ANDA POR AÍ

Disquisitiones Mathematicae

Geometria

morfismo

… não portugueses

Gaussianos

Gower’s Weblog

The Unapologetic Mathematician

Todd and Vishal’s blog

What’s new

Weblog de Pierre Bernard

Ligações (Links)

Matemática

Matemática/Computação

Matemática/Problemas

Matemática/Publicações, bibliotecas online

Meu blogue auxiliar

Outros: ciências, tecnologia e economia, etc.

N.º de Visualizações (início: Out. 2007)

Acompanhe este blogue via RSS

COMENTÁRIOS