Correção da segunda prova para casa

Universidade Federal de Uberlândia
Bacharelado em Ciência da Computação
Matemática para Ciência da Computação
Profa. Sandra de Amo
Segunda Prova para Casa : 20-9-2004
Questão 1
Quantos anagramas diferentes se pode formar com a palavra FACETIOUSLY dado
que todas as seis vogais devem permanecer em ordem alfabética (mas não necessariamente
contı́guas umas às outras) ?
Sugestão: Temos C 1 16 possibilidades de distribuirmos as 6 vogais (AEIOUY) no anagrama (de 11 letras ao todo). Para cada uma destas combinações referentes ao posicionamento das vogais (em ordem alfabética), existem 5! possibilidades de distribuirmos
as consoantes (FCTSL). Assim, o total de anagramas diferentes mantendo as vogais em
ordem alfabética é C 1 16 *5! = 11*10*9*8*7 = 55.440.
Questão 2
Classifique as relações abaixo sobre o conjunto dos números naturais em (a) relação
de equivalência, (b) relação de ordem (c) nenhuma das anteriores. Justifique sua resposta. Analise cada uma das propriedades reflexiva, transitiva, simetrica, antissimetrica,
transitiva.
1. R1 = {(x, y) | x e y são pares ou x e y são ı́mpares }.
Solução :
• A relação é reflexiva. De fato, qualquer número x, podemos afirmar que x está
relacionado com ele próprio, pois x e x são pares ou x e x são ı́mpares.
• A relação é simétrica. De fato, suponhamos que (x, y) ∈ R1 . Então, temos
duas possibilidades : ou x e y são pares ou x e y são ı́mpares. Logo, podemos
afirmar que ou y e x são pares ou y e x são impares. Logo (y, x) ∈ R1 .
• A relação não é antissimétrica, pois (2, 4) ∈ R1 , (4, 2) ∈ R1 , mas 2 6= 4.
• A relação é transitiva. De fato, suponhamos que (x, y) ∈ R1 e (y, z) ∈ R1 .
Temos as seguintes possibilidades a considerar :
(a) x e y são pares e y e z são pares. Neste caso, é claro que x e z são pares,
e portanto (x, z) ∈ R1 .
(b) x e y são impares e y e z são impares. Neste caso, é claro que x e z são
impares, e portanto (x, z) ∈ R1 .
A partir da análise acima, concluimos que R1 é uma relação de equivalência mas
não é uma relação de ordem, já que não é antissimétrica.
2. R2 = {(x, y) | x e y são ambos múltiplos de 3 ou x e y são ambos sucessores de
múltiplos de 3 ou x e y são ambos sucessores de sucessores de múltiplos de 3 }. Por
exemplo :(3,12) e (4,13) e (5,14) estão relacionados. Já (1,2) não estão relacionados.
Solução:
• A relação é reflexiva. De fato, qualquer número x temos que x = 3k, ou
x = 3k + 1 ou x = 3k + 2, para algum k. Logo, qualquer número x está
relacionado consigo mesmo, pois x e x são ambos múltiplos de 3 ou x e x são
ambos sucessores de múltiplos de 3 ou x e x são ambos sucessores de sucessores
de múltiplos de 3.
• A relação é simétrica. De fato, suponhamos que (x, y) ∈ R2 . Então, temos
3 possibilidades : (1) ou x e y são multiplos de 3 ou (2) x e y são sucessores
de multiplos de 3 ou (3) x e y são sucessores de sucessores de multiplos de 3.
No primeiro caso, podemos afirmar que y e x são multiplos de 3. No segundo
caso, podemos afirmar que y e x são sucessores de multiplos de 3 e no terceiro
caso, podemos afirmar que y e x são sucessores de sucessores de multiplos de
3. Logo, em cada um dos 3 casos, temos que (y, x) ∈ R2 .
• A relação não é antissimétrica, pois (3, 6) ∈ R2 , (6, 3) ∈ R2 , mas 3 6= 6.
• A relação é transitiva. De fato, suponhamos que (x, y) ∈ R2 e (y, z) ∈
R2 . Então, temos 3 possibilidades : (1) ou x e y são multiplos de 3 E y e
z são multiplos de 3, ou (2) x e y são sucessores de multiplos de 3 E y e z
são sucessores de múltiplos de 3 ou (3) x e y são sucessores de sucessores de
multiplos de 3 E y e z são sucessores de sucessores de múltiplos de 3 . No
primeiro caso, podemos afirmar que x e z são multiplos de 3. No segundo
caso, podemos afirmar que x e z são sucessores de multiplos de 3 e no terceiro
caso, podemos afirmar que x e z são sucessores de sucessores de multiplos de
3. Logo, em cada um dos 3 casos, temos que (x, z) ∈ R2 .
A partir da análise acima, concluimos que R2 é uma relação de equivalência mas
não é uma relação de ordem, já que não é antissimétrica.
3. R3 = {(x, y) | x = y ou mdc(x, y) = 1}
Solução:
• A relação é reflexiva, pois qualquer x, é claro que (x, x) ∈ R3 , já que x = x.
• A relação é simétrica, pois se x = y então y = x, e se mdc(x, y) = 1 então
mdc(y, x) = 1.
• A relação não é antissimétrica, pois se (2, 5) ∈ R3 , (5, 2) ∈ R3 , mas x 6= y.
• A relação não é transitiva, pois (2, 5) ∈ R3 , (5, 12) ∈ R3 , mas (2,12) 6∈ R3 , já
que 2 6= 12 e mdc(2,12) 6= 1.
A partir da análise acima, concluimos que R3 não é uma relação de equivalência,
pois não é transitiva, nem é uma relação de ordem, pois não é nem antissimétrica
nem transitiva.
Questão 3
Duas moedas diferentes são colocadas em casas de um tabuleiro de xadrez (8 x 8).
Elas podem ser colocadas ambas na mesma casa. Chamemos “equivalentes” dois arranjos
dessas moedas no tabuleiro se pudermos mover as moedas diagonalmente para passar de
um arranjo para outro. Por exemplo, as duas configurações mostradas nos dois tabuleiros
abaixo são equivalentes:
Porém, as duas configurações mostradas nos dois tabuleiros abaixo não são equivalentes :
De quantas maneiras (não equivalentes) as moedas podem ser colocadas no tabuleiro ?
Sugestão : analise quantas configurações existem em cada classe de equivalência. Analise
o número total de configurações. O que está sendo pedido é o número de classes de
equivalência.
Solução:
Considere o tabuleiro de xadrez abaixo (as casas com um circulo dentro são as casas
pretas e as sem nenhum circulo dentro são as brancas).
1. Se uma moeda 1 é colocada numa casa preta, então qualquer movimento em zig-zag
(por diagonais) que fazemos com esta moeda, a posição final é numa casa preta. Não
dá para passar de uma casa preta para uma branca somente fazendo movimentos
nas diagonais. (Tente !)
2. Se uma moeda é colocada numa casa branca, então então qualquer movimento em
zig-zag (por diagonais) que fazemos com esta moeda, a posição final é numa casa
branca. Não dá para passar de uma casa branca para uma preta somente fazendo
movimentos nas diagonais.
Assim, temos 4 possibilidades de posicionar as 2 moedas no inicio :
1. Moeda 1 e Moeda 2 em casas pretas.
2. Moeda 1 numa casa preta e Moeda 2 numa casa branca.
3. Moeda 1 numa casa branca e Moeda 2 numa casa preta.
4. Moeda 1 e Moeda 2 em casas brancas.
Seja (P1 , P2 ) um posicionamento das duas moedas (1 na posição P1 e 2 na posição
P2 ). Dizemos que dois posicionamentos (P1 , P2 ) e (Q1 , Q2 ) são equivalentes se uma das 4
condições abaixo se verificam :
1. se (P1 , P2 ) e (Q1 , Q2 ) se as duas casas de (P1 , P2 ) são pretas e as duas de (Q1 , Q2 )
também são pretas.
2. se (P1 , P2 ) e (Q1 , Q2 ) se a casa de P1 é preta e a de P2 é branca e o mesmo vale para
Q1 (preta) e Q2 (branca).
3. se (P1 , P2 ) e (Q1 , Q2 ) se a casa de P1 é branca e a de P2 é preta e o mesmo vale para
Q1 (branca) e Q2 (preta).
4. se (P1 , P2 ) e (Q1 , Q2 ) se as duas casas de (P1 , P2 ) são brancas e as duas de (Q1 , Q2 )
também são pretas.
Assim : de Preta-Preta só posso passar para Preta-Preta.
De Preta-Branca só posso passar para Preta-Branca.
De Branca-Preta só posso passar para Branca-Preta.
De Branca-Branca só posso passar para Branca-Branca.
Portanto, o número de classes de equivalência é 4.