Opa, descobri outro dia que a prova desse problema (na versão para grafos),
é um teorema com nome - teorema de Dirac (não o Paul). Não deve sair por
indução mesmo!
2011/2/28 Rogerio Ponce
> Oi Bernardo e Pedro,
> voces tem razao!
> Nao da' para usar inducao quando temos 2K pessoas, pois ao tirar
Oi Bernardo e Pedro,
voces tem razao!
Nao da' para usar inducao quando temos 2K pessoas, pois ao tirarmos o Joao,
talvez nem todos os participantes do grupo 2K-1 permanecam com o minimo de K
amigos ( teto(2K-1) = K ).
Portanto, nao podemos aplicar a hipotese ao grupo 2K-1.
Em provas por inducao, qu
Olá...
Ponce, eu ainda acho que o Bernado está certo - não dá pra usar a H.I.
quando se tira o João da roda.
2011/2/25 Bernardo Freitas Paulo da Costa
> Oi Ponce !
>
> 2011/2/25 Rogerio Ponce :
> > Bernardo,
> > acho que voce se confundiu nisso daqui:
> >
> > "Se você retirar qualquer um dos pa
Oi Ponce !
2011/2/25 Rogerio Ponce :
> Bernardo,
> acho que voce se confundiu nisso daqui:
>
> "Se você retirar qualquer um dos participantes de grupo, já era, porque
> sobram (sem perda de generalidade) A,B e C, e você não pode botar A do lado
> de C..."
>
> Nos queremos justamente colocar pessoa
Bernardo,
com o Joao no grupo de N+1 pessoas, marque um X nas costas dos amigos dele.
Retire o Joao do grupo.
Suponhamos que a conjetura valha para N, certo?
Faca uma arrumacao legal com o que sobrou.
Havera' pelo menos duas pessoas lado a lado e com X nas costas.
Coloque o Joao entre estes dois.
Bernardo,
acho que voce se confundiu nisso daqui:
"Se você retirar qualquer um dos participantes de grupo, já era, porque
sobram (sem perda de generalidade) A,B e C, e você não pode botar A do lado
de C..."
Nos queremos justamente colocar pessoas lado a lado, e o grupo esta' reunido
numa roda.
[]
2011/2/25 Rogerio Ponce :
> Oi Pedro, vamos la'...
>
> 1) Sabemos que a conjetura e' valida para um grupo com 3 pessoas.
>
> 2) Seja um grupo com 2K pessoas, incluindo Joao que, como todos, tem K
> amigos no grupo.
> Suponhamos que a conjetura seja valida para o grupo de 2K-1 pessoas
> (excluindo J
Oi Pedro, vamos la'...
1) Sabemos que a conjetura e' valida para um grupo com 3 pessoas.
2) Seja um grupo com 2K pessoas, incluindo Joao que, como todos, tem K
amigos no grupo.
Suponhamos que a conjetura seja valida para o grupo de 2K-1 pessoas
(excluindo Joao).
Portanto existe uma arrumacao lega
Opa, perdão! Confundi teto[ (2N+1)/2] = N+1. De qualquer forma, não funciona
do N ímpar pro N par mesmo. Olha só, Bernardo, Rogério e os demais...
repetindo o enunciado por questão de clareza ---
"Prove que num grupo de N pessoas - onde cada pessoa tem pelo menos
teto(N/2) amigos
9 matches
Mail list logo
