Resumo do meu curso de Matemática Discreta – Parte 1: Análise Combinatória

Este é um resumo de tudo que eu vi enquanto fazia uma matéria chamada Matemática Discreta nesse semestre. Separei ele em 3 partes, uma parte pra cada prova.

Você pode conferir a parte 2 e a parte 3 aqui:

Resumo do meu curso de Matemática Discreta – Parte 2: Recorrências e Teoria das probabilidades

Resumo do meu curso de Matemática Discreta – Parte 3: Teoria dos Grafos

Quase todos os dias, após as aulas, eu vinha aqui escrever o que o professor passou.

Separei o post em resumo e comentários. O resumo é o que está seguido de bolinhas e os comentários não.

— publicidade —

Aula 1: dedução da fórmula de combinação e resolução do problema dos apertos de mão

• Prova “pensando” do porque a fórmula de combinação que eu deduzi nesse post é verdade.

Para provar é só usar o PFC pra ver que o número de permutações de $n$ objetos é $n!$. Então esse é o número de combinações repetidas.

• Cálculo de quantos apertos de mão 10 pessoas podem fazer.

Eu me perdi durante a explicação, mas fiz da seguinte forma: a primeira pessoa pode fazer 9 apertos diferentes. A segunda pessoa também pode fazer 9 apertos diferentes, mas já contamos um deles nos apertos da primeira pessoa, então ela pode fazer 8 apertos diferentes. Assim vai até a décima pessoa, que fará 0 apertos diferentes. Logo o total de apertos é 9+8+7+6+5+4+3+2+1+0. Isto é uma PA de razão -1. Um jeito fácil de fazer essa conta é fazer como Gauss fez com $10$ anos. Dá 45.

Posteriomente, conversando com um colega de curso ele me explicou um jeito mais fácil de calcular o total de apertos, que é assim: cada pessoa vai apertar a mão de 9 pessoas, então o total seria 9 $\cdot$ 10. Mas contamos todos os apertos duas vezes (pois a pessoa x apertar a mão da pessoa y é o mesmo que a pessoa y apertar a mão da pessoa x). Logo, a resposta é $\frac{9 \cdot 10}{2} = 45$. Acho que o professor fez assim na aula.

• Cálculo (deduzindo a fórmula pensando) de qual a chance de ganhar na mega sena.

• Comentário sobre o problema de trocar de portas, chamado problema de Monty Hall.

Aula 2: binômio de Newton e revisão da aula passada

Eu faltei. Mas perguntei a uma colega o que o professor passou e foi:

• Fórmula de combinação.

• Fórmula de permutação.

• Binômio de Newton.

Por causa disso depois dessa aula eu estudei bastante o binômio de Newton, e quase consegui deduzir a fórmula.

Aula 3: axiomas de Peano e demonstração por indução de várias igualdades e desigualdades

A aula foi só sobre indução.

• Enunciamento dos axiomas de Peano.

• Definição por recorrência do fatorial e da sequência de somas parciais.

• Demonstração por indução de várias igualdades e desigualdades (incluindo a desigualdade de Bernoulli e a soma dos quadrados dos naturais).

• Uma das desigualdades provada por indução foi a desigualdade estranha $\frac{1}{2} \frac{3}{4} … \frac{2n-1}{2n} \leq \frac{1}{\sqrt{2n+1}}$.

• Enunciamento da torre de Hanoi.

• Exercício para casa: calcular a quantidade mínima de movimentos para resolver a torre de Hanoi (sempre são 3 torres).

Eu consegui achar de um jeito pouco rigoroso a quantidade mínima de movimentos para resolver a torre de Hanoi com $n$ peças, depois de muitas dicas (de um colega e o professor).

• Dica de nomear para conquistar. Isto é, sempre comece a resolver um problema nomeando as coisas.

Qualquer coisa em função de um número natural é uma sequência, independente da forma que a coisa está escrita. Isso é estranho.

Aula 4: PFC e muitos exercícios de combinatória

• Enunciamento do PFC.

Quando um colega meu perguntou porque o PFC era verdade o professor recorreu ao diagrama de árvores. Realmente ajuda imaginar o diagrama em problemas difíceis, mas eu fiquei maluco quando tentei imaginar todos os ramos de um diagrama de 3 decisões com $n_1$, $n_2$, $n_3$ possibilidades. E foda que eu não sei como calcular combinações pelo diagrama de árvore. Preciso descobrir algum padrão dos ramos repetidos.

Apesar do PFC ser enunciado para apenas 2 decisões, é comum em problemas simples termos que fazer mais de 10 decisões.

• Resolução de vários exercícios de combinatória. O professor escrevia os exercícios, dava uns 2 minutos para nós fazermos e depois resolvia eles. A gente deve ter feito uns 15 exercícios (uma boa parte eu ja tinha visto no Morgado).

Os problemas começaram a complicar quando ele perguntou quantos anagramas tem as palavras ‘mala’ e ‘banana’. Um anagrama é uma permutação, então achei que fosse $4!$ e $6!$, mas nesse caso há letras repetidas. Então precisamos pensar em… –chorar–

• Dois problemas de combinação (de formar comissões) que inéditos e difícieis pra mim.

Nessa aula eu consegui enxergar porque as duas fórmulas de combinação são iguais. Fica fácil de ver quando usamos números não muito grandes.

• Exercício para casa: demonstrar por indução do binômio de Newton.

Pensando no dia seguinte a aula eu conclui que provavelmente da pra provar o PFC por indução.

Brincando com o binômio de Newton depois da aula eu percebi que é importantíssimo começar do zero na fórmula do binômio de Newton. Além disso, eu aprendi a mudar os extremos de um somatório. Basta remover ou adcionar parcelas de dentro do somatório.

Graças a esse novo conhecimento (binômio de Newton) eu finalmente consegui deduzir a derivada de $x^n$ sem ser só pra $n = 2$. Por causa disso eu cheguei a achar que o Newton deduziu o binômio de Newton pra poder fazer isso que eu fiz, mas quando fui pesquisar descobri que seu objetivo era estudar séries, não a derivada de $x^n$.

Brincando com o binômio de Newton eu também percebi que as propriedades algébricas do somatório derivam da comutatividade e da associatividade.

Talvez para provar o binômio de Newton eu precise deduzir o que da ao multiplicarmos uma combinação por uma constante.

Aula 5: resolução de exercícios de combinatória, triângulo de Pascal e princípio de exclusão-inclusão

Na verdade, depois de umas três semanas eu consegui provar o binômio de Newton por indução. O que usamos é só as relações de Stifel e a propriedade de que ${n \choose 0} = {n+1 \choose 0}$. E dessa vez eu fiz sem olhar literalmente nada sobre a resposta. Foi uma vitória completa. Na verdade, quase completa pois não consegui provar usando a notação de somatório, infelizmente tive que expandir o somatório usando pontinhos entre os sinais de mais. A chave foi passar do 2 pro 3 antes de fazer pra $n$.

Usar o binômio de Newton para expandir $2^n$ te da uma forma bacana de enxegar a cardinalidade do conjunto das partes.

Nesse mesmo dia que deduzi a fórmula do binômio de Newton eu também consegui deduzir quanto da $1^2 + 2^2 + … + n^2$ sem olhar em lugar nenhum. Esse sim foi uma vitória mais que completa. Em ambos os problemas eu passei semanas pensando. Em breve faço um post deduzindo isso.

• Comentário de que é possível provar o PFC fazendo uma indução dupla, seja lá o que isso quer dizer.

• Cálculo de quantas maneiras podemos colocar 5 crianças numa roda.

A resposta pode ser $5!$ ou $\frac{5!}{5}$. Depende do que você chamar de maneiras diferentes.

• Cálculo de quantos anagramas da palavra búlgaro que não tem duas vogais adjascentes existem.

Nesse temos que usar uma abodagem criativa. Primeiro contamos quantas permutações de consoantes existem. Depois notamos que há 5 espaços para botar as três vogais entre as consoantes. Logo, há $C_{5}^3$ formas de fazer isso. Mas para cada forma você pode permutar as vogais, logo você precisa multiplicar o total por $3!$. Segue que a resposta é $4!C_{5}^3 3!$. Ainda preciso acreditar completamente nessa resposta. Acho que multiplicamos tudo por causa do PFC.

• Cálculo de quantas soluções inteiras e não negativas da equação $x_1 + x_2 + … + x_n = p$ existem, onde $p>0$.

A resposta é $\frac{(p+n-1)!}{p!(n-1)!}$ e é de uma criatividade absurda. Tanto que eu ainda não acredito que é isso.

Quando eu já estava estudando probabilidade voltei nesse problema e percebi algumas coisas: meu primeiro chute foi que a resposta era $(p+3)!$ porque achei que qualquer permutação dos pontinhos e barras daria uma solução diferente, mas percebi que eu estava contando muitas soluções mais de uma vez. A solução consiste em escolher os espaços que as barras vão ficar.

• Construção do triângulo de Pascal com números e combinações.

• “Dedução” da relação de Stifel a partir do triâgulo de Pascal.

• “Dedução” de que a soma das linhas do triângulo de Pascal sempre da $2^n$.

• “Dedução” da relação de Combinações Complementares a partir do triâgulo de Pascal.

• Enunciamento do princípio da adição e da multiplicação.

O da multiplicação é simplesmente o PFC em termos de teoria de conjuntos.

• Enunciamento das fórmulas para calcular $|A \cup B|$ e $|A \cup B \cup C|$

• Cálculo de quanto múltiplos de 2, 5 ou 7 existem entre os números 1 e 1000.

A resposta é 657.

— publicidade —

Aula 6: demonstração do princípio de inclusão-exclusão para 3 conjuntos, prova do princípio da casa dos pombos e mais exercícios

• Demonstração da fórmula de $|A \cup B \cup C|$ usando a fórmulal de $|A \cup B|$.

Esse foi o único exercício dessa aula que consegui fazer durante a aula. Fui bastante derrotado nessa aula.

• Enunciamento do princípio da casa dos pombos.

• Uso do princípio da casa dos pombos para dizer que existem 2 pessoas com a mesma quantidade de fios de cabelos na grande vitória.

• Prova de que se a média de $n$ números é $x_m$ então pelo menos um dos $n$ números é maior ou igual a $x_m$.

A prova é por contradição.

• Uso do resultado acima para provar o princípio da casa dos pombos.

Confesso que não entendi como o professor fez isso, mas eu já acredito no princípio da casa dos pombos mesmo sem saber prová-lo.

• Prova de que todo número inteiro positivo tem um múltiplo que se escreve apenas em 0’s e 1’s.

Esse exercício é tão cabuloso que até o professor confessou que não saberia fazer se ele não tivesse visto a resposta e caisse numa prova que ele teria apenas duas horas para fazer. Para resolvê-lo usamos o princípio da casa dos pombos em um conjunto de restos, depois subtraimos os números que deixam o mesmo resto. A subtração será um múltiplo do inteiro positivo que se escreve apenas com 0’s e 1’s.

• Prova de que se você pegar 5 pontos dentro de um quadrado de lado de tamanho 2 então pelo menos 2 desses pontos distam uma distância menor ou igual a $\sqrt{2}$.

Para provar isso basta dividir o quadrado em 4 quadrados de lado 1, e usar o princípio em seguida.

Esse exercício é simples depois que eu vi a resposta, mas não consegui fazê-lo na aula. Por isso eu voltei pensando em exemplos que eu poderia usar o princípio da casa dos pombos e pensei em um legal: suponha que o conjunto de tudo que eu aprendi na vida tenha 1 bilhão de coisas. Segue do princípio da casa dos pombos que existe pelo menos 1 pessoa no mundo que sabe a mesma quantidade de coisas que eu, pois há mais de 1 bilhão de pessoas no mundo. Isso não significa que essa pessoa saiba exatamente as mesmas coisas que eu, só significa que sabemos a mesma quantidade de coisas.

NA VERDADE, conversando com minha mãe depois eu percebi que o que escrevi acima está ERRADO. Um contra exemplo seria todas as outras 8 bilhões de pessoas saberem 1 trilhão de coisas.

Aula 7: dedução da soma dos quadrados dos naturais e princípio de indução

• Dedução da soma dos quadrados dos n primeiros naturais de um jeito que da pra generalizar pra para qualquer potência (melhor que o meu jeito).

• “Prova” usando argumentos combinatórios de que $\binom{n}{k} = \binom{n}{n-k}$.

Provar por argumentos combinatórios significa dizer que os dois lados da igualdade contam a mesma coisa.

Depois de pensar muitos dias eu entendi a prova. Para cada forma de pegar $k$ elementos em $n$, há uma forma de pegar $n-k$ elementos de $n$ (que é justamente os que ficaram de fora quando você pegou $k$).

• “Prova” usando argumentos combinatórios das relações de Stifell.

Essas são mais difíceis de entender e aceitar.

• Prova por indução de que $4^n + 6n – 1$é divisível por $9$ $\forall n \in \mathbb{N}$.

• Enunciamento de três princípios da indução.

• Prova por indução de que a soma dos ângulos internos de um polígono de n lados é $\pi (n -2)$ rad.

A ideia é simples e criativa. Você prova que vale para um triângulo (Euclides ja fez isso), depois assume que vale para um polígono de $n$ lados, constrói um poligono com $n+1$ lados e fecha um dos lados. Ai você vai ter um polígono de $n$ lados e um triângulo. Apesar de simples, eu não consegui fazer isso na hora. Realmente tenho pouca criatividade, mas estou treinando isso.

Eu tenho o mais importante para ser um matemático, que é a vontade de ser um. Mas infelizmente não tenho a inteligência de um matemático. Sorte que isso não é uma condição necessária para se tornar matemático.

• Uso do princípio da indução forte para provar que $\mathbb{Z}$ é um domínio fatorial.

Aula 8: aula de dúvidas

• Aula de dúvidas.

• Resposta a minha pergunta de porque dividimos por $n!$ nas permutações repetidas.

A resposta do professor foi para eu fixar as outras letras e ver que se eu permutar as letras repetidas eu obtenho os mesmos anagramas.

• Explicação de como calcular a quantidade de caminhos da formiga.

• Explicação de que para provar que um número é inteiro usando argumentos combinatórios, basta mostrar que ele é igual a alguma cominação ou permutação (ou seja, que ele conta algo).

Aula 9: aula de dúvidas

• Aula de dúvidas.

Acho que combinatória é uma matéria problemática para ser ensinada, pois nela a intuição reina, então muitas vezes não nos entendemos no diálogo. Nessa aula eu e um colega calculamos corretamente o número de funções da forma $f : \{ 1 … n \} \rightarrow \{ 1 … n \}$ tais que a equação $f(k) = k$ tem solução (pelo menos segundo o chat gpt) e o professor não aceitou. Isso deve acontecer porque é muito difícil saber se estamos deixando algum caso passar ou não. Eu testei pra $n = 1$ e $n = 2$ e a fórmula bateu, mas não consegui provar por indução.

Acho que a indução foi criada pros matemáticos poderem confiar nos resultados que não conseguem criar exemplos.

Aula 10: P1

• P1.

A questão da pizza eu tô até agora sem entender o enunciado. Essa me derrotou completamente mas não me sinto abalado por isso (porque ela realmente parece bem difícil).

Na prova eu tive que usar pela primeira vez o princípio das gavetas de forma sucessiva (para garantir que pelo menos 4 elementos satisfizesse uma coisa, e não apenas 2).

A P1 literalmente cobriu os 4 primeiros capítulos do Morgado (aquele livro que eu falei que queria ler no post passado). Então esse curso realmente foi um ótimo preparatório para eu ler esse livro. O sumário dele deixou de ser grego para mim.

Coisas que aprendi nessa parte

• Finalmente entendi porque o nome é análise combinatória! É porque estudamos combinações.
• Toda combinação é um número natural, pois conta algo.
• Apesar do professor ter ensinado como calcular a soma das quartas potências dos $n$ primeiros naturais, a conta é tão grande que quando fui fazer eu devo ter comido algum número em algum lugar que ferrou tudo. Então não consegui fazer ela. Eu precisaria estar numa calmaria imensa para fazer essa conta.
• Com o conteúdo da P1 deu pra ter uma ótima noção do que posso esperar do livro do Morgado. Também deu pra ver que ele é bem completo, só não tem recorrência.
• Estou descobrindo que há um mundo de identidades com combinações.
• Para usar o princípio das gavetas nós sempre temos que separar os objetos em caixas/gavetas.
• Arranjos são combinações onde a ordem importa.
• O triângulo de Pascal tem muitas propriedades escondidas.
• Há $n.m$ parcelas num somatório duplo que vai de $1$ a $n$ e $1$ a $m$.
• TODA EXPRESSÃO MATEMÁTICA pode ser interpretada como a contagem de algo. Por exemplo, um número $k$ conta quantas maneiras temos de escolher 1 objeto de $k$ objetos.
• Talvez a melhor forma de enxergar o PFC seja de trás pra frente. Isto é, a quantidade de maneiras de fazer $n$ decisões é igual a quantidade de maneiras de fazer $n-1$ decisões vezes a quantidade de maneiras de fazer a última decisão. Isso é basicamente o que você faz quando desenha uma tabela verdade, por exemplo. Para cada maneira de fazer as $n-1$ decisões vai ter uma nova maneira escolhendo a última decisão.
• A forma mais eficiente que achei de resolver os problemas de combinatória foi sempre pensar em termos de uplas ordenadas e fazer bijeções. Isto é, calcular a quantidade de elementos de um conjunto mais fácil e fazer uma bijeção com o conjunto que você quer calcular quantos elementos tem.
• O problema da análise combinatória está em identificar as escolhas corretas no problema. Pra resolver isso, sempre se pergunte: “essas escolhas cobrem todas as possibilidades que queremos?” e “essas escolhas contam alguma possibilidade mais de uma vez?”.

— publicidade —