PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Princípio da Casa dos Pombos

2 participantes

Ir para baixo

Princípio da Casa dos Pombos Empty Princípio da Casa dos Pombos

Mensagem por Perceval Sáb 03 Abr 2021, 12:54

(EUA)  Em uma festa há n pessoas. Prove que existem duas pessoas tais que, das n-2 pessoas restantes é possível achar [latex]\left \lfloor \frac{n}{2}\right \rfloor-1[/latex] onde cada uma delas conhece ou não conhecem ambas.
Perceval
Perceval
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 121
Data de inscrição : 03/01/2021

Ir para o topo Ir para baixo

Princípio da Casa dos Pombos Empty Re: Princípio da Casa dos Pombos

Mensagem por NikolsLife Sex 15 Out 2021, 15:48

É teoria dos grafos. Vou considerar como dois pontos encontrados A e B

Considere o número de pares (X, {Y, Z}), onde X, Y, Z são pontos distintos, de modo que X é unido a apenas um de Y, Z. Se X é unido a apenas k pontos, então há apenas [latex] k (n - 1 - k) \leq \frac{(n - 1)^2}{4} [/latex] desses pares (X, {Y, Z}). Portanto, no total, há no máximo [latex] \frac{n (n - 1)^2}{4}[/latex] desses pares. Mas há [latex] \frac{n (n - 1) }{2} [/latex] possíveis {Y, Z}. Portanto, devemos ser capazes de encontrar um deles {A, B} que pertença a no máximo [latex] \frac{(n - 1)}{2}[/latex]  desses pares. Portanto, há pelo menos [latex] n - 2 - [\frac{n - 1}{ 2}] = [\frac{n}{2}] - 1[/latex]  pontos X que são unidos a ambos A e B ou a nenhum de A e B.
NikolsLife
NikolsLife
Padawan
Padawan

Mensagens : 84
Data de inscrição : 10/12/2019

Ir para o topo Ir para baixo

Ir para o topo

- Tópicos semelhantes

 
Permissões neste sub-fórum
Não podes responder a tópicos