Durante o estudo da Análise Combinatória, são apresentadas diversas técnicas de contagem aplicadas a diferentes tipos de problemas. Naturalmente, algumas delas, especialmente as mais elementares, aparecem com maior frequência nas resoluções. O objetivo desta sala de estudos é apresentar uma nova técnica de contagem, o Princípio da Reflexão, utilizada na resolução de problemas de olimpíadas e, em alguns casos, também em vestibulares que exigem uma abordagem matemática mais avançada.
Iniciaremos os nossos estudos aprendendo (ou relembrando) o que são anagramas.
Anagrama é toda palavra formada com as mesmas letras de uma dada palavra, podendo ou não ter sentido na linguagem usual.
Assim, os anagramas de uma dada palavra são as palavras obtidas pelo "embaralhamento" das letras da palavra original (manter as letras mudando ou não a ordem).
A palavra [tex]PORTA[/tex], por exemplo, possui vários anagramas que fazem sentido na linguagem usual, veja alguns:
[tex]PARTO[/tex]
[tex]TRAPO[/tex]
[tex]RAPTO[/tex]
[tex]TOPAR[/tex]
[tex]OPTAR[/tex]
[tex]PRATO[/tex]
[tex]TROPA[/tex]
Há também anagramas que não fazem sentido na linguagem usual, por exemplo:
[tex]PTORA[/tex]
[tex]OARPT[/tex]
[tex]TORAP[/tex]
► Exibimos acima alguns anagramas da palavra [tex]PORTA \, [/tex]. E se quiséssemos saber quantos anagramas essa palavra possui?
A ideia de “embaralhar” as letras é a mesma que a de permutá-las; portanto, a palavra [tex]PORTA[/tex] possui:
[tex]\qquad \qquad 5!=5\times 4\times 3\times 2\times 1=120[/tex] anagramas.
Vamos visualizar essa conta?
Observe, inicialmente, o número de escolhas para cada posição das letras, lembrando que as letras não se repetem.
[tex]\begin{array}{c c c c c}
\textcolor{#993366}{5}\text{ escolhas}&\textcolor{#993366}{4}\text{ escolhas}&\textcolor{#993366}{3}\text{ escolhas}&\textcolor{#993366}{2}\text{ escolhas}&\textcolor{#993366}{1}\text{ escolha}\\
\overline{\text{primeira letra}}&\overline{\text{segunda letra}}&\overline{\text{terceira letra}}& \overline{\text{quarta letra}}& \overline{\text{quinta letra}}
\end{array}[/tex]
Assim, pelo Princípio Fundamental da Contagem, o número de modos distintos de embaralharmos as letras da palavra [tex]PORTA \, [/tex] é dado por [tex] \, \fcolorbox{#993366}{#ddebe8}{$\textcolor{#993366}{5}\times \textcolor{#993366}{4}\times \textcolor{#993366}{3}\times \textcolor{#993366}{2}\times \textcolor{#993366}{1}=120$} \, .[/tex]
E se houver letras repetidas? Por exemplo: Quantos anagramas a palavra “ARARAS” possui?
Como a palavra tem seis letras, podemos permutá-las de [tex]6![/tex] maneiras. No entanto, há três letras A e duas letras R idênticas, o que gera contagens repetidas. Para corrigir isso, dividimos por [tex]3![/tex] e [tex]2![/tex]. Assim, obtemos
[tex]\dfrac{6!}{3! \cdot 2!}=60[/tex],
valor que comumente é representado por [tex]P_{6}^{3,2}=60[/tex].
Querem treinar mais sua criatividade na resolução de problemas onde a divisão é utilizada para eliminar casos indevidamente contados em uma permutação? Deem uma passadinha na Sala de Estudos Mais um papel da divisão na Análise Combinatória.
Naturalmente, um dos maiores desafios em problemas de contagem é reconhecer quando a estratégia utilizada em um problema já estudado pode ser aplicada a uma nova situação. Por exemplo, no problema adaptado da OBMEP abaixo:
Problema 1: Uma formiguinha está no ponto A de um quadriculado e deseja chegar ao ponto B, deslocando-se apenas pelos lados dos quadradinhos e realizando movimentos exclusivamente para a direita ou para baixo. De quantas maneiras diferentes ela pode realizar esse trajeto?
Para resolver esse problema, vamos representar por [tex]D[/tex] os movimentos da formiga para a direita e por [tex]B[/tex] os movimentos para baixo. Observe que, em qualquer trajeto possível, a formiga realiza exatamente cinco movimentos para a direita e cinco para baixo. Assim, cada caminho pode ser associado a um anagrama da palavra [tex]DDDDDBBBBB[/tex], e o número total de trajetos corresponde à quantidade desses anagramas. Esse valor pode ser calculado por
Variações do problema acima são comuns em diversos vestibulares.
Problema 2: (ENEM – 2020) Três amigos, André, Bernardo e Carlos, moram em um condomínio fechado de uma cidade. O quadriculado representa a localização das ruas paralelas e perpendiculares, delimitando quadras de mesmo tamanho nesse condomínio, em que nos pontos A, B e C estão localizadas as casas de André, Bernardo e Carlos, respectivamente.
André deseja deslocar-se da sua casa até a casa de Bernardo, sem passar pela casa de Carlos, seguindo ao longo das ruas do condomínio, fazendo sempre deslocamentos para a direita ([tex]\rightarrow[/tex]) ou para cima ([tex]\uparrow[/tex]), segundo o esquema da figura.
Calcule o número de diferentes caminhos que André poderá utilizar para realizar o deslocamento nas condições propostas.
Perceba que se trata de um problema bastante semelhante ao anterior.
Para resolvê-lo, basta inicialmente contar o número total de caminhos possíveis de [tex]A[/tex] a [tex]B[/tex], desconsiderando, por enquanto, a restrição de não passar por [tex]C[/tex]. Esse deslocamento exige quatro movimentos para a direita e três para cima, em qualquer ordem. Assim, representando por [tex]D[/tex] os movimentos para a direita e por [tex]I[/tex] os movimentos para cima, cada trajeto corresponde a um anagrama da palavra [tex]DDDDIII[/tex], cuja quantidade pode ser calculada por [tex]P_{7}^{4,3}=\dfrac {7!}{4! \cdot 3!}=35[/tex].
Agora, vamos calcular a quantidade de caminhos de [tex]A[/tex] a [tex]B[/tex] que passam pelo ponto [tex]C[/tex].
Observe que, para determinar o número de trajetos de [tex]A[/tex] a [tex]C[/tex], basta contar os anagramas da palavra [tex]DDII[/tex], o que resulta em [tex]P_{4}^{2,2}= \dfrac {4!}{2! \cdot 2!}=6[/tex].
Já para o percurso de [tex]C[/tex] a [tex]B[/tex], são necessários dois movimentos para a direita e um para cima, correspondendo aos anagramas da palavra [tex]DDI[/tex], cujo total é [tex]P_{3}^{2}=\dfrac {3!}{2!}=3[/tex].
Pelo princípio multiplicativo, o número de caminhos de [tex]A[/tex] a [tex]B[/tex] que passam por [tex]C[/tex] é [tex]6 \cdot 3=18[/tex].
Como o total de caminhos possíveis de [tex]A[/tex] a [tex]B[/tex] é [tex]35[/tex], concluímos que o número de caminhos que não passam por [tex]C[/tex] é [tex]35-18=17[/tex].
Imaginemos agora o seguinte problema.
Problema 3: Quantos caminhos distintos existem na malha quadriculada representada abaixo para ir do ponto [tex]A(1,2)[/tex] ao ponto [tex]B(8,5)[/tex], realizando deslocamentos exclusivamente na diagonal para cima ([tex] \nearrow [/tex]) ou na diagonal para baixo ([tex]\searrow[/tex])?
Observe que este problema é bastante semelhante aos anteriores, embora os movimentos permitidos sejam diferentes. A partir de um ponto [tex](x,y)[/tex], um objeto pode deslocar-se para [tex](x+1,y+1)[/tex], representando um movimento diagonal para cima, ou para [tex](x+1,y-1)[/tex], representando um movimento diagonal para baixo.
Para simplificar a análise, vamos representar os movimentos de subida pela letra [tex]S[/tex], isto é, [tex]S:(x,y)\rightarrow (x+1,y+1)[/tex], e os movimentos de descida pela letra [tex]D[/tex], isto é, [tex]D:(x,y)\rightarrow(x+1,y-1)[/tex].
Assim, cada caminho possível pode ser descrito por uma sequência de movimentos [tex]S[/tex] e [tex]D[/tex].
Na imagem abaixo, o caminho descrito pelo objeto é [tex]SDDSSSS[/tex].
Observe ainda que, em cada deslocamento, seja ele [tex]S[/tex] ou [tex]D[/tex], o objeto avança exatamente uma unidade na direção horizontal. Como o ponto inicial tem abscissa [tex]1[/tex] e o ponto final tem abscissa [tex]8[/tex], o deslocamento horizontal total é de [tex]7[/tex] unidades, o que implica
[tex]S+D=7[/tex].
Na direção vertical, cada movimento [tex]S[/tex] corresponde a uma subida de uma unidade, enquanto cada movimento [tex]D[/tex] corresponde a uma descida de uma unidade. Como o ponto inicial possui ordenada [tex]2[/tex] e o ponto final possui ordenada [tex]5[/tex], o deslocamento vertical total é de [tex]3[/tex] unidades, o que nos fornece
[tex]S-D=3[/tex].
Essas duas equações permitem determinar a quantidade de movimentos de cada tipo ao longo do trajeto.
Resolvendo o sistema de equações, obtemos [tex]S=5 [/tex] e [tex]D=2[/tex], ou seja, o trajeto deve conter cinco movimentos de subida e dois movimentos de descida.
Assim, o número total de caminhos possíveis é igual ao número de anagramas da palavra [tex]SSSSSDD[/tex], que pode ser calculado por
[tex]P_{7}^{5,2}=\dfrac{7!}{5!\cdot2!}=21[/tex].
Portanto, existem [tex]21[/tex] caminhos distintos que satisfazem às condições do problema.
Da mesma forma que nos exemplos anteriores, vamos empregar essa estratégia para resolver um problema apresentado em uma nova situação.
Problema 4: Em uma eleição para líder de um clube de Matemática, participam [tex]10[/tex] membros e concorrem dois candidatos, [tex]A[/tex] e [tex]B[/tex]. Cada um dos [tex]10[/tex] membros vota, de forma sigilosa, em exatamente um dos candidatos. Ao final da votação, o candidato [tex]A[/tex] vence com uma diferença de [tex]4[/tex] votos.
Considerando que os votos são apurados um a um, de quantas maneiras distintas pode ocorrer a ordem de apuração dos votos?
Para resolver esse problema, podemos adotar a seguinte estratégia. Considere um objeto que se desloca exclusivamente na diagonal para cima ([tex]\nearrow[/tex]) ou na diagonal para baixo ([tex]\searrow[/tex]), partindo do ponto [tex](0,0)[/tex] e chegando ao ponto [tex](10,4)[/tex].
Nessa representação, cada ponto [tex](x,y)[/tex] indica que [tex]x[/tex] votos já foram apurados e que o candidato [tex]A[/tex] possui vantagem de [tex]y[/tex] votos em relação ao candidato [tex]B[/tex].
De modo análogo à solução do problema anterior, podemos estabelecer o seguinte sistema:
[tex]\begin{cases} S + D = 10 \\ S-D = 4 \end{cases}[/tex]
Em que [tex]S[/tex] representa os movimentos de subida ([tex]\nearrow[/tex]) e [tex]D[/tex] os movimentos de descida ([tex]\searrow[/tex]).
Resolvendo o sistema, obtemos [tex]S = 7[/tex] e [tex]D = 3[/tex]. Assim, o número de caminhos é calculado pelo número de anagramas da palavra [tex]SSSSSSSDDD[/tex], dado por [tex]P_{10}^{7,3}=\dfrac{10!}{7! \cdot 3!}=120[/tex].
Portanto, existem [tex]120[/tex] ordens distintas de apuração dos votos.
Uma solução ainda mais simples consiste em calcular o número de anagramas da palavra [tex]aaaaaaabbb[/tex], em que cada letra [tex]a[/tex] representa um voto no candidato [tex]A[/tex] e cada letra [tex]b[/tex] representa um voto no candidato [tex]B[/tex]. O cálculo seria o mesmo feito anteriormente.
Agora, suponha que o problema fosse o seguinte:
Problema 5: Em uma eleição para líder de um clube de Matemática, participam [tex]10[/tex] membros e concorrem dois candidatos, [tex]A[/tex] e [tex]B[/tex]. Cada membro vota, de forma sigilosa, em exatamente um dos candidatos. Ao final da votação, o candidato [tex]A[/tex] vence com uma diferença de [tex]4[/tex] votos.
Sabendo que os votos são apurados um a um, qual é o número de ordens de apuração nas quais o candidato perdedor esteve em vantagem em algum momento da contagem?
Uma maneira de resolver esse problema é considerar, como antes, o número de caminhos que podem ser feitos, partindo do ponto [tex](0, 0)[/tex] e chegando ao ponto [tex](10, 4)[/tex], realizando deslocamentos exclusivamente na diagonal para cima ([tex]\nearrow[/tex]) ou na diagonal para baixo ([tex]\searrow[/tex]), porém com a restrição de que esses caminhos tocam a reta [tex]y=-1[/tex] em algum momento. Desta forma, em algum momento, a vantagem de [tex]A[/tex] será negativa, ou seja, a real vantagem será do candidato [tex]B[/tex].
Observe que todo caminho que satisfaz a restrição imposta pode ser transformado, por meio de uma reflexão em torno da reta [tex]y=-1[/tex], aplicada ao trecho do trajeto entre [tex](0,0)[/tex] e o primeiro ponto de interseção com essa reta, em um caminho que parte do ponto [tex](0,-2)[/tex] e chega ao ponto [tex](10,4)[/tex].
Por outro lado, qualquer caminho que vai de [tex](0,-2)[/tex] a [tex](10,4)[/tex], o qual necessariamente toca a reta [tex]y=-1[/tex], pode ser transformado, por essa mesma reflexão, em um caminho de [tex](0,0)[/tex] a [tex](10,4)[/tex] que toca a reta [tex]y=-1[/tex].
Assim, estabelece-se uma correspondência biunívoca (um para um) entre os dois conjuntos de caminhos.
A imagem abaixo ilustra uma dessas correspondências.
Portanto, concluímos que o número de trajetos de [tex](0, 0)[/tex] a [tex](10, 4)[/tex] que satisfazem essa restrição é igual ao número de caminhos que partem de [tex](0, -2)[/tex] e chegam a [tex](10, 4)[/tex], o que reduz a resolução ao mesmo tipo de problema analisado anteriormente.
Nesse caso, os deslocamentos obedecem ao sistema
[tex]\begin{cases} S + D = 10 \\ S-D = 6 \end{cases}[/tex]
do qual obtemos [tex]S=8[/tex] e [tex]D=2[/tex].
Assim, o número total de caminhos corresponde ao número de anagramas da palavra [tex]SSSSSSSSDD[/tex], dado por
A estratégia utilizada nessa resolução é conhecida, na Análise Combinatória, como Princípio da Reflexão.
Observe agora um problema bem interessante que pode ser resolvido com esse Princípio.
Problema 6: (IME) Um pipoqueiro vende cada saco de pipoca pelo valor de [tex]R\$\;1,00[/tex] e inicia o atendimento sem qualquer dinheiro para troco. Em uma fila de oito pessoas, quatro possuem uma moeda de [tex]R\$\;1,00[/tex] e as outras quatro possuem uma nota de [tex]R\$\;2,00[/tex].
Supondo que a ordem da fila seja aleatória e que cada pessoa compre exatamente um saco de pipoca, determine a probabilidade de que o pipoqueiro consiga dar troco a todas as quatro pessoas que pagarão com a nota de [tex]R\$\;2,00[/tex].
Por definição, em um espaço amostral equiprovável, a probabilidade de ocorrência de um evento é dada pela razão entre o número de casos favoráveis e o número total de casos possíveis.
Denotemos por [tex]U[/tex] os clientes que possuem moeda de [tex]R\$\;1,00[/tex] e por [tex]D[/tex] os clientes que possuem nota de [tex]R\$\;2,00[/tex].
Assim, o número total de casos possíveis corresponde ao número de permutações distintas da palavra [tex]UUUUDDDD[/tex], isto é, ao número de anagramas formados com quatro letras [tex]U[/tex] e quatro letras [tex]D[/tex]. Esse número é dado por
Para o cálculo do número de casos favoráveis, recorreremos ao Princípio da Reflexão.
A ideia consiste em contar os caminhos que partem do ponto [tex](0, 0)[/tex] e chegam ao ponto [tex](8, 0)[/tex], realizando apenas deslocamentos na diagonal para cima ([tex]\nearrow[/tex]) ou na diagonal para baixo ([tex]\searrow[/tex]), sem interceptar a reta [tex]y=-1[/tex] em nenhum momento do percurso.
Nessa representação, cada ponto [tex](x,y)[/tex] indica que [tex]x[/tex] pessoas já foram atendidas e que há [tex]y[/tex] moedas disponíveis para troco.
Conforme visto anteriormente, é mais conveniente determinar inicialmente o número de caminhos que tocam a reta [tex]y=-1[/tex] e, em seguida, subtrair esse valor do total de caminhos possíveis.
Pelo Princípio da Reflexão, o número de caminhos de [tex](0,0)[/tex] a [tex](8,0)[/tex] que tocam a reta [tex]y=-1[/tex] é igual ao número de caminhos que partem de [tex](0,-2)[/tex] e chegam a [tex](8,0)[/tex].
A imagem abaixo ilustra um desses caminhos, bem como sua reflexão em torno da reta considerada.
Nesse caso, os deslocamentos obedecem ao sistema
[tex]\begin{cases} S + D = 8 \\ S-D = 2 \end{cases}[/tex]
do qual obtemos [tex]S=5[/tex] e [tex]D=3[/tex].
Assim, o número de caminhos que partem de [tex](0,-2)[/tex] e chegam a [tex](8,0)[/tex] (e que, portanto, correspondem aos caminhos de [tex](0,0)[/tex] a [tex](8,0)[/tex] que interceptam a reta [tex] y=-1[/tex]) é igual ao número de anagramas da palavra [tex]SSSSSDDD[/tex], dado por
Consequentemente, o número de casos favoráveis é [tex]70 – 56 = 14[/tex].
Logo, a probabilidade de o pipoqueiro conseguir dar troco a todas as pessoas que pagarem com a nota de [tex]R\$\;2,00[/tex] é
[tex]P=\dfrac{14}{70}=\dfrac{1}{5}=20\%[/tex].
Como se trata de um número pequeno de pessoas, seria possível calcular o número de casos favoráveis por meio da enumeração direta de todas as possibilidades, obtendo-se os [tex]14[/tex] casos. No entanto, ao utilizar o Princípio da Reflexão, obtemos uma técnica geral, aplicável a uma quantidade arbitrária [tex]n[/tex] de pessoas.
Que tal vocês resolverem mais alguns problemas utilizando o Princípio da Reflexão?
Problema 7: Em uma eleição com dois candidatos, [tex]X[/tex] e [tex]Y[/tex], participam [tex]20[/tex] eleitores, sendo que cada eleitor vota em exatamente um dos candidatos. Ao final da votação, o candidato [tex]X[/tex] recebe [tex]15[/tex] votos e o candidato [tex]Y[/tex], [tex]5[/tex] votos.
Os votos são apurados um a um, em alguma ordem.
Responda:
a) De quantas maneiras distintas pode ocorrer a ordem de apuração dos votos?
b) Em quantas ordens de apuração o candidato [tex]X[/tex] permanece sempre em vantagem sobre o candidato [tex]Y[/tex], isto é, nunca ocorre empate nem desvantagem após o primeiro voto apurado?
c) Em quantas ordens de apuração o candidato [tex]X[/tex] permanece sempre em vantagem ou empatado com o candidato [tex]Y[/tex]?
a) [tex]15504.[/tex]
b) [tex]7752.[/tex]
c) [tex]10659.[/tex]
Problema 8: (Extraído de A.C. Morgado) Numa fila para um teatro popular, [tex]m[/tex] pessoas têm notas de [tex]R\$\;5,00[/tex] e [tex]n[/tex] ([tex]n \lt m[/tex]) pessoas têm notas de [tex]R\$\;10,00[/tex]. A entrada custa [tex]R\$\;5,00[/tex].
a) Quantas são as filas possíveis?
b) Quantas são as filas que terão problemas de troco, se a bilheteria começar a trabalhar sem troco?
c) Quantas são as filas que terão problema de troco, se a bilheteria começar a trabalhar com duas notas de [tex]R\$\;5,00[/tex]?
a) [tex](m+n)![/tex]
b) [tex]\dfrac {n}{m+1}(m+n)![/tex]
c) [tex](m+n)!\dfrac{n(n-1)(n-2)}{(m+3)(m+2)(m+1)}.[/tex]
Problema 9: Um programador está escrevendo um código utilizando parênteses de abertura “[tex]([/tex]” e parênteses de fechamento “[tex])[/tex]”. Para evitar erros de sintaxe, ele estabelece as seguintes regras:
Em qualquer trecho da sequência, o número de parênteses de fechamento nunca pode ser maior que o número de parênteses de abertura.
Ao final da sequência, o número total de parênteses de abertura deve ser igual ao número de parênteses de fechamento.
Observe que apenas as três primeiras sequências são válidas, pois, na última, em determinado momento aparece um parêntese de fechamento sem que exista um parêntese de abertura correspondente ainda não fechado.
Sabendo que a sequência contém exatamente [tex]4[/tex] parênteses de abertura e [tex]4[/tex] parênteses de fechamento, responda:
De quantas maneiras distintas é possível formar uma sequência válida de parênteses?
[tex]14.[/tex]
Um comentário importante sobre esse último problema é que, ao generalizá-lo para [tex]n[/tex] pares de parênteses, o número de sequências válidas obtidas é dado por [tex]C_{n}=\dfrac {1}{n+1}\begin{pmatrix}
2n \\
n
\end{pmatrix}[/tex].
Esse valor define a sequência conhecida, na Análise Combinatória, como números de Catalan.
Esses números surgem em diversos problemas clássicos de contagem com estrutura recursiva, como, por exemplo, o número de maneiras distintas de triangular um polígono convexo. A sequência dos primeiros números de Catalan é [tex](1, 1, 2, 5, 14, 42, 132, 429, …)[/tex].
Um vídeo para fixar ideias
Vídeoaula O Princípio da Reflexão – POTI
Professor Victor Bitarães
Equipe COM – OBMEP
Maio de 2026.
Referências: [1] MORGADO, Augusto César; CARVALHO, Paulo Cezar Pinto. Matemática discreta. Rio de Janeiro: SBM, 2022. [2] MORGADO, Augusto César; CARVALHO, João Bosco Pitombeira de; CARVALHO, Paulo Cezar Pinto; FERNANDEZ, Pedro. Análise combinatória e probabilidade. 9. ed. Rio de Janeiro: SBM, 2006.
Link permanente para este artigo: https://clubes.obmep.org.br/blog/sala-de-estudos-principio-da-reflexao/
