Problemas de Combinatoria - Nivel Avancado

1 10 Sejam a b inteiros positivos Prove que o número de caminhos reticulares no plano cartesiano Z2 de 00 a ab que nunca ultrapassa a diagonal principal é ab b ab b1 Um caminhos reticular é aquele que a cada passo retrocede ou avança em exatamente uma unidade na horizontal ou vertical ij i1j ou ij i1j ou ij ij1 ou ij ij1 2 10 Ao encontrarmos quatro montes de pedras em uma trilha decidimos rearranjálos em cinco montes Prove que ao menos duas pedras terminaram em montes menores cada uma podendo ter sido movida ou não 3 10 Colorimos os pontos com coordenadas inteiras do plano R2 com uma dentre seis cores diferentes Prove que existe um retângulo monocromático todos os vértices possuem a mesma cor em tal coloração Podemos limitar as dimensões da tal retângulo Justifique 4 10 Seja S 3n tal que S n2 Prove que existem i j em S tais que n i j 2n 5 10 Considere três casais x1 y1 x2 y2 e x3 y3 Utilize o princípio de inclusão e exclusão para determinandos números de formas em que as seis pessoas podem ser acomodadas em uma mesa redonda tal que para i j os elementos xi e xj não podem sentarse frente a frente 6 1010 Seja σ σ1σ2 σn uma permutação de n Dizemos que i é uma descida em σ se σi σi1 O conjunto descendente de σ é o conjunto de todas as descidas em σ a Quantas permutações de 8 possuem conjunto descendente T 146 b Quantas permutações de 8 possuem conjunto descendente 146 7 10 Considere a recorrência rn rn1 rn2 para n 3 com r1 r2 1 Prove que rn é divisível por 3 se e somente se n é divisível por 4 8 10 Seja an o número de permutações e de n tais que σi1 σi 1 Prove que para todo n 3 a recorrência an n1an1 n2an2 é válida 9 10 Em um torneio de tênis com 2n participantes cada possível par de indivíduos se enfrentou uma única vez Prove por indução em n que terminado o torneio é possível encontrarmos n1 jogadores e arrumálos em uma fila um atrás o outro de forma que cada jogador derrotou todos os demais que estão atrás dele na fila 10 10 Seja G um grafo com n vértices m arestas e κ componentes Prove por indução em que que m n κ O que ocorre quando a igualdade é atingida 11 10 O lema abaixo é verdadeiro mas a prova fornecida é defeituosa Identifique pontos precisos na prova em que um passo não justificado é feito e explique o porquê tal passo é injustificado Lema 1 Para quaisquer primo p e inteiros positivos nx1x2xn se px1x2xn então pxi para algum 1 i n Notação px significa p divide x isto é que existe um inteiro positivo q tal que x pq Prova defeituosa A prova é por indução forte em n Como hipótese de indução suponha que o lema é válido para n Quando n1 o caso base temos que px1 e portanto px1 para i1 Para o passo de indução supondo que a afirmação é válida para todo k n vamos provar que ela é válida para n1 Assim suponha que px1x2xn1 Seja yn xn xn1 de forma que x1x2xn1 x1x2xn1 yn Como o lado direito da equação é um produto de n termos temos por hipótese de indução que p divide um deles Se pxi para algum i n obtemos o valor i desejado Em caso contrário pyn Mas como yn é o produto dos dois termos xn e xn1 temos por hipótese de indução que p divide um deles Neste caso pxi para i n ou i n1 o que conclui a prova 12 10 Seja F S1 S2Sm uma família de conjuntos sobre um conjunto X com Si r e suponha que F possui um sistema de representantes distintos Prove que F possui ao menos frm i1minrm r1 i sistemas de representantes distintos Questão 1 sejam ab inteiros positivos Prove que o número de caminhos reticulares no plano cartesiano Z2 números inteiros de 00 a aB que nunca ultrapassa a diagonal principal é a b a b b b 1 Um caminhos reticular é aquele que a cada passo retrocede ou avança em exatamente uma unidade na horizontal ou vertical ij i1jou ij i 1 j ou ij i j1ou ij ij 1 Questão 2 Ao encontrarmos quatro montes de pedras em uma trilha decidimos rearranjálos em cinco montes Prove que ao menos duas pedras terminaram em montes menores cada uma podendo ter sido movida ou não Vamos supor que o número de pedras em cada um dos quatro montes originais seja a b c e d Então o número total de pedras é a b c d Quando rearranjamos essas pedras em cinco montes o número médio de pedras por monte é a b c d 5 Como a média é um número fracionário pelo menos um dos cinco montes deve ter menos pedras do que a média Além disso pelo menos um dos quatro montes originais deve ter mais pedras do que a média Portanto pelo menos duas pedras terminaram em montes menores Questão 3 Colorimos os pontos com coordenadas inteiras do plano R2 com uma dentre seis cores diferentes Prove que existe um retângulo monocromático todos os vértices possuem a mesma cor em tal coloração Podemos limitar as dimensões de tal retângulo Justifique Considere um retângulo de dimensões 6 por 36 Dentro deste retângulo existem 37 linhas horizontais De acordo com o Princípio da Casa dos Pombos pelo menos duas dessas linhas devem ter pontos da mesma cor em uma mesma coluna Esses pontos formam um retângulo monocromático Para entender melhor como isso funciona imagine que cada linha horizontal é uma casa de pombo e cada cor é um pombo Como temos 37 casas de pombos e apenas 6 pombos cores pelo menos uma das casas deve ter mais de um pombo Isso significa que pelo menos duas linhas horizontais devem ter pontos da mesma cor em uma mesma coluna Quanto às dimensões do retângulo elas não podem ser limitadas Isso porque podemos sempre encontrar um retângulo maior simplesmente aumentando as dimensões do retângulo inicial e repetindo o processo Questão 4 Seja S 3n tal que S n 2 Prove que existem i j em S tais que n i j 2n Considere os n 1 conjuntos A0 A1 An onde Ak é o conjunto de todos os elementos de S que estão no intervalo 3k 1 3k 3 Como S tem n 2 elementos e existem n 1 conjuntos Ak pelo princípio da casa dos pombos pelo menos um dos conjuntos Ak deve conter pelo menos dois elementos Seja k o índice desse conjunto Agora considere dois elementos distintos i e j em Ak Como i e j estão ambos no intervalo 3k 1 3k 3 temos que i j 2 Além disso como i e j são ambos maiores do que 3k temos que i j 3k 3k 3 3 Portanto 3 i j 2 Multiplicando essa desigualdade por n obtemos 3n ni j 2n Como ni j é um múltiplo inteiro de n temos que ni j 2n Portanto n i j 2n Isso completa a prova Questão 5 Considere três casais x1y1 x2 y2 e x3 y3 Utilize o princípio de inclusão e exclusão para determinar os números de formas em que as seis pessoas podem ser acomodadas em uma mesa redonda tal que para i j elementos os elementos xi e xj não podem sentarse frente a frente Questão 6 Seja σ σ1 σ2 σn uma permutação de n Dizemos que i é uma descida em σ se σi σi 1 O conjunto descendente de σ é o conjunto de todas as descidas em σ a Quantas permutações de 8 possuem conjunto descendente T 146 b Quantas permutações de 8 possuem conjunto descendente 146 Questão 7 Considere a recorrência rn rn 1 rn 2 para n 3 com r1 r2 1 Prove que rn é divisível por 3 se e somente se n é divisível por 4 Por indução Caso base Para n 4 r4 r3 r2 2 1 3 que é divisível por 3 Passo indutivo Suponha que para algum k 4 rk é divisível por 3 se e somente se k é divisível por 4 Queremos mostrar que isso também vale para k1 Caso 1 k1 é divisível por 4 Então k 4m para algum inteiro m Como k é par podemos escrever k 2j para algum inteiro j Então rk1 rk rk1 r2j r2j1 Pela hipótese indutiva como 2j é divisível por 4 r2j é divisível por 3 Portanto rk1 também é divisível por 3 Caso 2 k1 não é divisível por 4 Então k 4m t para algum inteiro m e t 1 2 ou 3 Como k é ímpar podemos escrever k 2j 1 para algum inteiro j Então rk1 rk rk 1 r2j1 r2j Pela hipótese indutiva como nenhum desses termos é divisível por 4 nenhum deles é divisível por 3 Portanto sua soma também não é divisível por 3 Assim a afirmação vale para todos os n 4 Questão 8 Seja an o número de permutações σ de n tais que σi 1 σi1 Prove que para todo n 3 a recorrência an n 1an1 n2an2 é válida Vamos provar isso por indução Para n 3 temos a3 2a2 a1 22 1 5 Isso é verdade porque existem 5 permutações de 3 que satisfazem a condição 132 213 231 312 e 321 Agora suponha que a recorrência seja verdadeira para algum n 3 Queremos mostrar que também é verdade para n1 Considere uma permutação σ de n1 que satisfaça a condição σi 1 0 σi1 Existem dois casos a considerar Caso 1 σn1 n1 Neste caso podemos remover o último elemento da permutação para obter uma permutação de n que satisfaça a condição Existem an tais permutações Caso 2 σn1 0 n1 Neste caso podemos trocar σn1 com o elemento na posição n1 e remover o último elemento para obter uma permutação de n1 que satisfaça a condição Existem an1 tais permutações Portanto an1 an n1an1 Por indução a recorrência é verdadeira para todo n 3 Questão 9 Em um torneio de tênis com 2n participantes cada possível par de indivíduos se enfrentou uma única vez Prove por indução em n que terminado o torneio é possível encontrarmos n1 jogadores e arrumálos em uma fila um atrás o outro de forma que cada jogador derrotou todos os demais que estão atrás dele na fila Base da indução Para n 1 temos 2 jogadores É possível colocálos em uma fila de forma que o jogador que venceu esteja na frente Passo da indução Suponha que a afirmação seja verdadeira para n k Agora considere um torneio com 2k1 jogadores Divida os jogadores em dois grupos de 2k jogadores cada Dentro de cada grupo cada jogador enfrentou todos os outros jogadores do mesmo grupo Pela hipótese de indução é possível organizar os jogadores de cada grupo em uma fila de forma que cada jogador tenha derrotado todos os jogadores atrás dele na fila Agora considere os jogos entre os jogadores dos dois grupos Escolha um jogador do primeiro grupo e um jogador do segundo grupo Se o jogador do primeiro grupo venceu o jogador do segundo grupo coloque todos os jogadores do primeiro grupo na frente dos jogadores do segundo grupo na fila final Caso contrário coloque todos os jogadores do segundo grupo na frente dos jogadores do primeiro grupo na fila final Essa fila final terá 2k1 1 jogadores e satisfará a condição de que cada jogador tenha derrotado todos os jogadores atrás dele na fila Portanto a afirmação é verdadeira para n k 1 Pela indução matemática a afirmação é verdadeira para todo n 1 Questão 10 Seja G um grafo com n vértices m arestas e κ componentes Prove por indução em que que mnk O que ocorre quando a igualdade é atingida Para n1 temos que m110 o que é verdadeiro já que m é não negativo Agora suponha que a afirmação seja verdadeira para nk e vamos provar para nk1 Seja G um grafo com k1 vértices e κ componentes Se removermos um vértice v de G obtemos um grafo G com k vértices e pelo menos κ1 componentes já que a remoção de um vértice pode aumentar o número de componentes em no máximo 1 Pela hipótese de indução temos que o número de arestas m de G é pelo menos kκ1k κ1 Como G tem uma aresta a mais do que G temos que mm1kκ2k1κ Quando a igualdade é atingida ou seja quando mnκ cada componente do grafo é uma árvore Questão 11 O lema abaixo é verdadeiro mas a prova fornecida é defeituosa Identifique pontos precisos na prova em que umpasso não justificado é feito e explique o porquê tal passo é injustificado Lema 1 Para quaisquer primo p e inteiros positivos n x1 x2xn se p x1 x2 xn então p xi para algum 1 i n Notação px significa p divide x isto é que existe um inteiro positivo q tal que x pq Prova defeituosa A prova é por indução forte em n Como hipótese de indução suponha que o lema é válido para n Quando n 1 o caso base temos que p xi e portanto p xi para i 1 Para o passo de indução supondo que a afirmação é válida para todo k n vamos provar que ela é válida para n1 Assim suponha que p x1x2 xn1 Seja yn xn xn1 de forma que X1X2 xn1 x1x2 xn1Yn Como o lado direito da equação é um produto de n termos temos por hipótese de indução que p divide um deles Se pxi para algum i n obtemos o valor i desejado Em caso contrário pyn Mas como yn é o produto dos dois termos xn e xn1 temos por hipótese de indução que p divide um deles Neste caso pxi para i n ou i n 1 o que conclui a prova O erro na prova ocorre no passo de indução A hipótese de indução é que o lema é válido para n mas é usado para afirmar que p divide um dos termos xn ou xn1 No entanto a hipótese de indução não pode ser aplicada a yn xn xn1 porque yn não é um produto de n termos Portanto o passo em que se afirma que p divide um dos termos xn ou xn1 é injustificado Na prova original o passo de indução assume que a afirmação é válida para um produto com n1 fatores e usa a hipótese de indução para afirmar que p divide um dos termos xn ou xn1 No entanto essa hipótese de indução é inválida porque ela só se aplica a um produto com n fatores Isso acontece porque a hipótese de indução é formulada como uma afirmação sobre um produto de n termos não sobre um produto de n1 termos Mas na tentativa de estender a hipótese de indução para um produto com n1 termos a prova original usa um produto auxiliar yn xn xn1 que não é um produto de n termos e assim a hipótese de indução não pode ser aplicada diretamente Questão 12Seja F S1 S2 Sm uma família de conjuntos sobre um conjunto X com Si e suponha que F possui um sistema de representantes distintos Prove que F possui ao menos frm produtorio de i 1 indo até minrm com função r 1 i Sistemas de representantes distintos