90
edits
Changes
→Exemplos da Seção 4.2
Provar que em qualquer grupo de três números inteiros positivos, existem pelo menos dois, cuja a soma é par.
'''Solução:'''
Considere dois compartimentos, classificado em Par e Ímpar. Se três inteiros positivos são colocados nestes compartimentos, um deles deve ter pelo menos dois inteiros (digamos A e B) no mesmo compartimento. Assim, A e B são ou ambos par ou impar. Em ambos os casos, A + B é PAR.
Se forem escolhidos inteiros positivos aleatoriamente, qual é o número mínimo que podemos garantir que dois dos números escolhidos sejam congruentes módulo 6.
'''Solução:'''
Para que A e B serem congruentes módulo 6, temos de ter a mod 6 = b mod 6. Mas existem 6 possibilidades para x mod 6: 0, 1, 2, 3, 4, ou 5. Portanto, 7 inteiros positivos devem ser escolhidos de modo a garantir que, pelo menos, dois sejam congruentes módulo 6.
'''EXEMPLO (E3, página 314)'''
Prove que em qualquer conjunto de 700 palavras em inglês, deve haver pelo menos duas que começam com o mesmo par de letras (na mesma ordem), por exemplo, ST OP e STAndard.
'''Solução: '''O número de possíveis pares de letras que podem aparecer nas duas primeiras posições é 26 x 26=676.Assim, qualquer conjunto de 677 ou mais palavras deve ter pelo menos duas palavras com o mesmo par de letras no início da palavra.
(OBS:. Na realidade, o número 700 pode ser substituída com um número muito menor, uma vez que muitas combinações de letras não aparecem como as duas primeiras letras de uma palavra, por exemplo, não há palavras inglesas que começam com NQ, RR, ou TZ).
'''EXEMPLO (E4, página 315)'''
Cada tipo de peça de uma máquina feita em uma fábrica é carimbada com um código do formulário de letter-digit-digit, onde os dígitos podem ser repetidos. Prove que, se 8000 peças são feitas, então, pelo menos, quatro delas devem ter o mesmo código carimbadas.
'''Solução: '''O numero de codigos possiveis 26 x 10 x 10 = 2600. Desde que,8000 > 3 x 2600,pelo menos 4 tenham o mesmo codigo.
'''EXEMPLO (E5, página 315)'''
Cada aluno é classificado como um membro de uma das seguintes classes: Freshman, Sophomore, Junior, Senior. Encontrar o número mínimo de estudantes que devem ser escolhidos de modo a garantir que, pelo menos, oito pertencem à mesma classe.
'''Solução:'''De um grupo de 28 estudantes podem ser 7 pertencentes a cada classe.Mas se há 29 estudantes, pelo menos 8 devem ser membros da mesma classe.Portanto, o número mínimo de estudantes que deve ser escolhido é de 29.
Em outras palavras, nós estamos olhando para o número mínimo N tal que <math>|\frac{N}{4} | = 8</math>. O numero minimo é 29.