2009/9/23 Lucas Colucci <lucascolu...@hotmail.com> > Olá membros da lista, gostaria de uma ajuda ajuda no seguinte problema: > > Os inteiros positivos 1, 2, ..., n são colocados nos vértices de um > n-ágono. Cada vértice é pintado de: > > *Vermelho, se ambos os números nos vértices vizinhos são maiores do que o > número neste vértice; > *Azul, se ambos os números nos vértices vizinhos são menores do que o > número neste vértice; > *Branco, se nenhuma das duas condições acima for satisfeita. > Prove que o número de vértices vermelhos é igual ao número de vértices > azuis. > > Também gostaria de algum material bom sobre contagem dupla, não > necessariamente em português, caso alguém conhecesse. >
Imagine que saiam flechas dos vértices menores para seus vizinhos maiores (em vez de uma reta). Para cada permutação, todo lado possuirá uma flecha correspondente (não existem dois números iguais). É possível fazer uma indução. A base é a disposição de flechas num mesmo sentido (sentido horário por exemplo), nesta situação o número de vértices de onde partem duas flechas (vértices azuis) é igual ao número de vértices para onde chegam duas flechas (vértices vermelhos), note que esta base não representa nenhuma disposição possível de se chegar com os dados do problema: a -> b -> c -> d -> ... -> z -> a O passo de indução seria mudar uma única flecha de sentido e ver que os números de vértices azuis e vermelhos continuam iguais.
