Suponha que cada um dos elementos de S = {1,2,..,n} deva ser colorido de vermelho ou azul. Mostre que, se , são subconjuntos de S, há uma maneira de colorir em que no máximo desses subconjuntos têm todos os elementos da mesma cor (onde representa o número de elementos no conjunto A).
Passo 1
Fala pessoal, tudo certinho? vamos responder mais uma questão, então prepara o material e vamos responder!!
Suponha que escolhemos nossos subconjuntos de de . Definindo indicadores de variáveis aleatórias que marcam se todos os elementos em são da mesma cor. Nós temos que
Já que queremos que todos os elementos sejam vermelhos ou todos os elementos sejam azuis. Definindo uma variável aleatória, temos
Observe que é a variável aleatória que conta quantos subconjuntos têm cores comum. Portanto
Com isso, nós temos que
Então, tem que existir uma realização de variável aleatória tal que
Passo 2
Caso contrário, se fosse isso , certamente teríamos que
Com isso, nós temos que
O que é obviamente uma contradição. Assim, provamos que existe uma coloração de modo que na maioria desses subconjuntos tenha a cor comum.
Resposta
Ei, a resposta está no passo a passo :)