90
edits
Changes
no edit summary
==='''6. Computações e explorações'''===
=====1. (Projetos de computador) Dado um inteiro positivo “n”, encontre a probabilidade de selecionar seis inteiros do conjunto {<math>1, \cdots , n</math>} que foram mecânicamente selecionados em uma loteria. =====
Solução
Nós seguiremos o exemplo 4 no texto. O número total de maneiras de escolher 6 números de “n” números é <math>C(n, 6)</math>, que pode ser encontrado com o procedimento “numbcomb” no pacote “combinat”. Isso nos dá o número total de possibilidades, onde apenas uma irá vencer.
'''''Lottery2(49,6); '''''
'''''Lottery(30,3); '''''
=====2. Dados inteiros positivos “n” e “r”, liste todas as r-combinações, com repetições permitidas, do conjunto .=====
Solução
A função “choose” do Maple (no pacote “combinat”), vai listar todas as r-combinações de, mas sem repetições. Portanto nós não podemos usá-la diretamente. Entretanto, digamos que queremos todas as 2-combinações de, com repetições.
'''''happylist := [ happy $ 4]; '''''
'''''happyset := happy $ 4 ; '''''
=====3. Encontre o número de resultados possíveis em uma partida de dois times quando o vencedor é o primeiro time a ganhar 5 de 9, 6 de 11, 7 de 13 ou 8 de 15 jogos.=====
Solução
Nossa solução vai usar o procedimento Maple chamado “permute” para computar o número total de maneiras que um torneio de jogos pode ser jogado. Vamos começar construindo duas listas que observa como cada um dos dois times pode ganhar. Nós iremos atribuir as duas do time 1 vencendo o torneio sem nenhuma derrota, e o time 2 vencendo o torneio sem nenhuma derrota. A cada iteração do loop principal do algoritmo, vamos computar as permutações possíveis de jogos a serem jogados, notando que a ordem de vitórias é importante para nós. Após essas permutações serem calculadas, nós vamos aumentar o número de jogos que o torneio dura (ou seja, permite o eventual time perdedor do torneio a vencer um jogo adicional). Isso é equivalente a usar um diagrama de árvore para computar os resultados possíveis. O loop externo (while) corresponde ao nível de vértices na árvore, e o loop interior (for) itera sobre todos os jogos naquele nível.
'''''nops(Tournaments(7)); '''''
Ao leitor é deixado explorar os casos restantes, e conjecturar uma fórmula no caso geral.
=====4. Nós queremos olhar para os coeficientes binomiais <math>C(2n, n)</math>. Especificamente, para muitos exemplos, nós queremos determinar se <math>C(2n, n)</math> é divisível pelo quadrado de um primo, e se o maior expoente na fatorização do primo cresce sem limites enquanto “n” cresce.=====
Solução
Primeiro tentaremos um exemplo, para ver o que exatamente desejamos fazer, e então escrever um programa.
'''''c := binomial(6,3); '''''
Nós usamos a função “ifactors” (o “i” significa “integer”) para fatorar “c”. Essa função é uma das várias do Maple que deve ser definida “readlib” antes que possamos usá-la. Isso significa que pedimos para o Maple encontrar a função na sua biblioteca, e carregá-la na sessão atual.
'''''readlib(ifactors): '''''
'''''ifacts := ifactors(c); '''''
A página de ajuda para “ifactors” explica o que este resultado significa. Ela diz que <math>20 = 1.2^2.5^1</math>. Nós estamos interessados nos expoentes dos primos. Primeiro, pegamos o segundo elemento da lista, para obter a lista dos primos e expoentes.
'''''facts := ifacts[2]; '''''
Isso nos dá uma lista de listas, onde o primeiro elemento em cada lista é o fator primo, e o segundo é a multiplicidade (o número de vezes que o fator aparece) daquele primo. Então nós queremos percorrer a lista e obter o segundo elemento de cada sublista.
'''''powers := seq(x[2],x=facts); '''''
Então nós usamos a função “max” para encontrar o maior expoente.
'''''max(powers); '''''
Se o maior exemplo é maior que 1, então <math>C(2n, n)</math> é divisível pelo quadrado de um primo. Nesse caso, o maior exemplo 2 é, de fato, maior que 1, e <math>C(6, 3)</math> sem dúvida é divisível por <math>5^2</math>.
Combinando esses passos, agora nós escrevemos um programa que dado “n”, retorna o maior expoente na fatorização de <math>C(2n, n)</math>.
'''''LargestExpon := proc(n) '''''
'''''local c, ifacts, x; '''''
''''' c := binomial(2*n,n); '''''
''''' ifacts := ifactors(c); '''''
''''' max(seq(x[2],x=ifacts[2])); '''''
'''''end: '''''
'''''LargestExpon(6); '''''
Agora nós vamos escrever outra rotina que vai calcular o maior expoente para muitos valores de “n”, e armazenar os resultados numa tabela.
'''''Manyn := proc(maxn) '''''
'''''local results, i; '''''
''''' for i to maxn do '''''
''''' results[i] := LargestExpon(i); '''''
''''' if results[i] = 1 then '''''
''''' printf(`Hurray! A counterexample! %d`, i); '''''
''''' fi; '''''
''''' od; '''''
''''' eval(results); '''''
'''''end: '''''
Rode o programa e veja o que acontece.
'''''Manyn(10): '''''
Parece que 1, 2 e 4 são valores de “n” tais que <math>C(2n, n)</math> não é divisível pelo quadrado de um primo.
'''''binomial(8,4); '''''
'''''ifactors(%); '''''
Agora deixe o programa rodar por muito mais tempo, e veja se nós podemos encontrar algo mais.
'''''vals := Manyn(200): '''''
Vamos olhar para o crescimento do expoente máximo representando graficamente os resultados.
'''''plot([ seq([i,vals[i]],i=1..200)],style=POINT, '''''
'''''title=`Growth of Largest Exponents`); '''''
Para comparar, tente novamente com ainda mais valores de “n”.
'''''vals := Manyn(300): '''''
Dessa vez, plote com os pontos que participaram, para ver que diferença isso faz.
'''''plot([ seq([i,vals[i]],i=1..300)], '''''
'''''title=`Growth of Largest Exponents 2`); '''''
É difícil encontrar quaisquer conclusões desses dois gráficos, além de que não parece ser um limite para o tamanho. O tempo de cálculo está se tornando longo, mas ainda podemos olhada para alguns exemplos maiores.
'''''LargestExpon(500); '''''
'''''LargestExpon(1001); '''''
'''''LargestExpon(1005); '''''
'''''LargestExpon(1007); '''''
'''''LargestExpon(1009); '''''