Haroldo Costa Silva FilhoMatemática

Análise Combinatória · Teoria e Questões de Competições

Capítulo 1 — Princípios de Contagem

O capítulo na íntegra: a teoria construída do zero, os exemplos e as 107 questões com a resolução escrita por extenso. Nenhum gabarito solto.

O capítulo 1 do livro, com as 107 questões e a resolução de cada uma. Os números e a ordem são os da edição publicada.

Questão 1.1

A viagem se decompõe em duas etapas: primeiro escolhemos um dos 5 caminhos de A até B e, em seguida, um dos 3 caminhos de B até C. Para cada escolha da primeira etapa há 3 possibilidades para a segunda; pelo MP: 5 × 3 = 15. Resposta: 15 caminhos.

Ver a resolução

A viagem se decompõe em duas etapas: primeiro escolhemos um dos 5 caminhos de A até B e, em seguida, um dos 3 caminhos de B até C. Para cada escolha da primeira etapa há 3 possibilidades para a segunda; pelo MP: 5 × 3 = 15. Resposta: 15 caminhos.

voltar ao índice

Questão 1.2

Quantos são os pares (x,y) de números inteiros que satisfazem x2+y2 = 25? E quantos satisfazem x2 + y2 = 2027?

Ver a resolução

Para 25. Como x2 ≤ 25, basta testar x ∈ {0,±1,...,±5} e ver quando 25 − x2 é quadrado perfeito. Isso só acontece para x2 ∈ {0,9,16,25}, o que dá as decomposições 25 = 0 + 25 = 9 + 16 = 16 + 9 = 25 + 0. Cada uma produz os pares com todos os sinais possíveis: (±5,0), (0,±5), (±3,±4), (±4,±3), isto é, 2 + 2 + 4 + 4 = 12 pares. Geometricamente, são os 12 pontos de coordenadas inteiras sobre a circunferência de raio 5. Para 2027. Aqui não adianta procurar: não há nenhum. Todo quadrado perfeito deixa resto 0 ou 1 na divisão por 4, pois (2k)2 = 4k2 e (2k + 1)2 = 4(k2 + k) + 1. Somando dois quadrados, os restos possíveis são 0+0, 0+1, 1+0 e 1+1, ou seja, x2+y2 deixa resto 0, 1 ou 2 — nunca 3. E 2027 = 4 · 506 + 3 deixa resto 3. Resposta: 12 pares para 25; nenhum para 2027.

voltar ao índice

Questão 1.3

Ao cume de uma montanha conduzem cinco caminhos. De quantas maneiras um turista pode subir e descer? E com a condição de que a subida e a descida se deem por caminhos diferentes?

Ver a resolução

Subir e descer livremente: 5 × 5 = 25. Por caminhos diferentes: 5 × 4 = 20. Resposta: 25 maneiras; 20 com caminhos distintos.

voltar ao índice

Questão 1.4

Numa granja há 20 ovelhas e 24 porcos. De quantos modos se pode escolher uma ovelha e um porco? Feita essa escolha, de quantas maneiras se pode escolher novamente uma ovelha e um porco?

Ver a resolução

Primeira escolha: 20 × 24 = 480. Após retirar uma ovelha e um porco: 19 × 23 = 437. Resposta: 480; depois, 437.

voltar ao índice

Questão 1.5

De quantas formas se podem indicar, no tabuleiro de xadrez, duas casas, uma branca e uma preta? E se não houver restrição quanto às cores?

Ver a resolução

O tabuleiro tem 32 casas brancas e 32 pretas: 32×32 = 1024. Sem restrição de cor, escolhem-se duas casas distintas (ordenadamente, uma “primeira” e uma “segunda”): 64 × 63 = 4032. Resposta: 1024; sem restrição, 4032.

voltar ao índice

Questão 1.6

De quantas maneiras se podem escolher no tabuleiro de xadrez uma casa branca e uma preta que não estejam na mesma linha nem na mesma coluna?

Ver a resolução

Escolhida a casa branca (32 modos), sua linha contém 4 casas pretas e sua coluna outras 4; restam 32 − 8 = 24 casas pretas permitidas: 32 × 24 = 768. Resposta: 768 maneiras.

voltar ao índice

Questão 1.7

Há 6 pares de luvas de tamanhos distintos. De quantas maneiras se podem escolher uma luva da mão esquerda e outra da direita de forma que sejam de tamanhos diferentes?

Ver a resolução

Luva esquerda: 6 modos; luva direita de tamanho diferente: 5 modos: 6 × 5 = 30. Resposta: 30 maneiras.

voltar ao índice

Questão 1.8

Numa livraria há 6 exemplares do romance Rudin, 3 de Ninho de Fidalgos e 4 de Pais e Filhos. Além disso, há 5 volumes contendo Rudin e Ninho de Fidalgos juntos e 7 contendo Ninho de Fidalgos e Pais e Filhos. De quantos modos se pode efetuar uma compra que contenha um exemplar de cada um dos três romances?

Ver a resolução

Separamos por tipo de compra (AP), usando o MP em cada caso: três volumes avulsos: 6×3×4 = 72; o volume duplo (R+N) e um Pais e Filhos: 5×4 = 20; o volume duplo (N+P) e um Rudin: 7×6 = 42. Total: 72 + 20 + 42 = 134. Resposta: 134 modos.

voltar ao índice

Questão 1.9

O mesmo problema, se além disso a livraria tem 3 volumes contendo Rudin e Pais e Filhos.

Ver a resolução

Acrescenta-se o caso: volume duplo (R+P) e um Ninho de Fidalgos: 3 × 3 = 9. Total: 134 + 9 = 143. Resposta: 143 modos.

voltar ao índice

Questão 1.10

Numa cesta há 12 maçãs e 10 laranjas. Ivan toma uma maçã ou uma laranja; em seguida, Nadia escolhe uma maçã e uma laranja. Em que caso Nadia tem maior liberdade de escolha: quando Ivan toma uma maçã ou quando toma uma laranja?

Ver a resolução

Se Ivan toma uma maçã, restam 11 maçãs e 10 laranjas: Nadia escolhe de 11×10 = 110 modos. Se Ivan toma uma laranja: 12×9 = 108 modos. Resposta: Quando Ivan toma uma maçã (110 contra 108).

voltar ao índice

Questão 1.11

Há três piões com 6, 8 e 10 faces, respectivamente. De quantas maneiras diferentes podem cair? E se soubermos que pelo menos dois deles caíram sobre a face marcada com o algarismo 1?

Ver a resolução

Sem restrição: 6×8×10 = 480. Com pelo menos dois “1”: contamos por pares que mostram 1, deixando o terceiro livre: 1o e 2o: 1 × 1 × 10 = 10; 1o e 3o: 1 × 8 × 1 = 8; 2o e 3o: 6 × 1 × 1 = 6. A soma 10 + 8 + 6 = 24 conta o caso “três 1” três vezes (uma em cada parcela); descontamos duas: 24 − 2 = 22. Resposta: 480 maneiras; 22 com pelo menos dois “1”.

voltar ao índice

Questão 1.12

De quantas formas se pode confeccionar uma bandeira de três faixas horizontais de cores distintas, dispondo-se de tecido de 5 cores? E se uma das faixas deve ser vermelha?

Ver a resolução

As faixas são ordenadas (superior, média, inferior): 5×4×3 = 60. Com uma faixa vermelha: escolhe-se a posição do vermelho (3 modos) e as outras duas faixas com as 4 cores restantes: 4 × 3 = 12: 3 × 12 = 36. Resposta: 60 bandeiras; 36 com faixa vermelha.

voltar ao índice

Questão 1.13

Quantos dicionários é preciso editar para que se possam efetuar traduções diretas entre quaisquer dos cinco idiomas: espanhol, russo, inglês, francês e alemão?

Ver a resolução

Um dicionário traduz de um idioma para outro; para traduções diretas em ambos os sentidos são necessários dois dicionários por par de idiomas (por exemplo, russo–francês e francês–russo). Assim, precisamos de um dicionário para cada par ordenado de idiomas distintos: o idioma de origem pode ser escolhido de 5 modos e, para cada origem, o idioma de destino de 4 modos. Pelo MP: 5 × 4 = 20. Resposta: 20 dicionários.

voltar ao índice

Questão 1.14

Quantos dicionários será preciso acrescentar se o número de idiomas passar a 10?

Ver a resolução

Com 10 idiomas: 10×9 = 90. Acréscimo: 90−20 = 70. Resposta: 70 dicionários.

voltar ao índice

Questão 1.15

De quantas maneiras se pode escolher, de um baralho completo de 52 cartas, uma carta de cada naipe? E com a condição de que não haja duas cartas de mesmo valor (dois reis, dois dez etc.)?

Ver a resolução

Uma carta de cada um dos 4 naipes: 134 = 28561. Sem valores repetidos: o primeiro naipe tem 13 opções, o segundo 12 (exclui o valor já usado), o terceiro 11 e o quarto 10: 13 × 12 × 11 × 10 = 17160. Resposta: 28561; sem valores repetidos, 17160.

voltar ao índice

Questão 1.16

De quantos modos se pode escolher de um baralho de 52 cartas uma carta de cada naipe, de forma que as cartas dos naipes vermelhos e as dos naipes pretos formem pares de mesmo valor?

Ver a resolução

Escolhe-se o valor comum das duas cartas vermelhas (copas e ouros): 13 modos; e o valor comum das duas pretas (espadas e paus): 13 modos: 13 × 13 = 169. Resposta: 169 modos.

voltar ao índice

Questão 1.17

Os ingleses costumam dar vários nomes a seus filhos. De quantas formas se pode dar nome a uma criança, se o número total de nomes disponíveis é 300 e lhe são dados no máximo três nomes (distintos e em ordem)?

Ver a resolução

Um nome: 300 modos; dois nomes ordenados: 300 × 299 = 89700; três: 300 × 299 × 298 = 26730600. Pelo AP: 300 + 89700 + 26730600 = 26820600. Resposta: 26820600 formas.

voltar ao índice

Questão 1.18

É preciso enviar 6 cartas urgentes. De quantas maneiras isso pode ser feito, se há três mensageiros disponíveis e cada carta pode ser entregue a qualquer um deles?

Ver a resolução

Decompomos a entrega em 6 etapas: para a 1a carta, escolhemos um dos 3 mensageiros; para a 2a carta, novamente um dos 3 (o mesmo mensageiro pode levar várias cartas); e assim por diante, até a 6a carta. Pelo MP: 3 × 3 × ··· × 3 = 36 = 729. | {z } 6 fatores Atenção ao papel de cada número: é “para cada carta, um mensageiro” (base 3, expoente 6), e não o contrário — 63 contaria outra coisa. Resposta: 729 maneiras.

voltar ao índice

Questão 1.19

Numa estação ferroviária há m semáforos. Quantos sinais diferentes podem ser dados, se cada semáforo tem três estados: vermelho, amarelo e verde?

Ver a resolução

Um “sinal” da estação é a configuração conjunta dos m semáforos. Examinemos os casos pequenos: com m = 1 semáforo há 3 sinais (vermelho, amarelo, verde); com m = 2, cada um dos 3 estados do primeiro combina-se com os 3 do segundo: 3×3 = 9 sinais. Em geral, cada semáforo é uma etapa com 3 opções, independentes entre si; pelo MP, 3 × 3 × ··· × 3 = 3m. | {z } m fatores Resposta: 3m sinais.

voltar ao índice

Questão 1.20

Em certo Estado não havia dois habitantes com a mesma quantidade de dentes. Qual pode ser a população máxima desse Estado, se o número máximo de dentes é 32?

Ver a resolução

As quantidades possíveis de dentes são 0,1,2,...,32: são 33 valores; cada habitante deve ter um valor diferente. Resposta: 33 habitantes.

voltar ao índice

Questão 1.21

As placas de automóvel são formadas por uma, duas ou três letras seguidas de quatro algarismos. Determine a quantidade total dessas placas, utilizando as 32 letras do alfabeto russo.

Ver a resolução

Partes literais: 32 + 322 + 323 = 32 + 1024 + 32768 = 33824. Cada uma combina-se com 104 sequências de algarismos: 33824 × 104 = 338240000. Resposta: 338240000 placas.

voltar ao índice

Questão 1.22

O saguão do prédio sede de uma multinacional possui quatro portas, uma em cada uma das direções Norte, Sul, Leste e Oeste. De quantas maneiras distintas uma pessoa dispõe para entrar e sair do prédio por uma dessas portas?

Ver a resolução

A pessoa pode entrar por qualquer uma das 4 portas e sair por qualquer uma das 4 portas. Pelo MP: 4 × 4 = 16. Resposta: 16 maneiras.

voltar ao índice

Questão 1.23

Dois dados, um vermelho e outro verde, são lançados. Quantos são os possíveis resultados distintos? Quantos são os possíveis resultados distintos se os dois dados devem apresentar resultados diferentes?

Ver a resolução

Cada dado tem 6 faces; pelo MP: 6×6 = 36 resultados. Se os resultados devem ser diferentes, o segundo dado tem apenas 5 opções: 6 × 5 = 30. Resposta: 36 resultados; 30 com faces diferentes.

voltar ao índice

Questão 1.24

A ligação entre as cidades de Itapipoca e Peritoró pode ser feita por vias ferroviária, marítima, rodoviária e aérea. De quantas maneiras distintas uma pessoa pode fazer a viagem Itapipoca–Peritoró–Itapipoca sem utilizar na volta o mesmo meio de transporte utilizado na ida?

Ver a resolução

Para a ida há 4 escolhas de meio de transporte; para a volta, qualquer meio exceto o da ida: 3 escolhas. Pelo MP: 4 × 3 = 12. Resposta: 12 maneiras.

voltar ao índice

Questão 1.25

Qual é, aproximadamente, o número de sequências distintas de caras e coroas que podemos obter ao lançarmos uma moeda 100 vezes? (Considere 210 ≈ 103.)

Ver a resolução

Cada lançamento tem 2 resultados possíveis; pelo MP o total é (cid:16)210(cid:17)10 (cid:16)103(cid:17)10 2100 = ≈ = 1030. Resposta: Cerca de 1030 sequências.

voltar ao índice

Questão 1.26

Quantos são os números que podemos formar com todos os dígitos 1,1,1,1,1,1,1,2 e 3?

Ver a resolução

São números de 9 algarismos com sete 1’s, um 2 e um 3. Basta escolher a posição do 2 (9 modos) e a posição do 3 (8 modos restantes); as demais posições recebem 1: 9 × 8 = 72. Resposta: 72 números.

voltar ao índice

Questão 1.27

Dispondo das cores verde, amarelo, azul e branco, de quantos modos distintos podemos pintar 7 casas enfileiradas de modo que cada casa seja pintada de uma só cor e duas casas vizinhas não sejam pintadas com a mesma cor?

Ver a resolução

A primeira casa pode receber qualquer uma das 4 cores. Cada casa seguinte pode receber qualquer cor exceto a da casa anterior: 3 opções. Pelo MP: 4 × 36 = 4 × 729 = 2916. Resposta: 2916 modos.

voltar ao índice

Questão 1.28

As antigas placas para automóveis, formadas por duas letras seguidas de quatro algarismos, foram substituídas por placas com três letras seguidas de quatro algarismos. Utilizando um alfabeto de 26 letras e supondo que qualquer sequência de letras e algarismos seja permitida, quantos veículos a mais podem ser emplacados?

Ver a resolução

Sistema novo: 263×104 placas; sistema antigo: 262×104 placas. A diferença é 263 · 104 − 262 · 104 = 262 · 104(26 − 1) = 676 · 25 · 104 = 169000000. Resposta: 169 milhões de veículos a mais.

voltar ao índice

Questão 1.29

Dispondo de 5 livros diferentes de Matemática, 6 livros diferentes de Física e 8 livros diferentes de Química, de quantas maneiras podemos escolher um par (não ordenado) de livros que não sejam da mesma matéria?

Ver a resolução

Um par Matemática–Física pode ser escolhido de 5 × 6 = 30 modos; um par Matemática–Química, de 5×8 = 40 modos; um par Física–Química, de 6 × 8 = 48 modos. Pelo AP: 30 + 40 + 48 = 118. Resposta: 118 pares.

voltar ao índice

Questão 1.30

Seis livros distintos de Matemática serão arrumados em fila numa estante. De quantos modos isto pode ser feito se dois determinados livros não devem ficar lado a lado?

Ver a resolução

Total de arrumações: 6! = 720. Arrumações com os dois livros juntos: tratando o par como um bloco, 5! × 2! = 240. Logo, 720 − 240 = 480. Resposta: 480 modos.

voltar ao índice

Questão 1.31

Quantas coleções não vazias e distintas podem ser formadas a partir de cinco maçãs idênticas e oito laranjas também idênticas?

Ver a resolução

Como as maçãs são idênticas entre si e as laranjas são idênticas entre si, uma coleção fica determinada apenas pelas quantidades de maçãs (0 a 5: 6 opções) e de laranjas (0 a 8: 9 opções). Pelo MP: 6 × 9 = 54 coleções. Excluindo a coleção vazia: 54 − 1 = 53. Resposta: 53 coleções.

voltar ao índice

Questão 1.32

Quantos são os divisores positivos de 64800? Destes, quantos são pares? E múltiplos de 30?

Ver a resolução

Fatorando: 64800 = 648×100 = 23·34·22·52 = 25·34·52. Todo divisor tem a forma 2a3b5c com 0 ≤ a ≤ 5, 0 ≤ b ≤ 4, 0 ≤ c ≤ 2. Pelo MP: (5 + 1)(4 + 1)(2 + 1) = 90 divisores. Pares: a ≥ 1, logo 5 × 5 × 3 = 75. Múltiplos de 30: como 30 = 2 · 3 · 5, precisamos de a ≥ 1, b ≥ 1, c ≥ 1: 5 × 4 × 2 = 40. Resposta: 90 divisores; 75 pares; 40 múltiplos de 30.

voltar ao índice

Questão 1.33

Existem quatro estradas ligando a cidade A à cidade B, três estradas ligando a cidade B à cidade C e duas estradas ligando A diretamente a C. Considere as afirmações: 1. Existem ao todo 14 rotas distintas ligando a cidade A à cidade C. 2. Existem 196 rotas distintas para se ir e voltar de A até C. 3. Existem 144 rotas distintas para se ir e voltar de A até C visitando B nos dois trajetos. 4. Existem 122 rotas distintas para se ir e voltar de A até C sem utilizar qualquer estrada duas vezes. Quais sentenças são verdadeiras? Justifique.

Ver a resolução

(1) De A a C via B: 4 × 3 = 12 rotas; diretamente: 2 rotas. Pelo AP: 12 + 2 = 14. Verdadeira. (2) Ida: 14 opções; volta: 14 opções. Pelo MP: 142 = 196. Verdadeira. (3) Ida via B: 12; volta via B: 12. Total 12 × 12 = 144. Verdadeira. (4) Contamos ida e volta sem repetir estrada. Ida via B (12 modos): volta via B sem repetir estradas: 2×3 = 6 modos (restam 2 estradas C−B e 3 estradas B−A); volta direta: 2 modos. Subtotal: 12×(6+2) = 96. Ida direta (2 modos): volta direta sem repetir: 1 modo; volta via B: 12 modos. Subtotal: 2 × (1 + 12) = 26. Total: 96 + 26 = 122. Verdadeira. Resposta: Todas as quatro sentenças são verdadeiras.

voltar ao índice

Questão 1.34

Dez pessoas — A, B, C, D, E, F, G, H, I e J — participam da fundação de um clube de Matemática. A primeira tarefa é escolher um Presidente, um Secretário e um Tesoureiro, dentre as pessoas deste grupo, sem acúmulo de cargos. De quantos modos distintos pode ser feita a escolha se A se recusa a ser o Presidente e B se recusa a ser o Secretário?

Ver a resolução

Sem restrições: 10 × 9 × 8 = 720 escolhas. Seja X o conjunto das escolhas com A na presidência (9 × 8 = 72) e Y com B na secretaria (9×8 = 72); escolhas com A presidente e B secretário: |X∩Y | = 8. Por inclusão–exclusão, as escolhas proibidas somam 72 + 72 − 8 = 136, restando 720 − 136 = 584. Resposta: 584 modos.

voltar ao índice

Questão 1.35

Ao escrevermos todos os números inteiros de 1 até 2222, quantas vezes escrevemos o algarismo zero?

Ver a resolução

Contamos o zero em cada posição. Unidades: 10,20,...,2220: 2220 − 1010 + 1 = 222 zeros. Dezenas: números da forma ∗0∗ com centenas 1 a 9 (90 números de 100–999), 1000–1999 (100 números) e 2000–2222 (2000–2009, 2100–2109, 2200–2209: 30 números): 90 + 100 + 30 = 220 zeros. Centenas: 1000–1099 e 2000–2099: 100 + 100 = 200 zeros. Total: 222 + 220 + 200 = 642. Resposta: 642 vezes.

voltar ao índice

Questão 1.36

Escrevem-se os números de 1 a 8888. Quantas vezes o algarismo 8 é escrito?

Ver a resolução

Unidades (8,18,...,8888): 8888 − 810 + 1 = 889. Dezenas: blocos 80–89, 180–189,...; até 8888 há 88 × 10 + 9 = 889 ocorrências (8880–8888 contribui com 9). Centenas: 800–899, 1800–1899,...: 8 × 100 + 89 = 889 ocorrências (8800–8888 contribui com 89). Milhares: 8000–8888: 889 ocorrências. Total: 889 × 4 = 3556. Resposta: 3556 vezes.

voltar ao índice

Questão 1.37

Quantos são os números pares compreendidos entre 20000 e 70000 que possuem algarismos distintos?

Ver a resolução

Números d1d2d3d4d5 com d1 ∈ {2,3,4,5,6}, d5 par e todos os algarismos distintos. Caso 1: d1 par (d1 ∈ {2,4,6}, 3 modos): d5 par e d5 ≠ d1: 4 modos; d2,d3,d4 escolhidos entre os 8 algarismos restantes: 8 × 7 × 6 = 336. Subtotal: 3 × 4 × 336 = 4032. Caso 2: d1 ímpar (d1 ∈ {3,5}, 2 modos): d5 par: 5 modos; d2,d3,d4: 336. Subtotal: 2 × 5 × 336 = 3360. Total: 4032 + 3360 = 7392. Resposta: 7392 números.

voltar ao índice

Questão 1.38

Dispondo de 5 cores distintas, de quantos modos podemos colorir os quatro quadrantes de um círculo, cada quadrante com uma só cor, se quadrantes cuja fronteira é uma linha não podem receber a mesma cor?

Ver a resolução

Os 4 quadrantes formam um ciclo Q1Q2Q3Q4, em que cada um faz fronteira com o anterior e o seguinte (quadrantes opostos se tocam apenas no centro, e podem ter a mesma cor). Q1 faz fronteira com Q2 e Q4; os pares opostos (Q1,Q3) e (Q2,Q4) não têm fronteira comum. Colorimos Q1 (5 modos) e Q2 (4 modos). Separamos em casos conforme Q3: Q3 com cor diferente de Q1: 3 modos; então Q4 ≠ Q3 e Q4 ≠ Q1: 3 modos. Subtotal: 5 × 4 × 3 × 3 = 180. Q3 com a mesma cor de Q1: 1 modo; então Q4 só precisa diferir dessa cor: 4 modos. Subtotal: 5 × 4 × 1 × 4 = 80. Total: 180 + 80 = 260. Resposta: 260 modos.

voltar ao índice

Questão 1.39

De um baralho comum de 52 cartas, extraem-se sucessivamente e sem reposição duas cartas. De quantos modos isto pode ser feito se:

a) a primeira carta é uma dama e a segunda não é um rei? b) a primeira carta é uma dama e a segunda não é de espadas? c) a primeira carta é de espadas e a segunda não é uma dama?

Ver a resolução

a) Primeira carta: 4 damas. Segunda: das 51 restantes, excluem-se os 4 reis: 47 opções. Total: 4 × 47 = 188.

b) Caso 1: a primeira é a dama de espadas (1 modo); a segunda não pode ser de espadas: 51−12 = 39 opções. Subtotal: 39. Caso 2: a primeira é dama de outro naipe (3 modos); a segunda não pode ser de espadas: 51 − 13 = 38 opções. Subtotal: 3 × 38 = 114. Total: 39 + 114 = 153.

c) Caso 1: a primeira é a dama de espadas (1 modo); a segunda não pode ser dama: 51 − 3 = 48 opções. Subtotal: 48. Caso 2: a primeira é outra carta de espadas (12 modos); a segunda não pode ser dama: 51−4 = 47 opções. Subtotal: 12 × 47 = 564. Total: 48 + 564 = 612. Resposta:

a) 188;

b) 153;

c) 612 modos.

voltar ao índice

Questão 1.40

Um vagão de metrô possui 10 bancos individuais, sendo 5 de frente e 5 de costas. De 10 passageiros, 4 preferem sentar de frente, 3 preferem sentar de costas e os demais não têm preferência. De quantos modos os passageiros podem se sentar respeitando-se as preferências?

Ver a resolução

Os 4 que preferem frente escolhem, ordenadamente, 4 dos 5 bancos de frente: 5×4×3×2 = 120 modos. Os 3 que preferem costas: 5 × 4 × 3 = 60 modos. Restam 3 passageiros para os 3 bancos restantes (1 de frente e 2 de costas): 3! = 6 modos. Pelo MP: 120 × 60 × 6 = 43200. Q2 Q1Q3 Q4 Resposta: 43200 modos.

voltar ao índice

Questão 1.41

Um curso de línguas oferece aulas de Inglês, Espanhol e Francês, cada língua com duas aulas semanais em dias distintos, escolhidos dentre segundafeira, quarta-feira e sexta-feira, havendo exatamente duas aulas por dia. De quantos modos distintos podemos fazer o horário semanal?

Ver a resolução

São 6 aulas para 3 dias × 2 horários = 6 posições. Cada língua ocupa um par de dias distintos. Para que cada dia receba exatamente 2 aulas, as três línguas devem ocupar os três pares de dias distintos {seg,qua}, {seg,sex}, {qua,sex}: a atribuição dos pares às línguas pode ser feita de 3! = 6 modos. Em cada dia, as duas aulas (de línguas diferentes) podem ser ordenadas nos dois horários de 2 modos: 23 = 8. Pelo MP: 6 × 8 = 48. Resposta: 48 modos.

voltar ao índice

Questão 1.42

Com relação aos números de cinco algarismos do sistema de numeração decimal, pergunta-se:

a) quantos são? b) quantos são ímpares e de algarismos distintos? c) quantos são pares e de algarismos distintos? d) quantos apresentam exatamente um algarismo igual a 3? e) quantos permanecem os mesmos quando a ordem dos seus algarismos é invertida (por exemplo, 16261)?

Ver a resolução

a) De 10000 a 99999: 9 × 104 = 90000 números.

b) O algarismo das unidades deve ser ímpar: 5 opções. O primeiro algarismo: não pode ser 0 nem igual à unidade: 8 opções. Os três algarismos centrais: 8 × 7 × 6 = 336 arrumações com os dígitos restantes. Total: 5 × 8 × 336 = 13440.

c) Caso unidade = 0: primeiro algarismo com 9 opções e centrais 8×7× 6 = 336: 9 × 336 = 3024. Caso unidade ∈ {2,4,6,8} (4 opções): primeiro algarismo com 8 opções (não pode ser 0 nem a unidade) e centrais 336: 4 × 8 × 336 = 10752. Total: 3024 + 10752 = 13776.

d) (Não se exige algarismos distintos.) Se o 3 ocupa a primeira posição, as demais quatro posições não podem conter 3: 94 = 6561. Se o 3 ocupa uma das outras 4 posições, o primeiro algarismo tem 8 opções (nem 0 nem 3) e as três posições restantes 93 opções cada conjunto: 4 × 8 × 93 = 4 × 8 × 729 = 23328. Total: 6561 + 23328 = 29889.

e) O número é um palíndromo abcba: a ≠ 0 com 9 opções, b e c livres com 10 opções cada: 9 × 10 × 10 = 900. Resposta:

a) 90000;

b) 13440;

c) 13776;

d) 29889;

e) 900.

voltar ao índice

Questão 1.43

Define-se como anagrama qualquer sequência de letras do alfabeto latino. Com as letras a, b, c, d, e, f, g, h, i, j, k, l (12 letras), quantos anagramas de 7 letras podem ser feitos se:

a) é permitida a repetição de letras? b) não é permitida a repetição de letras? c) a letra e figura no anagrama e não há repetição de letras? d) a letra e figura no anagrama e pode haver repetição de letras? e) o anagrama é um palíndromo, isto é, não se altera quando lido de trás para a frente (com repetição permitida)?

Ver a resolução

a) Cada uma das 7 posições tem 12 opções: 127 = 35831808.

b) 12 × 11 × 10 × 9 × 8 × 7 × 6 = 3991680.

c) Escolhe-se a posição da letra e: 7 modos; as demais 6 posições são preenchidas com 6 das 11 letras restantes, sem repetição: 11×10×9×8× 7 × 6 = 332640. Total: 7 × 332640 = 2328480.

d) Contagem complementar: total com repetição menos anagramas sem a letra e: 127 − 117 = 35831808 − 19487171 = 16344637.

e) Num palíndromo de 7 letras, as posições 5, 6 e 7 são espelho das posições 3, 2 e 1; ficam livres as posições 1 a 4: 124 = 20736. Resposta:

a) 127 = 35831808;

b) 3991680;

c) 2328480;

d) 16344637;

e) 20736.

voltar ao índice

Questão 1.44

Os números 14647, 10085 e 12531 possuem algo em comum: cada um deles possui cinco algarismos, começa com 1 e possui exatamente dois algarismos iguais. Quantos números deste tipo existem?

Ver a resolução

Números 1d2d3d4d5 com exatamente um par de algarismos iguais. Caso 1: o algarismo repetido é o 1. Escolhe-se a posição do segundo 1 entre as 4 restantes: 4 modos. As outras 3 posições recebem algarismos (cid:16)9(cid:17) distintos, diferentes de 1: escolhem-se 3 valores dentre 9 (= 84) e arrumam-se (3! = 6): 84 × 6 = 504. Subtotal: 4 × 504 = 2016. Caso 2: o algarismo repetido não é o 1. Escolhe-se o algarismo: 9 (cid:16)4(cid:17) modos; as duas posições que ele ocupa: = 6 modos; as duas posições restantes recebem algarismos distintos, diferentes de 1 e do repetido: 8×7 = 56 modos. Subtotal: 9 × 6 × 56 = 3024. Total: 2016 + 3024 = 5040. Resposta: 5040 números.

voltar ao índice

Questão 1.45

De quantos modos podemos organizar a tabela da 1a rodada de um campeonato de futebol com 12 clubes?

Ver a resolução

Na primeira rodada os 12 clubes formam 6 partidas. Escolhendo os pares sucessivamente: 12! 10! 8! 6! 4! 2! = 66 · 45 · 28 · 15 · 6 · 1 = 7484400. 2 2 2 2 2 2 Como a ordem em que os 6 pares foram escolhidos não importa, dividimos por 6! = 720: = 10395. Resposta: 10395 modos (se a ordem das partidas na tabela importar, 10395 × 720 = 7484400 modos).

voltar ao índice

Questão 1.46

Um baralho comum é constituído de quatro naipes (copas, espadas, ouros e paus), cada naipe com treze cartas distintas, num total de 4 × 13 = 52 cartas. Escolhem-se sucessivamente e com reposição 4 cartas.

a) De quantos modos isto pode ser feito de modo que pelo menos uma carta seja repetida? b) De quantos modos, de modo que a quarta carta seja a única repetida? c) De quantos modos, de modo que a quarta carta seja repetida, mas não seja a única repetição?

Ver a resolução

a) Complementar: total − (todas diferentes): 524 − 52 × 51 × 50 × 49 = 7311616 − 6497400 = 814216.

b) As três primeiras são todas diferentes e a quarta coincide com exatamente uma delas: escolhem-se as três primeiras (52×51×50 modos) e qual delas é repetida na quarta posição (3 modos): 3 × 52 × 51 × 50 = 397800.

c) A quarta carta repete alguma anterior, e há outra repetição entre as três primeiras. Casos, segundo os valores das 4 cartas: (cid:16)52(cid:17) Dois pares (2 + 2): escolhem-se os dois valores, modos; qual deles ocupa a quarta posição, 2 modos; a posição, entre as três primeiras, da (cid:16)52(cid:17) carta igual à quarta, 3 modos: · 2 · 3 = 7956. Trinca (3 + 1): escolhe-se o valor repetido (52), as duas posições entre (cid:16)3(cid:17) as três primeiras que coincidem com a quarta (= 3) e a carta distinta (51): 52 · 3 · 51 = 7956. Quadra: todas iguais: 52 modos. Total: 7956 + 7956 + 52 = 15964. Resposta:

a) 814216;

b) 397800;

c) 15964 modos.

voltar ao índice

Questão 1.47

Escrevem-se números de cinco dígitos (inclusive os começados por zero) em cartões. Como 0, 1 e 8 não se alteram de cabeça para baixo, e como 6 de cabeça para baixo se transforma em 9 (e vice-versa), um só cartão pode representar dois números (por exemplo, 06198 e 86190). Qual o número mínimo de cartões para representar todos os números de cinco dígitos?

Ver a resolução

Há 105 = 100000 números. Um cartão pode ser “aproveitado” de cabeça para baixo quando todos os seus dígitos pertencem a {0,1,8,6,9}: são 55 = 3125 números desse tipo. Dentre eles, alguns coincidem com a própria leitura invertida: para isso é preciso que d5,d4,d3 sejam as inversões de d1,d2,d3; escolhem-se livremente d1,d2 (5 modos cada) e d3 autoinvertível ({0,1,8}: 3 modos): 5 × 5 × 3 = 75 números. Assim, 3125 − 75 = 3050 números agrupam-se em pares representáveis por um mesmo cartão: economizam-se 3050/2 = 1525 cartões. Número mínimo: 100000 − 1525 = 98475. Resposta: 98475 cartões.

voltar ao índice

Questão 1.48 IME 1990

Ligando as cidades A e B existem duas estradas principais. Dez estradas secundárias, de mão dupla, ligam as duas estradas principais, como “degraus” entre elas. Quantos caminhos sem autointerseções existem de A até B? (Um caminho sem autointerseção é um caminho que não passa por um ponto duas ou mais vezes.)

Ver a resolução

Um caminho sem autointerseção deve avançar sempre de A para B: se voltasse, para retomar o avanço teria de reutilizar um trecho já percorrido. Assim, o caminho fica determinado por: (i) a estrada principal em que se inicia (2 modos); (ii) o subconjunto das estradas secundárias utilizadas para trocar de estrada principal (cada troca usa uma estrada secundária, e qualquer subconjunto das 10 determina um caminho válido): 210 modos. Pelo MP: 2 × 210 = 2048. Resposta: 2048 caminhos.

voltar ao índice

Questão 1.49

No plano cartesiano, um peão se move de acordo com a seguinte regra: estando no ponto (x,y) pode ir para (x+1,y+1), (x+1,y−1), (x−1,y+1) ou (x−1,y−1). Se o peão parte do ponto (0,0), quantas posições distintas ele poderá ocupar após seus n primeiros movimentos?

Ver a resolução

Examinemos primeiro os casos pequenos. Para n = 1, o peão está em um dos 4 pontos (±1,±1). Para n = 2, cada coordenada pode ter variado de −2, 0 ou +2, e verificamos que todos os 9 pontos com x,y ∈ {−2,0,2} são atingíveis. n posições possíveis total 1 (±1,±1) 4 = 22 2 x,y ∈ {−2,0,2} 9 = 32 3 x,y ∈ {−3,−1,1,3} 16 = 42 O padrão 22,32,42,... sugere (n + 1)2. Provemos: a cada movimento, tanto x quanto y variam de ±1. Logo, após n movimentos, x e y têm ambos a mesma paridade de n, com |x| ≤ n e |y| ≤ n. Reciprocamente, todo ponto (x,y) com x ≡ y ≡ n (mod 2), |x| ≤ n, |y| ≤ n é atingível: as variações de x e de y podem ser escolhidas de forma independente (os quatro movimentos realizam todas as combinações de sinais). Os valores possíveis de x são −n,−n+2,...,n−2,n: são n+1 valores; o mesmo para y. Pelo MP: (n + 1) × (n + 1) = (n + 1)2. Resposta: (n + 1)2 posições.

voltar ao índice

Questão 1.50

Quantos números de 4 algarismos têm todos os algarismos distintos?

Ver a resolução

O primeiro algarismo não pode ser 0 (9 opções); os seguintes apenas devem ser novos: 9 × 9 × 8 × 7 = 4536. Resposta: 4536 números.

voltar ao índice

Questão 1.51

No padrão Mercosul, uma placa tem 3 letras, 1 algarismo, 1 letra e 2 algarismos, nessa ordem (letras de um alfabeto de 26). Quantas placas são possíveis?

Ver a resolução

Pelo Princípio Multiplicativo: 263 × 10 × 26 × 102 = 264 × 103 = 456976000. Resposta: 456976000 placas.

voltar ao índice

Questão 1.52

Uma bandeira é formada por quatro listras, que devem ser coloridas usandose apenas as cores amarelo, branco e cinza, não devendo listras adjacentes ter a mesma cor. De quantos modos pode ser colorida a bandeira?

Ver a resolução

Primeira listra: 3 cores; cada listra seguinte: qualquer cor exceto a da anterior: 2 opções. Pelo MP: 3 × 2 × 2 × 2 = 24. Resposta: 24 modos.

voltar ao índice

Questão 1.53 EN 2007

Um tapete de oito faixas deve ser pintado com as cores azul, preta e branca. A quantidade de maneiras de se pintar este tapete de modo que duas faixas consecutivas não sejam da mesma cor é: (A) 256 (B) 384 (C) 520 (D) 6561 (E) 8574

Ver a resolução

A primeira faixa admite 3 cores; cada faixa seguinte, qualquer cor exceto a da anterior: 2 opções. Pelo MP: 3 × 27 = 3 × 128 = 384. Resposta: Alternativa (B): 384.

voltar ao índice

Questão 1.54 OBM 2009

Um número natural A de três algarismos detona um número natural B de três algarismos se cada algarismo de A é maior do que o algarismo correspondente de B. Por exemplo, 876 detona 345; porém, 651 não detona 542, pois 1 < 2. Quantos números de três algarismos detonam 314?

Ver a resolução

Centena maior que 3: {4,...,9}, 6 opções; dezena maior que 1: {2,...,9}, 8 opções; unidade maior que 4: {5,...,9}, 5 opções. Pelo MP: 6 × 8 × 5 = 240. Resposta: 240 números.

voltar ao índice

Questão 1.55 IME 1979

Um elevador com 7 pessoas parte do andar térreo de um prédio e faz 4 paradas em andares diferentes. De quantas maneiras diferentes todas as 7 pessoas podem desembarcar até a 4a parada, inclusive?

Ver a resolução

Uma “maneira de desembarcar” fica completamente descrita dizendo em qual parada desce cada uma das 7 pessoas. Decompomos, então, o evento em 7 etapas: a 1a pessoa escolhe uma das 4 paradas; a 2a pessoa também escolhe uma das 4 paradas (várias pessoas podem descer na mesma parada); e assim por diante até a 7a pessoa. As escolhas são independentes, e pelo MP: 4 × 4 × ··· × 4 = 47 = 16384. | {z } 7 fatores Note que quem “escolhe” é a pessoa (7 etapas) e o que se escolhe é a parada (4 opções): a resposta é 47, e não 74. Resposta: 16384 maneiras.

voltar ao índice

Questão 1.56

Durante uma Copa do Mundo disputada por 24 países, as tampinhas de um refrigerante traziam palpites sobre os países que se classificariam nos três primeiros lugares (por exemplo: 1o Brasil, 2o Nigéria, 3o Holanda). Se em cada tampinha os três países são distintos, quantas tampinhas diferentes poderiam existir?

Ver a resolução

A ordem importa (são posições distintas do pódio): 24 × 23 × 22 = 12144. Resposta: 12144 tampinhas.

voltar ao índice

Questão 1.57 IME 1992

Calcule quantos números naturais de 3 algarismos distintos existem no sistema de base 7.

Ver a resolução

Primeiro algarismo: 1 a 6 (6 opções); segundo: qualquer dos 7 exceto o primeiro (6); terceiro: 5. Pelo MP: 6 × 6 × 5 = 180. Resposta: 180 números.

voltar ao índice

Questão 1.58

O conjunto A possui 4 elementos e o conjunto B possui 7 elementos. Quantas são as funções f: A → B? Quantas são as funções injetoras?

Ver a resolução

Cada elemento de A escolhe livremente sua imagem: 74 = 2401 funções. Injetoras: as imagens são distintas: 7×6×5×4 = 840. Resposta: 2401 funções; 840 injetoras.

voltar ao índice

Questão 1.59

Em uma sala há 15 aparelhos distintos de ar-condicionado. Para manter o ar fresco, pelo menos um dos aparelhos deve estar ligado o tempo todo. De quantas maneiras é possível manter a sala fresca?

Ver a resolução

Cada aparelho pode estar ligado ou desligado: 215 configurações; exclui-se a configuração com todos desligados: 215 − 1 = 32767. Resposta: 32767 maneiras.

voltar ao índice

Questão 1.60 AMC — adaptada

O conjunto A possui 512 subconjuntos. Quantos elementos tem o conjunto A? E de quantas formas é possível iluminar uma sala que possui 6 lâmpadas independentes?

Ver a resolução

Um conjunto com n elementos possui 2n subconjuntos (cada elemento entra ou não entra: MP). De 2n = 512 = 29 vem n = 9. Para as lâmpadas: cada uma pode estar ligada ou desligada, 26 = 64 configurações; para a sala estar iluminada, exclui-se a configuração com todas apagadas: 64 − 1 = 63. Resposta: 9 elementos; 63 formas.

voltar ao índice

Questão 1.61 AMC — adaptada

Quantos inteiros de 1 a 9999 possuem pelo menos um algarismo igual a zero?

Ver a resolução

Contagem complementar: contamos os que não têm zero. Com 1 algarismo: 9; com 2: 92 = 81; com 3: 93 = 729; com 4: 94 = 6561. Total sem zero: 9 + 81 + 729 + 6561 = 7380. Logo, com pelo menos um zero: 9999 − 7380 = 2619. Resposta: 2619 números.

voltar ao índice

Questão 1.62 ITA 2003

O número de divisores de 17640 que, por sua vez, são divisíveis por 3 é:

Ver a resolução

Fatorando: 17640 = 23 ·32 ·5·72. Um divisor 2a3b5c7d é múltiplo de 3 quando b ≥ 1: 4 × 2 × 2 × 3 = 48. Resposta: 48 divisores.

voltar ao índice

Questão 1.63

a) De quantos modos é possível colocar uma torre negra e uma torre branca em um tabuleiro de xadrez de maneira que elas não se ataquem? b) Qual seria a resposta com duas torres brancas iguais?

Ver a resolução

a) A primeira torre ocupa qualquer das 64 casas; a segunda não pode ficar na mesma linha nem na mesma coluna: 64−15 = 49 casas. Total: 64 × 49 = 3136.

b) Torres indistinguíveis: cada posição foi contada duas vezes: 3136/2 = 1568. Resposta:

a) 3136;

b) 1568 modos.

voltar ao índice

Questão 1.64

Quantos embrulhos não vazios é possível formar com cinco livros de matemática, três de física e dois de química, sendo iguais os livros de uma mesma matéria?

Ver a resolução

Quantidades: matemática de 0 a 5 (6 opções), física de 0 a 3 (4), química de 0 a 2 (3): 6 × 4 × 3 = 72; excluindo o embrulho vazio: 72 − 1 = 71. Resposta: 71 embrulhos.

voltar ao índice

Questão 1.65

Quantas coleções não vazias de letras podem ser formadas com n letras A, n letras B, n letras C e n letras D?

Ver a resolução

Uma coleção fica determinada pelas quantidades de cada letra, de 0 a n: (n + 1)4 possibilidades, menos a coleção vazia: (n + 1)4 − 1. Resposta: (n + 1)4 − 1 coleções.

voltar ao índice

Questão 1.66 EN 2010

No sistema decimal, a quantidade de números ímpares positivos menores que 1000, com todos os algarismos distintos, é: (A) 360 (B) 365 (C) 405 (D) 454 (E) 500

Ver a resolução

Um algarismo: {1,3,5,7,9}: 5 números. Dois algarismos: unidade ímpar (5 modos); dezena não nula e diferente da unidade (8): 5 × 8 = 40. Três algarismos: unidade ímpar (5); centena não nula e ≠ unidade (8); dezena diferente das duas (8): 5 × 8 × 8 = 320. Total: 5 + 40 + 320 = 365. Resposta: Alternativa (B): 365.

voltar ao índice

Questão 1.67 AMC — adaptada

Quantos números naturais de quatro algarismos distintos não possuem dois algarismos consecutivos com a mesma paridade?

Ver a resolução

As paridades devem alternar: padrão PIPI (par, ímpar, par, ímpar) ou padrão IPIP. Pares: {0,2,4,6,8}; ímpares: {1,3,5,7,9}. PIPI: 1o algarismo par e não nulo: 4 modos; 2o ímpar: 5; 3o par ≠ 1o: 4; 4o ímpar ≠ 2o: 4. Subtotal: 4 × 5 × 4 × 4 = 320. IPIP: 5 × 5 × 4 × 4 = 400. Total: 320 + 400 = 720. Resposta: 720 números.

voltar ao índice

Questão 1.68 OBM 2007

Um número de quatro dígitos é dito peroba se possui pelo menos dois dígitos vizinhos com a mesma paridade. Quantos números perobas existem?

Ver a resolução

Contagem complementar: número total de 4 dígitos: 9000. Não perobas são os de paridades alternadas: padrão ÍMPAR-PAR- ÍMPAR-PAR: 5 × 5 × 5 × 5 = 625; padrão PAR-ÍMPAR-PAR-ÍMPAR (primeiro dígito par não nulo): 4×5×5×5 = 500. Total alternante: 1125. Perobas: 9000 − 1125 = 7875. Resposta: 7875 números.

voltar ao índice

Questão 1.69 OBM 2010

Cada uma das oito casas de um retângulo de duas linhas e quatro colunas é pintada de uma entre três cores. Uma coluna é chamada de corte se as suas duas casas são da mesma cor. De quantas maneiras é possível pintar o retângulo de modo que haja exatamente um corte?

Ver a resolução

Escolhe-se a coluna do corte: 4 modos; sua cor: 3 modos. Cada uma das outras 3 colunas deve ter casas de cores diferentes: 3 × 2 = 6 modos por coluna. Pelo MP: 4 × 3 × 63 = 4 × 3 × 216 = 2592. Resposta: 2592 maneiras.

voltar ao índice

Questão 1.70

De um baralho comum (52 cartas) sacam-se sucessivamente, e sem reposição, três cartas. Quantas são as extrações nas quais a primeira carta é de copas, a segunda é um rei e a terceira não é uma dama?

Ver a resolução

Separamos em casos conforme a primeira carta: 1a é o rei de copas (1 modo): restam 3 reis para a segunda; a terceira exclui as 4 damas dentre as 50 restantes: 46. Subtotal: 1 × 3 × 46 = 138. 1a é a dama de copas (1 modo): segunda: 4 reis; terceira: excluem-se as 3 damas restantes: 47. Subtotal: 1 × 4 × 47 = 188. 1a é outra carta de copas (11 modos): segunda: 4 reis; terceira: excluemse as 4 damas: 46. Subtotal: 11 × 4 × 46 = 2024. Total: 138 + 188 + 2024 = 2350. Resposta: 2350 extrações.

voltar ao índice

Questão 1.71

Quantos números inteiros positivos com três algarismos distintos são múltiplos de 5 e têm soma dos algarismos ímpar?

Ver a resolução

O algarismo das unidades é 0 ou 5. Unidades = 0: o número é ab0; como os algarismos são distintos e a é o algarismo inicial, temos a,b ∈ {1,...,9} com a ≠ b. A soma a+b deve ser ímpar: um dos dois é par e o outro ímpar (e nesse caso a ≠ b é automático). a ímpar (5 opções) e b par não nulo (4): 20; a par (4) e b ímpar (5): 20. Subtotal: 40. Unidades = 5: número ab5, a ≠ 0, a,b ≠ 5, a ≠ b; soma a+b+5 ímpar ⇒ a+b par: mesmos pares de paridade. Ambos ímpares (≠ 5): 4×3 = 12; ambos pares (b pode ser 0): 4 × 4 = 16. Subtotal: 28. Total: 40 + 28 = 68. Resposta: 68 números.

voltar ao índice

Questão 1.72 AFA 2016

Uma caixa contém 10 bolas: 3 amarelas numeradas de 1 a 3, 3 verdes numeradas de 1 a 3 e 4 bolas de outras cores, todas distintas e sem numeração. De quantas formas distintas é possível enfileirar essas 10 bolas de modo que bolas de mesmo número fiquem juntas?

Ver a resolução

Os pares (amarela i, verde i), i = 1,2,3, formam blocos; cada bloco admite 2 ordens internas. Enfileiram-se 7 objetos (3 blocos + 4 bolas avulsas): 7! modos. Total: 7! × 23 = 5040 × 8 = 40320. Resposta: 40320 formas.

voltar ao índice

Questão 1.73 OBM 1998

De quantos modos se podem colocar numa tabela de duas linhas e três colunas duas letras A, duas letras B e duas letras C, uma em cada casa, de modo que não haja duas letras iguais na mesma coluna?

Ver a resolução

Cada coluna recebe um par de letras distintas; como cada letra aparece duas vezes, os três pares devem ser {A,B}, {A,C} e {B,C}, atribuídos às colunas de 3! = 6 modos. Em cada coluna, as duas letras ordenam-se de 2 modos: 23 = 8. Total: 6 × 8 = 48. Resposta: 48 modos. (cid:16)5(cid:17)

voltar ao índice

Questão 1.74 HMMT — adaptada

De quantos modos podemos escolher, num tabuleiro 5 × 5, três casas de modo que não haja duas casas escolhidas na mesma linha nem na mesma coluna?

Ver a resolução

Escolhem-se as 3 linhas (= 10 modos) e as 3 colunas (cid:16)5(cid:17) (= 10 modos) que conterão as casas; em seguida, associa-se cada linha escolhida a uma coluna escolhida (uma bijeção): 3! = 6 modos. Pelo MP: 10 × 10 × 6 = 600. Resposta: 600 modos.

voltar ao índice

Questão 1.75 OBM 2012

Um painel luminoso é formado por 10 círculos grandes; dentro de cada círculo há quatro lâmpadas: uma amarela, uma verde, uma vermelha e uma azul. De quantos modos podemos acender o painel de modo que pelo menos uma lâmpada de cada cor fique acesa? (Cada círculo pode ter de zero a quatro lâmpadas acesas.)

Ver a resolução

Para cada cor há 10 lâmpadas (uma por círculo), e as escolhas das quatro cores são independentes. Por cor, qualquer subconjunto não vazio das suas 10 lâmpadas pode estar aceso: 210 − 1 modos. Total: (cid:16) (cid:17)4 210 − 1. Resposta: (210 − 1)4 modos.

voltar ao índice

Questão 1.76 OBMEP 2019

Um tabuleiro preenchido com as letras A, B, C e D é bacana se essas quatro letras aparecem em qualquer quadriculado 2 × 2 do tabuleiro. Quantos tabuleiros bacanas 2 × 8 existem?

Ver a resolução

Preenchemos o tabuleiro coluna a coluna, da esquerda para a direita. As duas primeiras colunas formam o primeiro quadrado 2×2, que deve conter as quatro letras: são 4! = 24 preenchimentos possíveis. Agora observe a etapa de acréscimo de uma nova coluna: junto com a coluna anterior ela forma um novo quadrado 2×2, que também deve conter as quatro letras. Como a coluna anterior já usa duas letras distintas, a nova coluna deve conter exatamente as duas letras que faltam — e só resta escolher em qual ordem (em cima/embaixo): 2 maneiras. Essa escolha, automaticamente, também garante a condição, e nada mais é exigido. Das 8 colunas, as duas primeiras usam 4! = 24 modos e cada uma das 6 colunas seguintes dá 2 opções. Pelo MP: 4! × 26 = 24 × 64 = 1536. Resposta: 1536 tabuleiros.

voltar ao índice

Questão 1.77 OBMEP 2018

Um número inteiro positivo é chamado de interessante quando termina com um algarismo que é igual ao produto de seus demais algarismos. Por exemplo, 326 e 1020 são interessantes, pois 3 × 2 = 6 e 1 × 0 × 2 × 0 = 0.

a) Quantos números interessantes de quatro algarismos terminam com o algarismo 6? b) Quantos números interessantes de cinco algarismos terminam com o algarismo 0?

Ver a resolução

a) Seja abc6 interessante: a · b · c = 6. Pelo menos um dos algarismos é 1 (pois 2 · 2 · 2 = 8 > 6). Se apenas um é 1, os outros são 2 e 3: permutando, 3! = 6 possibilidades. Se dois são 1, o outro é 6: basta escolher sua posição, 3 possibilidades. Total: 6 + 3 = 9.

b) Seja abcd0 interessante: basta que a·b·c·d = 0, isto é, que algum de b,c,d seja 0 (note que a ≠ 0). Contamos o complementar: os números de cinco algarismos terminados em 0 são 9×103 = 9000; os não interessantes são os com b,c,d ≠ 0: 9 × 9 × 9 × 9 = 6561. Logo, 9000 − 6561 = 2439. Resposta:

a) 9;

b) 2439.

voltar ao índice

Questão 1.78 OBM 2013

Determine o número de quádruplas ordenadas de inteiros positivos (x,y,z,w) que satisfazem x · y · z · w = 2013.

Ver a resolução

Fatorando, 2013 = 3×11×61, produto de três primos distintos. Em uma quádrupla (x,y,z,w) com x · y · z · w = 2013, cada uma das entradas é um divisor de 2013 e cada fator primo deve aparecer, com expoente 1, em exatamente uma das quatro entradas (se aparecesse em duas, o produto teria aquele primo ao quadrado; se em nenhuma, faltaria o primo). Assim, construir a quádrupla equivale a decidir o destino de cada primo: o fator 3 vai para x, y, z ou w (4 opções); o fator 11, idem (4 opções); o fator 61, idem (4 opções). As três decisões são independentes e determinam a quádrupla (as entradas que não recebem primo algum valem 1). Pelo MP: 4 × 4 × 4 = 43 = 64. Por exemplo, a escolha “3 → y, 11 → y, 61 → w” produz (1,33,1,61). Resposta: 64 quádruplas.

voltar ao índice

Questão 1.79 USC High School Math Contest 1993 — Carolina do Sul

Denotando por ⌊x⌋ o maior inteiro menor do que ou igual a x (por exemplo, ⌊2,769⌋ = 2 e ⌊π⌋ = 3), calcule ⌊log22⌋ + ⌊log23⌋ + ⌊log24⌋ + ··· + ⌊log299⌋ + ⌊log2100⌋.

Ver a resolução

⌊log2n⌋ = m exatamente quando 2m ≤ n < 2m+1. Contamos por blocos: n = 2,3 ⇒ 2 termos iguais a 1; n = 4,...,7 ⇒ 4 termos iguais a 2; n = 8,...,15 ⇒ 8 termos iguais a 3; n = 16,...,31 ⇒ 16 termos iguais a 4; n = 32,...,63 ⇒ 32 termos iguais a 5; n = 64,...,100 ⇒ 37 termos iguais a 6. Logo a soma vale 2(1)+4(2)+8(3)+16(4)+32(5)+37(6) = 2+8+24+ 64 + 160 + 222 = 480. Resposta: 480.

voltar ao índice

Questão 1.80 OMERJ 2023

O país da OMERJlândia é composto por duas ilhas A e B. É uma tradição que os habitantes da ilha A enviem presentes para os habitantes da ilha B no dia da OMERJ. Pela tradição, cada pessoa da ilha B recebe no máximo um presente e cada pessoa da ilha A envia no máximo um presente. Infelizmente, nem todos os habitantes da ilha A gostam de enviar presentes. Em 2023, 2/3 dos habitantes da ilha A enviaram presentes, enquanto 3/5 dos habitantes da ilha B receberam presentes. Qual fração da população total da OMERJlândia recebeu presentes?

Ver a resolução

Sejam a e b as populações das ilhas A e B. Cada presente sai de exatamente uma pessoa de A e chega a exatamente uma pessoa de B; contando os presentes dos dois lados, 2 3 10 a = b =⇒ b = a. 3 5 9 A população total é a+b = 199a, e receberam presentes 35b = 23a pessoas. A fração pedida é 32a 2 9 6 = · =. 199a 3 19 19 (Exemplo concreto: a = 9 e b = 10 — 6 enviam, 6 recebem, população 19.) Resposta: 619 da população total.

voltar ao índice

Questão 1.81

Encontre o número de triplas ordenadas de conjuntos (A,B,C) tais que A ∪ B ∪ C = {1,2,...,2013} e A ∩ B ∩ C = ∅.

Ver a resolução

Examinemos primeiro o caso pequeno em que o universo é {1}: o elemento 1 deve pertencer a pelo menos um dos conjuntos A,B,C (para que a união seja {1}), mas não aos três simultaneamente (para que a interseção seja vazia). Das 23 = 8 combinações de pertinência — indicadas por um vetor (∈ A?,∈ B?,∈ C?) — excluem-se (N,N,N) e (S,S,S): restam 6 triplas. O argumento se repete para cada elemento: escolher (A,B,C) equivale a escolher, para cada i ∈ {1,...,2013}, uma das 23 = 8 combinações de pertinência; a condição A ∪ B ∪ C = {1,...,2013} proíbe “a nenhum” e a condição A ∩ B ∩ C = ∅ proíbe “a todos”. Cada elemento tem, portanto, 8−2 = 6 opções, e as escolhas dos 2013 elementos são independentes. Pelo MP: 62013. Resposta: 62013 triplas.

voltar ao índice

Questão 1.82

Determine o número de funções f: {1,2,...,1999} → {2000,2001,2002,2003} tais que f(1) + f(2) + ··· + f(1999) é ímpar.

Ver a resolução

No contradomínio há dois valores pares (2000, 2002) e dois ímpares (2001, 2003). A paridade da soma depende só da quantidade de argumentos com imagem ímpar. Fixadas as imagens de 1,...,1998 (livres: 41998 modos), a paridade da soma é decidida pela imagem de 1999: exatamente 2 das 4 opções tornam a soma ímpar. Total: 41998 × 2 = 23997. Resposta: 23997 funções.

voltar ao índice

Questão 1.83

Determine o número de funções f: {1,2,...,1999} → {1,2,3,4} satisfazendo a condição de que f(1) + f(2) + ··· + f(1999) seja ímpar.

Ver a resolução

Escolhemos livremente f(1),...,f(1998): são 41998 maneiras. Se a soma parcial é par, f(1999) ∈ {1,3}; se é ímpar, f(1999) ∈ {2,4}. Em qualquer caso há exatamente 2 escolhas finais: 41998 × 2 = 23997. Resposta: 23997 funções. j99999k j9999k

voltar ao índice

Questão 1.84 Duke Math Meet — adaptada

Quantos números naturais de cinco dígitos são múltiplos de 3 e têm 6 como um de seus dígitos?

Ver a resolução

Múltiplos de 3 com cinco dígitos: − = 3 3 33333 − 3333 = 30000. Retiramos os múltiplos de 3 sem o dígito 6. Números de cinco dígitos sem o 6: primeiro dígito em {1,...,9} \ {6} (8 opções), demais em {0,...,9} \ {6} (9 opções): 8 × 94 = 52488. Como os restos módulo 3 se distribuem igualmente nesse conjunto (os 9 dígitos disponíveis para cada posição livre cobrem todos os restos igualmente), exatamente 52488/3 = 17496 deles são múltiplos de 3. Logo, a resposta é 30000 − 17496 = 12504. Resposta: 12504 números.

voltar ao índice

Questão 1.85

Encontre a quantidade de números de dois dígitos ab que são divisíveis por ambos os seus dígitos.

Ver a resolução

Queremos a,b ≥ 1 com a | 10a + b e b | 10a + b, ou seja, a | b e b | 10a. Se b é ímpar e b ≠ 5: b | a, logo a = b — os números 11,33,77,99 (4 casos). Se b = 5: a | 5, logo a ∈ {1,5} — os números 15,55 (2 casos). Se b é par, b = 2b′ com b′ ≤ 4: obtém-se b = a ou b = 2a — os números 22,44,66,88,12,24,36,48 (8 casos). Total: 4 + 2 + 8 = 14. Resposta: 14 números.

voltar ao índice

Questão 1.86

Quantos são os números de cinco dígitos que são múltiplos de 3 e possuem 6 como um de seus dígitos?

Ver a resolução

Há 30000 múltiplos de 3 com cinco dígitos (de 10002 a 99999). Contamos os que não têm dígito 6: o primeiro dígito tem 8 opções (nem 0 nem 6), o segundo, terceiro e quarto têm 9 opções cada; escolhidos esses quatro, o último dígito deve completar um múltiplo de 3 e ser diferente de 6 — em qualquer caso restam exatamente 3 opções (por exemplo, resto 0: {0,3,9}). São 8 × 93 × 3 = 17496. Logo, a resposta é 30000 − 17496 = 12504. Resposta: 12504 números.

voltar ao índice

Questão 1.87 OBM 2000

Quantos números de três algarismos possuem um algarismo que é a média aritmética dos outros dois?

Ver a resolução

Um algarismo é média dos outros dois exatamente quando os três algarismos podem ser ordenados em progressão aritmética {b − d, b, b + d}. Caso d = 0: algarismos iguais: 111,222,...,999: 9 números. Caso d ≥ 1: para cada d, o termo central b percorre d ≤ b ≤ 9−d: são 10−2d valores. Cada conjunto {b−d,b,b+d} tem 3 algarismos distintos e gera 3! = 6 arranjos; quando b = d (e somente então) o conjunto contém o 0, e devemos descontar os 2 arranjos que começam por zero. Organizando os casos numa tabela: d valores de b conjuntos números 1 1,...,8 8 8 · 6 − 2 = 46 2 2,...,7 6 6 · 6 − 2 = 34 3 3,...,6 4 4 · 6 − 2 = 22 4 4,5 2 2 · 6 − 2 = 10 Somando: 46 + 34 + 22 + 10 = 112. Total: 112 + 9 = 121. Resposta: 121 números.

voltar ao índice

Questão 1.88 AIME 1992

Para quantos pares de inteiros consecutivos no conjunto {1000,1001,...,2000} a operação de “vai um” não acontece quando somamos os dois números?

Ver a resolução

Examinemos primeiro quando ocorre “vai um”: ao somar dois números coluna a coluna, a coluna dos dígitos d e d′ gera transporte exatamente quando d + d′ ≥ 10. Somamos n = 1abc com n + 1. Caso c < 9: então n + 1 = 1ab(c+1), e as colunas somam c + (c + 1), b + b, a + a e 1 + 1. Não há vai um se e só se 2c + 1 ≤ 9, 2b ≤ 9 e 2a ≤ 9, isto é, a,b,c ∈ {0,1,2,3,4}: 53 = 125 casos. Caso c = 9 e b < 9: então n+1 = 1a(b+1)0, e as colunas somam 9+0, b+(b+1), a+a: sem vai um se e só se a,b ∈ {0,...,4}: 5×5 = 25 casos. Caso c = b = 9 e a < 9: então n + 1 = 1(a+1)00, com colunas 9 + 0, 9 + 0, a + (a + 1): sem vai um se e só se a ∈ {0,...,4}: 5 casos. Caso a = b = c = 9: o par é 1999 + 2000, com colunas 9 + 0, 9 + 0, 9 + 0, 1 + 2: não gera vai um — mais 1 caso. Total: 125 + 25 + 5 + 1 = 156. Resposta: 156 pares.

voltar ao índice

Questão 1.89 Duke Math Meet 2020 — Carolina do Norte

Uma “palavra duke” é uma palavra de 10 letras, formada apenas com letras do conjunto {D,U,K,E}, que contém o bloco consecutivo DUKE. Quantas palavras duke existem?

Ver a resolução

O bloco DUKE pode começar nas posições 1,2,...,7. Para cada posição, as 6 letras restantes são livres: 7×46 = 28672 contagens. Porém, palavras com duas ocorrências (disjuntas) do bloco foram contadas duas vezes. Duas ocorrências começando em i < j exigem j ≥ i+4: os pares possíveis são (1,5),(1,6),(1,7),(2,6),(2,7),(3,7) — 6 pares — e em cada caso restam 2 letras livres: 6 × 42 = 96. (Três ocorrências são impossíveis em 10 letras.) Por inclusão–exclusão: 7 · 46 − 6 · 42 = 28672 − 96 = 28576. Resposta: 28576 palavras.

voltar ao índice

Questão 1.90 OBM 2012

Uma formiga deve caminhar ao longo das linhas de um quadriculado 5×5, do vértice A (canto inferior esquerdo) até o vértice B (canto superior direito), deslocando-se apenas um quadradinho para a direita ou para cima. Sabendo que a formiga não pode passar pelos vértices do quadradinho central (pintado de preto), determine o número de caminhos diferentes que a formiga pode percorrer.

Ver a resolução

Coloquemos A = (0,0) e B = (5,5); o quadradinho central tem vértices (2,2), (2,3), (3,2) e (3,3), todos proibidos. B A A antidiagonal x + y = 5 (tracejada) e seus 6 pontos: os 2 do quadrado preto são proibidos; os 4 pontos permitidos estão destacados. Como cada passo aumenta x + y em 1, todo caminho de A a B passa por exatamente um ponto da antidiagonal x+y = 5, cujos pontos são (0,5), (1,4), (2,3), (3,2), (4,1) e (5,0). Os pontos (2,3) e (3,2) são vértices do quadrado preto: proibidos. Isso separa os caminhos em 4 casos disjuntos (AP), e em cada caso multiplicamos os trechos (MP): (cid:16)5(cid:17) Por (1,4): de A a (1,4) há = 5 caminhos, e nenhum deles encosta (cid:16)5(cid:17) no quadrado preto (pois x ≤ 1 ao longo do trecho); de (1,4) a B há = 5 caminhos, também seguros (pois y ≥ 4). Subtotal: 5 × 5 = 25. Por (4,1): simétrico, 5 × 5 = 25. Por (0,5): só o caminho que sobe tudo e depois vai para a direita: 1 × 1 = 1. Por (5,0): simétrico, 1. (cid:16)10(cid:17) Total: 25+25+1+1 = 52. (Conferência: sem restrição seriam = 252 caminhos.) Resposta: 52 caminhos.

voltar ao índice

Questão 1.91 OMERJ 2025 (Nível 3, Questão 6

Para cada número inteiro n > 1 queremos colorir os números 2,3,...,n com k cores de modo que se a,b,c ∈ {2,...,n} e a · b = c, então a, b e c não podem ser os três da mesma cor. Denote por an o menor k para o qual isso é possível. (a) Calcule a45. (b) Calcule a2025. Nota: é permitido a = b: se a2 ≤ n, então a e a2 não podem ter ambos a mesma cor.

Ver a resolução

A estratégia é (i) estabelecer uma cota inferior para an (mostrar que k cores não bastam), e (ii) exibir uma coloração com k cores (mostrar que k cores bastam). Quando (i) e (ii) coincidem, encontramos o mínimo. Cota inferior: an ≥ 3 para n ≥ 32. Lema. Se n ≥ 32, não conseguimos colorir {2,...,n} com apenas 2 cores respeitando a regra. Prova. Suponha que exista uma 2-coloração válida. Consideramos os cinco números 2,4,8,16,32, todos presentes em {2,...,n} quando n ≥ 32. Digamos que 2 tem cor X. Produto Raciocínio Conclusão 2 · 2 = 4 Se 4 fosse X, a 4 tem cor Y tríade (2,2,4) seria monocromática 4 · 4 = 16 Se 16 fosse Y, a 16 tem cor X tríade (4,4,16) seria monocromática 2 · 8 = 16 Como 2 e 16 são X, a 8 tem cor Y tríade (2,8,16) não pode ter 8 em X 4 · 8 = 32 Como 4 e 8 são Y, a 32 tem cor X tríade (4,8,32) não pode ter 32 em Y 2 · 16 = 32 Mas agora 2,16,32 têm Contradição! todos cor X Logo, 2 cores não bastam quando n ≥ 32. Assim a45 ≥ 3 e a2025 ≥ 3. ■ Item (a): a45 = 3, colorindo por intervalos. Exibimos uma coloração com 3 cores: pinte cada número x ∈ {2,...,45} conforme o intervalo: cor 1: [2,3] cor 2: [4,15] cor 3: [16,45]. Verificamos que nenhuma tríade (a,b,ab) com a · b = ab ≤ 45 fica monocromática: • Se a,b ∈ [2,3]: então ab ≥ 2 · 2 = 4 > 3, logo ab não está em [2,3]. • Se a,b ∈ [4,15]: então ab ≥ 4 · 4 = 16 > 15, logo ab não está em [4,15]. • Se a,b ∈ [16,45]: então ab ≥ 16·16 = 256 > 45, logo ab não pertence a {2,...,45}. Em todos os casos, (a,b,ab) usa cores diferentes (ou ab nem existe no intervalo). Portanto, 3 cores bastam. Combinando com a cota inferior, a45 = 3. Item (b): a2025 = 3, colorindo por blocos de potências de 2. Para n = 2025, intervalos simples como em (a) não funcionam: começando em [2,3], [4,15], chegamos a no máximo [16,255], que não cobre 2025. A ideia é reutilizar cores em blocos não consecutivos. Para cada x ∈ [2,2025], defina e(x) = ⌊log2x⌋, o expoente do “bloco diádico” de x. Assim 2e(x) ≤ x < 2e(x)+1. Por exemplo: x [2,3] [4,7] [8,15] [16,31] [32,63] ··· [1024,2047] e(x) 1 2 3 4 5 ··· 10 Propriedade-chave: se e(a) = e e e(b) = f, então e(ab) ∈ {e+f,e+f+1} (pois 2e+f ≤ ab < 2e+f+2). Particionamos os expoentes {1,2,...,10} em três classes: A = {1,4,10}, B = {2,3,9}, C = {5,6,7,8}. Colorimos x com a cor da classe de e(x). A coloração é: cor 1: [2,4) ∪ [16,32) ∪ [1024,2025], cor 2: [4,16) ∪ [512,1024), cor 3: [32,512). Verificação: para que uma tríade (a,b,ab) fosse monocromática, precisaríamos que todos três pertençam à mesma classe de expoentes. Mas isso exigiria e,f,e + f ∈ mesma classe (ou ambos ∈ mesma classe). Conferindo manualmente: nenhuma classe tem essa propriedade (por exemplo, 1+4 = 5 ∈/ A, 2+3 = 5 ∈/ B, etc.). Logo não existe tríade monocromática, e 3 cores bastam até n = 2047. Combinando com a cota inferior, a2025 = 3. Resposta: (a) a45 = 3; (b) a2025 = 3.

voltar ao índice

Questão 1.92

Quantos são os pares (a,b) de inteiros positivos com mmc(a,b) = 1800? E quantos são se a ordem do par não importar?

Ver a resolução

Como 1800 = 23 · 32 · 52, escreva a = 2x13y15z1 e b = 2x23y25z2. O mínimo múltiplo comum toma, em cada primo, o maior dos dois expoentes, de modo que a condição mmc(a,b) = 1800 se separa em três condições independentes: max(x1,x2) = 3, max(y1,y2) = 2, max(z1,z2) = 2. Conte os pares que realizam max(u,v) = e com 0 ≤ u,v ≤ e: ou u = e e v é livre (e + 1 modos), ou v = e e u < e (e modos), num total de 2e + 1. Pelo princípio multiplicativo, (2 · 3 + 1)(2 · 2 + 1)(2 · 2 + 1) = 7 · 5 · 5 = 175. Para a ordem não importar, note que a = b obriga a = b = 1800, um único par. Os outros 174 pares ordenados vêm aos pares, (a,b) e (b,a), logo dão 87 conjuntos, e o total é 87 + 1 = 88. Resposta: 175 pares ordenados; 88 se a ordem não importa.

voltar ao índice

Questão 1.93

Três conjuntos A, B e C contidos num universo U repartem U em até oito regiões — uma para cada maneira de pertencer ou não a cada um dos três. Quantas dessas regiões podem ser não vazias em cada caso? (a) A ⊆ B ⊆ C; (b) A, B e C dois a dois disjuntos; (c) A ∩ B ∩ C = ∅ e A ∪ B ∪ C = U; (d) no caso (c), com U = {1,2,...,n}, de quantos modos podem ser escolhidos A, B e C?

Ver a resolução

Identifique cada região com uma terna (a,b,c) de zeros e uns, onde o primeiro dígito diz se os elementos daquela região pertencem a A, o segundo se pertencem a B e o terceiro se pertencem a C. São 23 = 8 ternas, e cada condição do enunciado proíbe algumas delas. (a) Pertencer a A obriga a pertencer a B, e pertencer a B obriga a pertencer a C: sobram as ternas com a ≤ b ≤ c, que são 000, 001, 011 e 111. São 4 regiões — as quatro “camadas” da cadeia. (b) Nenhum elemento está em dois dos conjuntos ao mesmo tempo: sobram as ternas com no máximo um dígito 1, isto é, 000, 100, 010 e 001. São 4 regiões. (c) A interseção vazia proíbe 111 e a união total proíbe 000; nenhuma outra terna é atingida. Sobram 6 regiões. (d) Cada um dos n elementos de U escolhe livremente uma das 6 regiões permitidas, e escolhas diferentes dão ternas (A,B,C) diferentes. Pelo princípio multiplicativo, 6n. Resposta: (a) 4; (b) 4; (c) 6; (d) 6n.

voltar ao índice

Questão 1.94

Os ciclistas têm aversão ao número zero (porque é oval) e ao número oito (porque assim ficam as rodas após os acidentes). Quantos sócios podem se inscrever num clube de ciclistas se cada um deve possuir uma identificação de três dígitos, sem usar o dígito zero nem o dígito oito?

Ver a resolução

Os dígitos permitidos são 1,2,3,4,5,6,7,9: são 8. Cada uma das três posições recebe qualquer um deles, com repetição permitida, logo 83 = 512. Resposta: 512 sócios.

voltar ao índice

Questão 1.95

Quantos são os números de até 4 dígitos que não possuem o zero?

Ver a resolução

Separe pela quantidade de dígitos. Com k dígitos, cada posição tem 9 opções (de 1 a 9), o que dá 9k números. Logo 9 + 92 + 93 + 94 = 9 + 81 + 729 + 6561 = 7380. Resposta: 7380 números.

voltar ao índice

Questão 1.96

De quantas maneiras podemos escrever 360 como produto de três inteiros positivos, se a ordem dos fatores importa? E se não importar?

Ver a resolução

Escrever 360 = abc é distribuir os fatores primos entre as três casas. Como 360 = 23 · 32 · 5, cada fator é da forma a = 2x13y15z1, e o que precisamos é repartir os três fatores 2, os dois fatores 3 e o único fator 5 em três parcelas ordenadas: x1 + x2 + x3 = 3, y1 + y2 + y3 = 2, z1 + z2 + z3 = 1, com os expoentes inteiros não negativos. Cada equação é uma distribuição independente das outras, e o princípio multiplicativo junta as três: 3 + 2! 2 + 2! 1 + 2! · · = 10 · 6 · 3 = 180. 2 2 2 Para a ordem não importar, note que nenhuma tripla tem os três fatores iguais, pois 360 não é cubo perfeito. Das 180 triplas ordenadas, as que têm exatamente dois fatores iguais vêm de 360 = a · a · c, isto é, a2 | 360 com a > 1 ou a = 1: os valores a ∈ {1,2,3,6} dão c = 360,90,40,10, quatro triplas não ordenadas, cada uma contada 3 vezes na lista ordenada. Sobram 180 − 12 = 168 triplas ordenadas com os três fatores distintos, contadas 3! = 6 vezes cada, o que dá 168/6 = 28. No total, 28 + 4 = 32. Resposta: 180 maneiras com a ordem importando, 32 sem.

voltar ao índice

Questão 1.97 IME 2026

Uma relação binária R sobre um conjunto S é dita antissimétrica se e somente se, para quaisquer x e y elementos de S, sempre que (x,y) ∈ R e (y,x) ∈ R, então x = y. Determine o número de relações binárias antissimétricas existentes sobre um conjunto com n elementos.

Ver a resolução

Uma relação é um subconjunto de S ×S, e a condição trata cada par não ordenado separadamente. Para x = y: o par (x,x) nunca viola a condição, logo cada um dos n pares da diagonal pode entrar ou não: 2n possibilidades. Para x ≠ y: o par não ordenado {x,y} admite três situações — nenhum dos pares ordenados, só (x,y), só (y,x) —, pois ter os dois violaria a (cid:16)n(cid:17) antissimetria. São pares não ordenados, cada um com 3 possibilidades. Pelo princípio multiplicativo, 2n · 3(n2) = 2n · 3n2−n. (Para n = 2: 4·3 = 12, que se confere listando as 12 relações antissimétricas entre as 16 relações possíveis.) Resposta: 2n · 3 n2−n2.

voltar ao índice

Questão 1.98 IME 2020

Os modelos de placas de identificação de automóveis adotados no Brasil estão sendo atualizados: o modelo antigo ABC1234 (três letras seguidas de quatro algarismos) está sendo substituído pelo modelo novo ABC1D23 (três letras, um algarismo, uma letra e dois algarismos). Placas de modelos distintos podem apresentar sequências de caracteres alfanuméricos iguais; por exemplo, a sequência “20” aparece em IME2020 e em BRA5P20, e a sequência “A12” aparece em BRA1234 e em IME4A12. Considere a placa do modelo antigo IME2019 e seja P o conjunto das placas do modelo novo que podem ser formadas com alguma sequência de três caracteres em comum com a placa IME2019. Determine o número de elementos de P. Considere o alfabeto com 26 letras.

Ver a resolução

As sequências de três caracteres consecutivos de IME2019 são IME, ME2, E20, 201, 019. No modelo novo, o padrão de posições é LLLDLDD (L = letra, D = algarismo), de modo que as janelas de três caracteres consecutivos têm os padrões LLL, LLD, LDL, DLD, LDD. |{z} | {z } | {z } | {z } | {z } 1–3 2–4 3–5 4–6 5–7 Logo 201 e 019 são impossíveis (não há três algarismos consecutivos), e cada uma das outras três cabe em uma única janela: A: IME em 1–3, B: ME2 em 2–4, C: E20 em 5–7. Contando os casos livres, |A| = 10 · 26 · 102 = 26000, |B| = 26 · 26 · 102 = 67600, |C| = 263 · 10 = 175760, |A ∩ B| = 26 · 102 = 2600, |A ∩ C| = 10, |B ∩ C| = 26, e |A ∩ B ∩ C| = 1. Pelo princípio da inclusão–exclusão, |P| = 26000 + 67600 + 175760 − 2600 − 10 − 26 + 1 = 266725. Resposta: 266725 placas.

voltar ao índice

Questão 1.99 IME 2005

O sistema de segurança de uma casa utiliza um teclado numérico conforme a figura. Um ladrão observa de longe e percebe que a senha utilizada possui 4 dígitos, que o primeiro e o último dígitos encontram-se numa mesma linha e que o segundo e o terceiro encontram-se na linha imediatamente superior. Calcule o número de senhas que deverão ser experimentadas pelo ladrão para que com certeza ele consiga entrar na casa. 1 2 3 4 5 6 7 8 9

Ver a resolução

As linhas do teclado são {1,2,3}, {4,5,6}, {7,8,9} e {0}. Se o primeiro e o último dígitos estão numa linha, o segundo e o terceiro estão na linha de cima, o que deixa três casos: • primeiro e último em {4,5,6}, segundo e terceiro em {1,2,3}: 3·3·3·3 = 81 senhas; • primeiro e último em {7,8,9}, segundo e terceiro em {4,5,6}: também 81 senhas; • primeiro e último iguais a 0, segundo e terceiro em {7,8,9}: 1·3·3·1 = 9 senhas. No total, 81+81+9 = 171. (Os dígitos podem repetir-se: nada no enunciado os obriga a serem distintos.) Resposta: 171 senhas.

voltar ao índice

Questão 1.100 IME 1996

É dado um tabuleiro quadrado 4×4. Deseja-se atingir o quadrado inferior direito a partir do quadrado superior esquerdo. Os movimentos permitidos são: andar um quadrado para a direita, para baixo ou na diagonal (para baixo e para a direita). De quantas maneiras isto é possível?

Ver a resolução

Seja N(i,j) o número de caminhos até a casa da linha i e coluna j, contadas a partir da casa inicial. Vale N(i,j) = N(i − 1,j) + N(i,j − 1) + N(i − 1,j − 1), pois a casa (i,j) é alcançada vindo de cima, da esquerda ou da diagonal, e N(i,0) = N(0,j) = 1. Preenchendo o tabuleiro: 1 1 1 11 3 5 7 1 5 13 251 7 25 63 A casa inferior direita recebe 63. (Esses são os números de Delannoy: 1,3,13,63,...) Resposta: 63 maneiras.

voltar ao índice

Questão 1.101 IME 1984

Determine a soma de todos os números inteiros que são obtidos permutando-se, sem repetição, os algarismos 1, 2, 3, 4 e 5.

Ver a resolução

São 5! = 120 números. Por simetria, cada algarismo ocupa cada uma das cinco posições em 4! = 24 dos números. Logo, em cada posição, a soma dos algarismos que ali aparecem é 24(1 + 2 + 3 + 4 + 5) = 24 · 15 = 360. Somando as contribuições das cinco posições, 360(104 + 103 + 102 + 10 + 1) = 360 · 11111 = 3999960. Resposta: 3999960.

voltar ao índice

Questão 1.102 IME 1980

Um barco tem 8 lugares, numerados como no diagrama, e dispõe-se de 8 remadores (A a H) com as seguintes restrições: os remadores A e B só podem sentar no lado ímpar; o remador C só pode sentar no lado par; os remadores D, E, F, G e H podem ocupar quaisquer posições. Quantas configurações podem ser obtidas com o barco totalmente guarnecido?

Figura da questão 1.102
Ver a resolução

O lado ímpar tem os lugares 1,3,5,7 e o lado par, os lugares 2,4,6,8 — quatro de cada. Sente primeiro os remadores com restrição. Para A e B no lado ímpar há 4·3 = 12 modos; para C no lado par há 4 modos. Restam 5 remadores para os 5 lugares ainda vazios, em 5! = 120 ordens. Pelo princípio multiplicativo, 12 · 4 · 120 = 5760. Resposta: 5760 configurações.

voltar ao índice

Questão 1.103 ITA 2021

Um relógio digital mostra o horário no formato H:M:S, onde H é um inteiro entre 1 e 12 representando as horas, M é um inteiro representando os minutos e S é um inteiro representando os segundos, ambos entre 0 e 59. Quantas vezes em um dia (H,M,S) são, nessa ordem, os três primeiros termos de uma progressão aritmética de razão estritamente positiva?

Ver a resolução

A condição é M −H = S −M = r com r > 0, isto é, M = H + r e S = H + 2r, com 1 ≤ H ≤ 12 e M,S ≤ 59. Fixado H, a restrição que pesa é S = H + 2r ≤ 59, ou seja r ≤ 59−H; como M = H + r ≤ 59 é consequência disso, o número de valores de r é j59−H k. Somando de H = 1 a H = 12: 29 + 28 + 28 + 27 + 27 + 26 + 26 + 25 + 25 + 24 + 24 + 23 = 312. Como o relógio é de 12 horas, cada leitura ocorre duas vezes por dia: 2 · 312 = 624. Resposta: 624 vezes.

voltar ao índice

Questão 1.104 IME 2027

Considere os conjuntos X = {x1,x2,x3,x4,x5} e Y = {1,2,3,4,5,6,7,8}. Quantas funções injetivas f: X → Y existem tais que, para dois elementos previamente fixados xi e xj ∈ X, |f(xi) − f(xj)| ≠ 1? (A) 4800 (B) 5040 (C) 5880 (D) 6480 (E) 6720 1 3 5 72 4 6 8

Ver a resolução

Contar o complementar é mais curto: em vez das funções que evitam valores vizinhos, contamos as que colocam f(xi) e f(xj) em valores consecutivos. 1. Sem restrição, uma função injetiva de X em Y é uma escolha ordenada de 5 valores distintos entre 8: 8 × 7 × 6 × 5 × 4 = 6720. 2. Agora as proibidas, aquelas com |f(xi) − f(xj)| = 1. O par ordenado (cid:16) (cid:17) f(xi),f(xj) tem de ser (t,t + 1) ou (t + 1,t) com 1 ≤ t ≤ 7, o que dá 2 × 7 = 14 possibilidades. 3. Fixados esses dois valores, sobram 6 valores em Y para os outros três elementos de X, injetivamente: 6 × 5 × 4 = 120. 4. Logo há 14 × 120 = 1680 funções proibidas, e 6720 − 1680 = 5040. Resposta: 5040 funções — alternativa (B).

voltar ao índice

Questão 1.105

A figura mostra um mapa com cinco regiões: a região central C e as regiões R1, R2, R3 e R4 ao redor dela, cada uma fazendo fronteira com a central e com as duas vizinhas. Dispõe-se de 4 cores. De quantos modos esse mapa pode ser pintado de maneira que duas regiões com fronteira comum recebam cores diferentes? Não é obrigatório usar todas as cores, e cada região recebe uma única cor. R3 R4 C R2 R1

Figura da questão 1.105
Ver a resolução

1. Pinte primeiro a região central: 4 escolhas. 2. Fixada a cor de C, as quatro regiões externas só podem usar as outras 3 cores, e formam um ciclo: R1 é vizinha de R2, que é vizinha de R3, que é vizinha de R4, que é vizinha de R1. 3. Conte as pinturas do ciclo de quatro regiões com 3 cores. Pinte R1 (3 modos) e R2 (2 modos). Para R3 há dois casos: se R3 recebe a cor de R1 (1 modo), então R4 só precisa diferir de R3 e de R1 — que têm a mesma cor —, e há 2 escolhas; se R3 recebe a terceira cor (1 modo), R4 deve diferir de R3 e de R1, restando 1 escolha. 4. Logo o ciclo admite 3 × 2 × (1 × 2 + 1 × 1) = 6 × 3 = 18 pinturas. 5. Total: 4 × 18 = 72. Em geral, um ciclo com m regiões e k cores admite (k−1)m+(−1)m(k−1) pinturas; com m = 4 e k = 3 isso dá 16 + 2 = 18. Resposta: 72 modos.

voltar ao índice

Questão 1.106

Considere as funções f(x) = ax + bcx + d, definidas no seu domínio natural, em que a,b,c,d ∈ {−2,−1,0,1,2} e ad − bc ≠ 0. Duas quádruplas (a,b,c,d) que definem a mesma lei correspondem à mesma função. Determine o número de funções distintas desse tipo cujo gráfico é simétrico em relação à reta y = x.

Ver a resolução

1. Um gráfico é simétrico em relação à reta y = x exatamente quando a função coincide com a sua inversa, isto é, quando f(f(x)) = x para todo x do domínio. 2. Calculando a composta, a · acxx++db + b (a2 + bc)x + b(a + d) f(f(x)) = =. c · acxx++db + d c(a + d)x + (bc + d2) 3. Essa expressão é igual a x para todo x quando b(a+d) = 0, c(a+d) = 0 e a2 + bc = bc + d2, ou seja, a2 = d2. Há dois casos: a + d = 0, ou b = c = 0 com a = d — e esse segundo caso é a função identidade. 4. Resta contar as funções com d = −a. Duas quádruplas proporcionais dão a mesma função, de modo que cada função é representada uma única vez pela sua quádrupla primitiva — a de máximo divisor comum 1 —, tomada a menos de sinal. Separamos pelos valores de a, exigindo a2 + bc ≠ 0: • a = 0: então f(x) = bcx com b,c ≠ 0, e a função depende só da razão b/c ∈ {±1,±2,±12} — 6 funções; • a = 1: b e c livres em {−2,...,2}, exceto bc = −1, que anula o determinante — 25 − 2 = 23 funções; • a = 2: de novo 25 pares, menos os 2 com bc = −4; e é preciso descartar os que têm b e c ambos pares, pois aí a quádrupla não é primitiva — sobram 23 − 7 = 16 funções. 5. Somando e acrescentando a identidade: 6 + 23 + 16 + 1 = 46. As mais simples da lista são f(x) = x, f(x) = 1/x, f(x) = −1/x, f(x) = 2/x e f(x) = −x; a condição a+d = 0 diz que todas as outras são da forma f(x) = ax + bcx − a. Resposta: 46 funções.

voltar ao índice

Questão 1.107

Considere os conjuntos X = {1,2,3,4,5} e Y = {1,2,3,4,5,6,7,8}.

a) Se Y ′ é um subconjunto de Y com três elementos, quantas são as funções f: X → Y ′ sobrejetoras? b) Quantas funções f: X → Y, não necessariamente injetoras, existem tais que |f(i) − f(j)| ≠ 1 para quaisquer i,j ∈ X?

Ver a resolução

1. Item a). São as funções de um conjunto de 5 elementos sobre um de 3. Por inclusão–exclusão, 3! 3! 35 − 25 + 15 = 243 − 96 + 3 = 150. 1 2 2. Item b). A condição não envolve os índices: ela diz que o conjunto imagem não pode conter dois inteiros consecutivos. 3. Conte por tamanho da imagem. Um subconjunto A ⊆ Y com t ele(cid:16)8−t+1(cid:17) mentos e sem dois consecutivos pode ser escolhido de modos, t e as funções de X sobre A são as sobrejetoras de 5 elementos em t. 4. Para t = 1,2,3,4 — não cabem 5 elementos não consecutivos em Y (cid:16)4(cid:17) com imagem de tamanho 5, pois = 0 — temos 8! 7! 6! 5! ·1+ ·30+ ·150+ ·240 = 8+630+3000+1200 = 4838, 1 2 3 4 usando que as sobrejetoras de 5 em t são 1, 30, 150 e 240 para t = 1,2,3,4. Resposta:

a) 150 funções;

b) 4838 funções.

voltar ao índice