Um problema muito interesasnte envolvendo a casa dos pombos.
Temos 55 elementos do conjunto {1,2,3,….,100}, Prove que dois desses elementos terão como diferença +, outros dois 10, outro par 12, mas que não haverá, obrigatoriamente, dois cuja diferença seja 11.
_______________________________________________________________________________________________________________________-
Parte 1 : Começamos mostrando a diferença 11.
Vamos criar as casas, que nesse caso serão conjuntos bem definidos.
I – {1,12,23,….,100}
II – {2,13,24,…….,90}
III – {3,14,25,……,91}
..
XI – {11,22,33,……..,99}
Vamos contar quantos elementos há em cada casa, não sabe fazer isso?.. nem eu ^^ mas vamos tentar.
vemos que de 1 pra 12 variou 11 e de 12 pra 23 variou 11 tb, então podemos fazer por P.A
100 = 1 + (n – 1)11
99 = 11n – 11
110/11 = n
n = 10
I – 10 elementos
II – 9 elementos
III – 9 elementos
IV – 9 elementos.
..
XI – 9 elementos.
Fato é que, se pegarmos 2 elementos do mesmo grupo eles podem ou não deixar diferença 11, para deixar basta pegar o consecutivo, como não queremos isso então temos que pegar os não consecutivos.
Cada casa então contribuirá com 5 elementos, por exemplo:
casa II {2,13,…,90} [ x ] [ ] [ x ] [ ] [ x ] [ ] [ x ] [ ] [ x ]
5 quadrados marcados com x, então de forma analoga pegamos dos demais.
Isso significa dizer que, se pegarmos 6 elementos de um grupo, obrigatoriamente terá diferença 11. Porém o exercicio pede para formarmos um grupo de 55 elementos, que NÃO deixem diferença 11, isso é possivel?
Claramente é, pois temos 11 casas, cada uma pode fornecer 5 elementos sem diferença 11 então 5 x 11 = 55, e finalizamos a primeira parte.
______________________________________________________________________________________________________________
Parte 2 : Diferença 9
Vamos fazer da mesma maneira agora para a diferença 9, porém queremos que seja qual for o grupo de 55 elementos, haverá diferença 9.
I – {1,10,19,………..,100}
II – {2,11,20,…….,92}
III – {3,12,21,…….,93}
..
IX – {9,18,…….,99}
Vamos contar quantos elementos temos em cada casa:
I – 12 elementos
II – 11 elementos
II- 11 elementos
..
IX – 11 elementos.
Vamos agora determinar quantos elementos podemos pegar para que não haja diferença 9, pra tanto devemos escolher os não consecutivos, vamos fazer apenas para o conjunto I os demais seram da mesma forma:
I – {1,10,………,100} [ x ] [ ] [ x ] [ ] [ x ] [ ] [ x ] [ ] [ x ] [ ] [ x ] [ ]
Temos 6 elementos, não consecutivos, que não deixam diferença 9, isso vai se repetir para os demais 8 grupos restantes.
Se de cada grupo podemos pegar 6 elementos sem dar diferença 9, o maior grupo que poderemos formar com isso será um grupo de 54 elementos. Porém o exercicio diz que o grupo terá que ter 55 elementos, então o próximo que pegarmos, seja ele de que grupo for, irá deixar diferença 9 com algum outro. c.q.d
____________________________________________________________________________________________________
Parte 3 : Diferença 10
Definindo as casas:
I- {1,11,21,………….,91}
II – {2,12,22,……..,92}
..
X – {10,20,30,……….,100}
Quantos elementos temos nas casas?
I -10 elementos..
II – 10 elementos
..
X – 10 elementos
Para não ter diferença 10, devemos pegar os não consecutivos, que serão definidos da seguinte maneira:
I – {1,11,21,…..,91} = [ x ] [ ] [ x ] [ ] [ x ] [ ] [ x ] [ ] [ x ] [ ]
Podemos pegar 5 elementos de cada grupo que não deixaram diferença 10, então no geral podemos pegar 50 elementos que nenhum deles deixara diferença 10, porém nosso grupo é formado por 55 elementos, então os próximos 5 elementos escolhidos irá, obrigatoriamente, deixar diferença 10.
O caso diferença 12, fica para quem quiser tentar ^^