MATERIAL OBMEP - CONTAGEM

Escrito por João Ferreira e João Linhares.

Introdução

Nesse material iremos abordar diferentes formas e ideias para se contar coisas e maneiras de se fazer algo, um dos tipos de questões mais cobrados na OBMEP. Confira abaixo a teoria necessária para fazer isso:

Fatorial (!). Fatorial é muito utilizado em problemas de contagem e pode ser usado, por exemplo, para contar a quantidade de maneiras de organizar $n$ objetos distintos em fila. $n!=n(n-1)\dots2\cdot1$, ou seja, é o produto de todos os numeros naturais menores ou iguais a $n$.

Selecionando elementos de diferentes conjuntos. Se temos que escolher um elemento de diferentes conjuntos, a quantidade de maneiras de se fazer isso é igual ao produto da quantidade de elementos de cada conjunto. Confuso? Veja um exemplo: De quantas maneiras diferentes Pedrinho pode se vestir se ele possui $3$ calças distintas e $2$ camisas distintas? A resposta é $2\cdot 3=6$, pois o conjunto das calças possui $3$ elementos distintos e o conjunto das camisas possui $2$ elementos distintos.

Selecionando uma quantidade de objetos de um único conjunto. Também conhecido como "$n$ escolhe $k$", a quantidade de maneiras de escolher $k$ objetos distintos de um conjunto de $n$ objetos diferentes é $\binom{n}{k}= \dfrac{n!}{k!(n-k)!}$.

Problemas

A seguir há uma lista de problemas selecionados por nós e em ordem de dificuldade para testar seus conhecimentos. Recomendamos fortemente que você tente os problemas sozinho, olhe as dicas e tente o problema novamente e se finalmente não conseguir respondê-lo olhe a solução.

1 (OBMEP/2014-F1-N2-P18). O número $2014$ tem quatro algarismos distintos, um ímpar e três pares, sendo um deles $0$. Quantos números possuem exatamente essas características?

2 (OBMEP/2015-F1-N2-P18). Em uma olimpíada de matemática, foram distribuídas várias medalhas de ouro, prata e bronze. Cada participante premiado pôde receber uma única medalha. Aldo, Beto, Carlos, Diogo e Elvis participaram dessa olimpíada e apenas dois deles foram premiados. De quantas formas diferentes pode ter acontecido essa premiação?

3(OBMEP-2012-N3). Juca quer pintar os algarismos do número $2013$, como na figura ao lado, de modo que cada região seja pintada com uma das cores branca, cinza ou preta e que regiões vizinhas tenham cores diferentes.

a) Observe que Juca pode pintar o algarismo $2$ de $3\times2\times2=12$ maneiras diferentes. De quantas maneiras diferentes ele pode pintar o algarismo $1$?

b) De quantas maneiras diferentes Juca pode pintar o algarismo $3$?

c) De quantas maneiras diferentes Juca pode pintar o algarismo $0$?

d) Escreva uma expressão numérica que permita calcular de quantas maneiras Juca pode pintar o número $2013$.

4(BQ-OBMEP-2017-N3). Os números inteiros do conjunto $\{1,2,\dots,20\}$ serão pintados com duas cores, branco e preto, de modo que ambas as cores sejam usadas. Além disso, o produto dos números de uma cor não deve possuir fatores primos em comum com o produto dos números da outra cor. De quantos modos isso pode ser feito?

5(OBMEP/2019-F1-N2-P16). Uma mesa circular tem seis lugares com cadeiras de cores diferentes. De quantos modos três casais de namorados podem ocupar esses seis lugares de forma que os três rapazes fiquem juntos e as três moças também, mas nenhum rapaz fique junto de sua namorada?

6 (OBMEP/2010-F1-N2-P19). De quantas maneiras é possível escolher três números inteiros de $1$ a $19$, de modo que o maior e o menor sejam ímpares e o outro seja par?

7 (OBMEP/2014-F1-N2-P19). Um cubo de madeira foi pintado de vermelho e depois cortado em $n^3$ cubinhos iguais, $n > 2$. Alguns desses cubinhos ficaram sem nenhuma face pintada e outros com uma, duas ou três faces pintadas. Se o número de cubinhos sem nenhuma face pintada é igual ao número de cubinhos com exatamente uma face pintada, qual é o valor de $n$?

8 (OBMEP/2016-F2-N2-P5). Fernanda precisa criar uma senha para poder usar o computador da escola. A senha deve ter cinco algarismos distintos de modo que, da esquerda para a direita, o algarismo da 1ª posição seja maior do que $1$, o da 2ª posição seja maior do que $2$, e assim por diante. Por exemplo, $25476$ é uma senha possível, mas $52476$ não é, pois o algarismo na segunda posição não é maior do que $2$. Quantas senhas Fernanda poderá formar?

9 (OBMEP/2017-F1-N2-P20). Sérgio quer numerar de $1$ a $16$ os triângulos da Figura 1 de tal modo que números consecutivos fiquem em triângulos que tem um lado em comum. Por exemplo, ele pode numerar os triângulos como na Figura 2. De quantas maneiras Sérgio pode fazer isso?

10 (OBMEP/2018-F2-N2-P6). Um enfeite é formado por um dado encaixado em uma cavidade quadrada sobre uma base, como mostra a figura. As faces do dado estão numeradas de $1$ a $6$.

a) De quantas maneiras o dado pode ser encaixado na base?

b) De quantas maneiras o dado pode ser encaixado na base, de modo que pelo menos um dos vértices da face $6$ fique em contato com a base?

c) De quantas maneiras um dado, encaixado como na figura, pode ser reposicionado na base, de modo que nenhum número permaneça em sua posição original?

11 (OBMEP/2013-F1-N2-P19). De quantas maneiras diferentes é possível pintar a figura, de modo que cada uma das regiões seja pintada com uma das cores azul, verde ou preto e que regiões cujas bordas possuem um segmento em comum não sejam pintadas com a mesma cor?

12 (OBMEP/2011-F2-N2-P5). João vai pintar figuras compostas por quadrados e triângulos. Cada quadrado pode ser pintado de azul, vermelho ou verde e cada triângulo de azul, vermelho ou amarelo, de modo que polígonos com um lado comum não tenham a mesma cor. Em cada um dos itens abaixo, determine de quantas maneiras João pode pintar a figura correspondente.

 

13 (OBMEP/2016-F1-N2-P20). Bruno tem $5$ figurinhas idênticas com a bandeira da Alemanha, $6$ com a bandeira do Brasil e $4$ com a da Colômbia. Ele quer fazer um pacote com pelo menos $3$ dessas figurinhas. De quantas maneiras ele pode fazer esse pacote?

14 (BQ-OBMEP-2018-N3). O jogo TORRECOPOS consiste em guardar uma pilha de copos, previamente empilhados sobre uma mesa, com as "bocas" voltadas para baixo, de forma que todos fiquem um dentro do outro e apenas um em contato com a mesa. No primeiro andar, os copos são do tipo A, no segundo, do tipo B, no terceiro, do tipo C e assim por diante. Vence o jogo aquele que os recolher no menor tempo.

a) Numa torre com $3$ andares, quantas possibilidades existem para a ordem dos copos após recolhidos (lembrando que copos de um mesmo andar são idênticos)?

b) Quantas configurações diferentes podemos obter ao recolher os copos em uma torre com $4$ andares?

c) Quantas configurações diferentes podemos obter ao recolher os copos de uma torre com $n$ andares?

15 (OBMEP-2017-N3). Marcela brinca de cobrir todas as casas de tabuleiros quadriculados com peças retangulares e cada uma dessas peças cobre exatamente duas casas do tabuleiro.
a) A figura abaixo mostra uma maneira de cobrir um tabuleiro $2\times3$  utilizando três peças. Desenhe as outras duas maneiras de cobrir com três peças o mesmo tabuleiro.

b) De quantas maneiras diferentes Marcela pode cobrir com quatro peças o tabuleiro abaixo?

c) De quantas maneiras diferentes Marcela pode cobrir com dez peças o tabuleiro abaixo?

16 (OBMEP-2006-N3). O quadrado da figura I é chamado especial porque

• ele esta dividido em $16$ quadrados iguais;
• em cada linha e em cada coluna aparecem os algarismos $1$, $2$, $3$ e $4$;
• em cada um dos quadrados $A$, $B$, $C$ e $D$ (como na figura II) aparecem os algarismos $1$, $2$, $3$ e $4$;

a) Complete o quadrado abaixo de modo que ele se torne especial.

b) É possível completar o quadrado abaixo de modo a obter um quadrado especial? Por que?

c) Exiba todas as maneiras de completar o quadrado abaixo de modo a obter um quadrado especial.

 

d) Quantos quadrados especiais existem?

17 (OBMEP/2018-F1-N2-P19). Para fazer um percurso do ponto $P$ ao ponto $Q$ da figura, uma formiguinha deve andar sobre os segmentos horizontais sempre para a direita e nunca passar duas vezes por um mesmo segmento vertical. De quantas maneiras diferentes ela pode fazer esse percurso?

18 (BQ-OBMEP-2019-N3). De quantas maneiras podemos colocar $8$ algarismos iguais a $1$ e $8$ algarismos iguais a $0$ em um tabuleiro $4\times4$ de modo que as somas dos números escritos em cada linha e coluna sejam as mesmas?

19 (OBMEP-2019-N3). Um tabuleiro preenchido com as letras $A$, $B$, $C$ e $D$ é bacana se essas quatro letras aparecem em qualquer quadriculado $2\times 2$ do tabuleiro.

a) Preencha os tabuleiros abaixo de modo que eles sejam bacanas e diferentes entre si.

b) Quantos tabuleiros bacanas $2\times8$ existem?

c) Quantos tabuleiros bacanas $8\times8$ existem?

20(BQ-OBMEP-2016-N3) Um baralho possui $32$ cartas divididas em $4$ tipos, cada um com $8$ cartas. De quantas formas podemos escolher $6$ cartas de modo que todos os quatro tipos de cartas estejam entre elas?

Dicas

2. Escolha os premiados e depois suas premiações.

3. b) Comece pintando uma casa específica de forma que as contas fiquem mais fáceis.

c) Divida em casos.

4. Preste atenção nas consequências de pintar um elemento e comece pelos menores.

5. Separe o problema em casos dependendo de onde a mulher do rapaz entre os outros senta.

6. Escolha o número central (o número par) e depois os ímpares.

7. Qual é a quantidade de cubinhos que não tem nenhuma face pintada? E qual é a quantidade de cubinhos que tem apenas uma face pintada?

8. Escolha os caracteres da senha de trás pra frente (direita para esquerda).

9. Divida o problema em dois casos: quando o número $1$ é posicionado em um dos triângulos centrais e quando é posicionado em um dos triângulos do canto.

10. a) De quantas formas o cubo pode ser posicionado na base quando uma face específica está virada pra cima?

b) Quando esse evento não ocorre?

c) Divida em dois casos: quando a face que estava em cima está em contato com a base e quando as faces que estão nas laterais do cubo estão em contato com a base.

11. Divida a pintura da parte inferior da figura em vários casos.

12. a) Divida em dois casos.

b) Pinte primeiro o triângulo.

c) Pinte primeiro o quadrado que está entre os quatro triângulos ou o triângulo entre os três quadrados.

13. Conte todos os pacotes que ele pode formar e depois subtraia os que não estão inclusos na contagem.

14. Ao fazer uma permutação onde existem termos iguais, é necessário eliminar os casos em que um deles está no lugar do outro para evitar casos repetidos.

15. b) Comece preenchendo uma casa e divida em casos dependendo de como foi colocada a primeira peça.

c) Similar ao item anterior.

16. b) Tente completar o quadrado.

d) Utilize os resultados dos itens anteriores e vá preenchendo as casas de forma que as contas fiquem menores.

17. Determine movimentos que a formiguinha pode fazer para poder percorrer todos os caminhos possíveis e não andar duas vezes seguidas na vertical.

18. Vá preenchendo as casas de forma que as contas fiquem menores.

19. b) Comece preenchendo cada quadrado $2\times2$ um por vez.

c) Use o resultado da item anterior.

20. Divida em casos dependendo do tipo das cartas que não tem tipo específico.

Soluções

1. O algarismo $0$ não pode ficar na posição das unidades de milhar, então tem $3$ escolhas para sua posição. Temos $5\cdot3=15$ possibilidades para escolher o algarismo ímpar e posicioná-lo, $4$ possibilidades para escolher um algarismo par (observe que não multiplicamos por $2$ para escolher sua posição, pois estaríamos contando as possibilidades de escolher os números pares duas vezes) e $3$ para escolher o outro algarismo par. Portanto o resultado final é $3\cdot15\cdot4\cdot3=540$.

2. Temos $\binom{5}{2}=10$ maneiras de escolher quem foram os premiados e cada um dos premiados pode ter recebido ouro, prata ou bronze. Assim a premiação pode ter ocorrido de $10\cdot 3\cdot 3=90$

3. a) $3$ opções para a parte de cima e $2$ para a de baixo sendo $6$ possibilidades.

b) Existem $3$ formas de preencher a área $2$ logo existem $2$ maneiras de preencher as áreas $1$ e $3$, $1$ maneira de preencher a área $4$ e $2$ maneiras de preencher a área $5$ sendo assim $24$ possibilidades.

c) Vamos dividir em $2$ casos um em que a cor de $2$ é igual a $3$ e outra em que são diferentes:

i. (igual) $3$ possibilidades para a área $1$, $2$ para a área $2$, $1$ para a área $3$ e $2$ para a área $4$ ($12$ formas).

ii. (diferente) $3$ possibilidades para a área $1$, $2$ para a área $2$, $1$ para a área $3$ e $1$ para a área $4$ ($6$ formas).

Totalizando $18$ possibilidades.

d) $12\cdot18\cdot6\cdot24$.

4. Note que todo par está na mesma cor que o $2$ mas se um número é da forma $2k$, ele tem a mesma cor que $k$ logo, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $12$, $14$, $15$, $16$, $18$ e $20$ tem a mesma cor. Portanto, temos $2$ possibilidades para $1$, $2$ para $2$, $2$ para $11$, $2$ para $13$, $2$ para $17$ e $2$ para $19$, totalizando $2^6=64$ formas de colorir.

5. Os rapazes devem se sentar juntos ao redor da mesa; escolhemos primeiramente três posições vizinhas e a ordem dos rapazes nas posições escolhidas, isso pode ser feito de $6\cdot 3!=36$ modos diferentes. Numere cada casal com $1$, $2$ ou $3$ e suponha que o rapaz $2$ esteja entre os outros rapazes. Agora temos dois casos:

A mulher $2$ não está entre as outras mulheres. Isso nos dá apenas duas possibilidades para acomodar as mulheres, pois a mulher $2$ pode sentar ao lado do rapaz $1$ ou $3$ e as outras mulheres terão apenas uma opção. Então o total de opções nesse caso é $2\cdot 36=72$.

A mulher $2$ esta sentada entre as outras mulheres. Nesse caso temos apenas uma possibilidade, já que os casais não podem sentar juntos, nos dando $1\cdot 36=36$ maneiras.

Então o total de possibilidades é $72+36=108$.

6. Escolhendo um número central par, basta multiplicarmos a quantidade de números ímpares menores que ele pela quantidade de números ímpares maiores que ele e menores que $20$. Somando esse resultado para os números pares de $2$ a $18$ obtemos $1\cdot9+2\cdot8+3\cdot7+4\cdot6+5\cdot5+6\cdot4+7\cdot3+8\cdot2+9\cdot1=165$ que é o nosso resultado.

7. Os cubinhos que não têm nenhuma face pintada são os que ficam internos ao cubo maior. Eles fazem parte de um cubo de dimensões $(n-2)(n-2)(n-2)$, o que dá um total de $(n-2)^3$ tais cubinhos. Os que têm exatamente uma face pintada são os cubinhos das faces do cubo maior que não tocam suas arestas. Em cada face há $(n-2)^2$ desses cubinhos, o que dá um total de $6(n-2)^2$ cubinhos com exatamente uma face pintada. Logo, deve-se ter $(n-2)^3=6(n-2)^2$. Como $n>2$ , esta equação é equivalente a $n-2=6$ , cuja solução é $n=8$.

8. Observamos primeiramente que há $4$ possibilidades de escolha para a 5ª posição ($6$, $7$, $8$ ou $9$). Feita uma dessas escolhas, vemos que há somente $4$ possibilidades de escolha para a 4ª posição. Utilizando exatamente o mesmo raciocínio, teremos também $4$ escolhas para cada uma das próximos posições. Assim a quantidade total de senhas que Fernanda poderá formar é $4^5=1024$.

9. Vamos dividir o problema em duas situações. Primeira situação: quando o número $1$ é colocado em um dos $8$ triângulos indicados na figura abaixo pela cor amarela (triângulos centrais). Escolhido qualquer um dos $8$ triângulos amarelos para colocar o número $1$, haverá $3$ caminhos para se preencherem os números de $1$ a $16$ atendendo as condições do problema. Portanto, há $8\cdot 3=24$ maneiras de fazer o preenchimento começando em um triângulo amarelo.

Segunda situação: quando o número $1$ é colocado em um triângulo branco (triângulo de canto). Escolhido qualquer um dos $8$ triângulos brancos para colocar o número $1$, haverá $4$ caminhos para se preencherem os números de $1$ a $16$ atendendo as condições do problema. Portanto, há $8\cdot 4=32$ maneiras de fazer o preenchimento começando em um triângulo amarelo.

Portanto o número total de maneiras é $24+32=56$

10. a) Para cada face virada para a base, o cubo pode ser encaixado de $4$ maneiras na base, então o total de maneiras de se encaixar o cubo é $4\cdot 6=24$.

b) Observe que esse evento não ocorre apenas quando a face $6$ está no lugar da face $1$ da figura, que pode ocorrer de $4$ maneiras distintas (girando o cubo). Como o número total de maneiras que o cubo pode ser encaixado na base é $24$, a resposta deste item é $24-4=20$.

c) Suponha que inicialmente a face com o número $6$ esteja em contato com a base e que o número escrito na face oposta à $6$ seja o $1$. Se a face $1$ está em contato com a base há $2$ reposicionamentos nos quais nenhum outro número permanece na mesma posição de antes. Para cada um dos números do conjunto $\{2,3,4,5\}$, existem $3$ reposicionamentos em que esse número está em contato com a base e os demais números não estão na posição de antes. Logo, o total de reposicionamentos em que nenhum número permanece na sua posição original é $2+3\cdot4=14$

11. Primeiro pintamos o quadrilátero pequeno e o triângulo superior, o que pode ser feito de $3\cdot2=6$ maneiras diferentes.Agora dividiremos o problema em quatro casos onde letras iguais representam cores iguais e a cor da região $a$ é diferente da cor da região $b$.

 

Caso 1: Temos $2$ possibilidades para $a$, $2$ para $A$ e $2$ para $B$, totalizando $2\cdot2\cdot2=8$ possibilidades.

Caso 2: Temos $2$ possibilidades para $a$, $1$ para $b$, $2$ para $A$ e $1$ para $B$, totalizando $2\cdot1\cdot2\cdot1=4$ possibilidades.

Caso 3: Análogo ao caso anterior, temos $4$ possibilidades.

Caso 4: Temos $2$ possibilidades para $a$, $1$ para $b$, $1$ para $A$ e $1$ para $B$, totalizando $2\cdot1\cdot1\cdot1=2$ possibilidades.

Portanto o número total de maneiras de pintar a figura é $6(8+4+4+2)=108$.

12. a) Se João pintar o quadrado de azul ou vermelho, ele terá como escolhas a cor oposta (vermelho se pintou de azul e azul se pintou de verde) e amarelo para o triângulo. Se ele pintar o quadrado de verde, ele terá as escolhas azul, vermelho e amarelo para o triângulo. Logo ele pode pintar a figura de $2\cdot 2 + 1\cdot3=7$ maneiras diferentes.

b) Se João escolher azul ou vermelho para o triângulo, cada um dos quadrados poderá ser pintado de duas cores; se ele escolher amarelo para o triângulo, cada quadrado poderá ser pintado de três cores. Logo o número de maneiras diferentes de pintar essa figura é $2\cdot 2\cdot2\cdot2+1\cdot3\cdot3\cdot3=43$.

c) Se João escolher azul ou vermelho para o quadrado entre os quatro triângulos, os triângulos adjacentes poderão ser pintados de $2\cdot2\cdot2\cdot2=16$ maneiras diferentes; em metade dessas maneiras o triângulo entre os três quadrados é azul ou vermelho, caso em que os quadrados em contato apenas com esse triângulo poderão ser pintados de $2\cdot2=4$ maneiras e na outra metade ele é amarelo, quando os quadrados adjacentes poderão ser pintados de $3\cdot3=9$ maneiras diferentes. Nesse caso, a figura poderá ser pintada de $16(4+9)=208$ maneiras diferentes. Se ele escolher verde para o quadrado entre os quatro triângulos, os triângulos adjacentes poderão ser pintados de $3\cdot3\cdot3=27$ maneiras diferentes; em dois terços dessas maneiras o triângulo entre os três quadrados é azul ou vermelho, caso em que os quadrados adjacentes poderão ser pintados de $2\cdot2=4$ maneiras e no terço restante ele é amarelo,quando os quadrados adjacentes poderão ser pintados de $3\cdot3=9$ maneiras diferentes.Nesse caso, a figura poderá ser pintada de $27(2\cdot4+1\cdot9)=459$ maneiras diferentes. No total, a figura poderá ser pintada de $208+459=667$ maneiras distintas.

13. Ele pode formar $6\cdot 7\cdot 5=210$ pacotes de figurinhas com qualquer quantidade de figurinhas em cada, pois das figurinhas da Alemanha por exemplo, ele tem a escolha de colocar $0$, $1$, $2$, $3$, $4$ ou $5$ figurinhas ($6$ escolhas no total), e os outros casos são análogos. Agora basta tirarmos desses $210$ possíveis pacotes os que contém zero, uma ou duas figurinhas. Com $0$ figurinhas há somente $1$ pacote. Com $1$ figurinha há $3$ pacotes, cada um com uma figurinha diferente. Com $2$ figurinhas há $6$ pacotes: AA, BB, CC, AB, AC, BC, onde A é uma figurinha da Alemanha, B é uma figurinha do Brasil e C é uma figurinha da Colômbia. Assim o número de pacotes que Bruno poderá formar seguindo as condições do enunciado são $210-(1+3+6)=200$.

14. a) Existem $6$ objetos para para permutar, mas é necessário desconsiderar a permutações dos copos do 1º nível ($3!$) e do 2º nível ($2!$). Logo:$\dfrac{6!}{3!\cdot2!}$.

b) Analogamente temos: $\dfrac{10!}{4!\cdot3!\cdot2!}$.

c) Temos $\dfrac{n(n+1)}{2}$ copos, mas temos que descontar as permutações de copos do mesmo nível. Logo: $\dfrac{[\frac{n(n+1)}{2}]!}{n!(n-1)!\dots2!1!}$.

15. a)

b) Vamos começar preenchendo o quadrado $(B,1)$ de $2$ formas:

i. colocar um peça ocupando $(B,1)$ e $(B,2)$ assim só existe uma forma de preencher.

ii. colocar um peça ocupando $(B,1)$ e $(C,1)$ assim temos $3$ formas de preencher.

Totalizando $4$ formas.

c) Vamos começar preenchendo o quadrado $(C,3)$, $(C,4)$, $(D,3)$, $(D,4)$ de $3$ formas:

i. colocar uma peça cobrindo $(C,3)$ e $(C,4)$ e outra cobrindo $(D,3)$ e $(D,4)$ existem $2$ formas de cobrir os quadrados $2\times2$ que faltam no tabuleiro somando $16$ formas, esse caso é análogo a colocar uma peça cobrindo $(C,3)$ e $(D,3)$ e outra em $(C,4)$ e $(D,4)$.

ii. colocar uma peça cobrindo $(B,3)$ e $(C,3)$ outra em $(B,4)$ e $(C,4)$ outra em $(D,3)$ e $(D,4)$. Assim temos $1$ forma de cobrir $(A,3)$ e $(A,4)$ e $2$ formas de cobrir os $3$ quadrados $2\times2$ que faltam no tabuleiro somando $8$ formas mas esse caso é análogo a girar as peças que foram colocadas no meio tendo $4\cdot8=32$ formas no total.

iii. colocar peças cobrindo $(B,3)$ e $(C,3)$, $(B,4)$ e $(C,4)$, $(D,3)$ e $(E,3)$ e outra em $(D,4)$ e $(E,4)$ análogo ao caso anterior temos $4$ casos para completar o tabuleiro e $2$ formas de girar as peças colocadas no centro.

Totalizando $72$ formas de completar o tabuleiro.

16. a)

b) Devido às posições do $1$ nos quadrados $A$ e $D$, é obrigatório que no quadrado $B$ o $1$ seja posicionado no canto inferior esquerdo. Analogamente, o $2$ deve ser colocado nesse mesmo lugar fazendo com que não haja forma de completar o quadrado.

c)

d) Existem $4!$ formas de preencher o quadrado $A$, $4$ formas de colocar o $1$ no quadrado $D$ e $3$ formas de completar o $D$ (como no item anterior) depois disso, existe apenas uma forma de preencher os quadrados $B$ e $C$. Totalizando $4!\cdot4\cdot3=288$ quadrados especiais.

17. Há $3$ formas distintas de a formiga chegar, saindo de $P$, a um dos pontos $A$ ou $B$ sem andar pelo segmento vertical $AB$ (duas maneiras de chegar a $A$ - horizontal/vertical ou vertical/horizontal e uma só de chegar a $B$ - vertical/vertical/horizontal).
A partir de $A$ ou $B$, podemos definir os movimentos $H$, no qual a formiga anda um segmento na horizontal e $VH$, no qual a formiga anda um segmento vertical e outro horizontal em seguida. Observe que assim ela pode escolher qualquer um dos dois movimentos em qualquer ponto antes de $Q$ e do ponto logo abaixo e com $9$ movimentos ela chega em $Q$ ou no ponto logo abaixo de $Q$, o qual tem apenas uma possibilidade de levar em $Q$. Assim o total de maneiras para que ela chegue de $P$ a $Q$ é $3\cdot 2^9=1536$.

18. Existem $2$ possibilidades para o quadrado do canto (chame esse valor de $x$), escolhido ele, existem $3$ possibilidades para colocar o $x$ na primeira fila (suponha que foi escolhida a coluna $A$) e $3$ na primeira coluna (suponha que foi escolhida a coluna $B$) sobrando assim um quadrado $3\times3$. Vamos dividir em casos para preencher esse quadrado restante:

i. Colocar $x$ em $(A,B)$. Dessa forma existe apenas uma forma de preencher.

ii. Não colocar $x$ em $(A,B)$. Assim temos $2$ possibilidades de colocar $x$ e $A$ e $2$ de colocar $x$ em $B$.

Totalizando $2\cdot3\cdot3\cdot(1+2\cdot2)=90$ formas de preencher o quadrado.

19. a)

b) Os números dentro dos quadrados representam a quantidade de possíveis valores para o quadrado. Para o quadrado $2\times2$ mais a esquerda, temos $4!$ formas de colocar as letras de $A$ a $D$ para cada coluna a partir da terceira (da esquerda para a direita) temos $2$ possibilidades pois ela faz parte de um quadrado $2\times2$ como a coluna anterior (que já está preenchida).

Totalizando $4!\cdot2^6=1536$.

c) Ao fixar o quadrado $2\times2$ do canto superior esquerdo, temos $64$ possibilidades para as $2$ primeiras linhas, vamos dividir em $2$ casos.

i. Caso a primeira linha seja composta por apenas $2$ letras intercaladas, todas as outras também serão, porém existem $2$ possibilidades para intercalar somando $64$ possibilidades nesse caso.

ii. Em todos as outras $63$ possibilidades, existe apenas uma forma de preencher. Ou seja, ao fixar o quadrado $2\times2$ do canto superior esquerdo, temos $127$ como existem $4!$ para o quadrado, temos $4!\cdot127$ possibilidades.

20. Vamos dividir em dois casos, em um dentre as cartas que não tem tipo específico tem tipos diferentes (i), em outro eles serão iguais (ii):

i. $\binom{4}{2}$ possibilidades de escolher os tipos que se repetem, ${\binom{8}{2}}^2$ formas de escolher as cartas dos tipos que se repetem ${\binom{8}{1}}^2$ formas de escolher as cartas dos tipos que não se repetem.

ii. $\binom{4}{1}$ possibilidades de escolher o tipos que aparece $3$ vezes, $\binom{8}{3}$ formas de escolher as cartas dos tipo que se repete ${\binom{8}{1}}^3$ formas de escolher as cartas dos tipos que não se repetem.

Totalizando $415744$ possibilidades.

Referências

Site da OBMEP: http://www.obmep.org.br/provas.htm