Suponha que cada um dos elementos de S = {1,2,..,n} deva ser colorido de vermelho ou azul. Mostre que, se A 1 ,   … ,   A n , são subconjuntos de S, há uma maneira de colorir em que no máximo ∑ i = 1 r 1 2 A i - 1 desses subconjuntos têm todos os elementos da mesma cor (onde | A | 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 A 1 , … ,   A r de S . Definindo indicadores de variáveis ​​aleatórias I j que marcam se todos os elementos em A j são da mesma cor. Nós temos que

P I j = 1 = 2 ∙ 1 2 A j = 1 2 A j - 1

Já que queremos que todos os elementos sejam vermelhos ou todos os elementos sejam azuis. Definindo uma variável aleatória, temos

X =   ∑ j = 1 r I j

Observe que X é a variável aleatória que conta quantos subconjuntos têm cores comum. Portanto

E X = E ∑ j = 1 r I j =   ∑ j = 1 r P I j = 1

Com isso, nós temos que

E X =   ∑ j = 1 r 1 2 A i - 1

Então, tem que existir uma realização de variável aleatória tal que

X ω ≤ ∑ j = 1 r 1 2 A i - 1

Passo 2

Caso contrário, se fosse isso X ω >   ∑ j = 1 r 1 2 A i - 1 , certamente teríamos que

E X = ∫ Ω X   d P > ∫ Ω ∑ j = 1 r 1 2 A i - 1   d P

Com isso, nós temos que

E X = ∑ j = 1 r 1 2 A i - 1 = E ( X )

O que é obviamente uma contradição. Assim, provamos que existe uma coloração de modo que na maioria desses subconjuntos ∑ j = 1 r 1 2 A i - 1 tenha a cor comum.

Resposta

Ei, a resposta está no passo a passo :)