Lista de Exercícios Resolvidos - Lógica, Divisibilidade e Teoria dos Grafos

Questões 1 5 5 5 Para cada item abaixo verifique se a afirmação do lado esquerdo é necessária suficiente ou ambas para o do lado direito Em cada caso forneça uma prova se verdadeiro ou um contraexemplo em caso contrário Suponha R como domínio das variáveis a x Px Qx x Px x Qx b x Px Qx x Px x Qx c x Px Qx x Px x Qx 2 5 Prove que para todo k o produto de k números naturais consecutivos é divisível por k 3 10 5 Considere o grafo G V E da figura abaixo em que V é o conjunto de 4 vértices e E o de 5 arestas a Via técnicas de contagem mas sem utilizar o princípio de inclusãoexclusão prove que podemos colorir os vértices de G com r 0 cores tal que vértices adjacentes recebem cores distintas de cr r4 5r3 8r2 4r maneiras b Se considerarmos os vértices em V indistinguíveis como fica cr Justifique 4 10 Sejam nm 0 inteiros e considere n bolas e m caixas numeradas de 1 a n e de 1 a m respectivamente De quantas formas podemos distribuir as n bolas nas m caixas de modo que as bolas na caixa j tenham numeração menor que as bolas na caixa j1 para 0 i j m Prove a correção da sua resposta 1 a Necessária e suficiente Prova da necessidade Suponha que x Px Qx é verdadeira Então x Px é verdadeira e Qx é verdadeira Portanto temos que x Px é verdadeira e x Qx é verdadeira Prova da suficiência Suponha que x Px x Qx seja verdadeira Então x Px é verdadeira e Qx é verdadeira Portanto temos que x Px Qx é verdadeira b Necessária e suficiente Prova da necessidade Suponha que x Px v Qx é verdadeira Então para todo x Px é verdadeira ou Qx é verdadeira Portanto temos que x Px é verdadeira ou x Qx é verdadeira Prova da suficiência Suponha que x Px x Qx seja verdadeira Então x Px é verdadeira ou Qx é verdadeira Portanto temos que x Px Qx é verdadeira c Considere o seguinte contraexemplo Px é verdadeira x mas Qx é falso para x Neste caso a afirmação x Px x Qx é verdadeira mas x Px Qx é falsa 2 seja n o menor número natural tal que o produto dos n primeiros seja divisível por n Para provar que n k para todo k basta mostrar que se n k então o produto dos k números consecutivos não é divisível por k Suponha que n k 1 2 3 n 1 são os n 1 primeiros naturais O produto é dado por 1 2 3 n 1 como n é o menor natural tal que o produto é divisível por n então 1 2 3 n m n onde m e m daí 1 2 3 n n 1 m n n 1 Observe que k divide k 1 e k 1 divide k 2 e assim por diante Logo k n m n 1 Como k n 1 então k não divide n 1 ou seja k não divide nmn1 logo se n k então o produto dos k primeiros números não é divisível por k Contradição Logo n k para todo k 3 Veja que se colormos os vértices de G com uma única cor temos r opções para cada vértice logo r4 possibilidades Mas temos que subtrair o número de maneiras que colorir de forma que conflite com a cor dos adjacentes Se o vértice tem três adjacentes subtraímos 4r13 como Se tem dois adjacentes e um adj ao oposto 4r12 r2 É por fim subtraímos 4r12 r22 das possibilidades se o vértice tem dois adjacentes que não compartilhama o vértice oposto Logo expandindo r4 4r12 4r12 r2 4r22 r22 e simplificado termos r4 5r3 8r2 4r b Se consideramos os vértices em V indistinguíveis então todas as permutações dos vértices resultam no mesmo grafo Portanto cIr deve ser ajustado vamos calcular cIr sem considerar indistinguibilidade dos vértices Temos que o grafo tem 4 vértices fixando e contabilizando as possibilidades para os outros 3 vértices isso resulta em 3 possibilidades de aresta partindo do vértice fixo Repetindo o processo para os outros vértices encontramos apenas uma possibilidade de aresta Logo cIr 3 2 1 6 Mas como os vértices não são distinguíveis é necessário ajustar o resultado Como existem 4 vértices cada grafo foi contabilizado 4 24 vezes Logo cIr 624 14 4 Vamos usar o Princípio das Gavetas Vamos enumerar as gavetas de J a m j já que a última não tem restrição sobre o números de bolas Podemos escolher as bolas para a primeira gaveta de m formas para a segunda temos n j bolas para m 2 gavetas logo pelo PGG deve ter pelo menos n 1m 2 bolas Continuando assim vemos que sempre haverá uma gaveta vazia Portanto o número de fon mas é dado por mC u x n 1m 2 x n n 1 m 2 m 1 x x n 3 4 n 2 13 2 Onde mC u é o coeficiente binomial m escolha i dado por ml il m i Note que em cada etapa do processo de distribuição estamos seguindo a restrição de que as bolas na gaveta i 1 têm número maior que as bolas na gaveta i Portanto todas as distribuições são contadas exatamente uma vez