Re: =?x-user-defined?Q?Quest=F5es?= de =?x-user-defined?Q?combinat=F3ria=2Fjogos?=

[Augusto Morgado <morgado@xxxxxxxxxxxxxxx>]

É, mas o idiota aqui teria poupado muito esforço e teria sido muito mais
claro se tivesse começado escrevendo a+b=c como a=c-b.
Morgado

Paulo Santa Rita wrote:
> 
> Ola Pessoal,
> 
> A solucao abaixo - do Prof Morgado - e muito bonita ! A linha de raciocinio
> e muito semelhante a que leva a solucao de um outro problema olimpico, cujo
> enunciado segue abaixo :
> 
> Num poligono convexo de N lados,
> 
> 1)Dois lados quaisquer nao sao paralelos
> 2)Duas diagonais quaisquer nao sao paralelas
> 
> Quantos pontos no exterior do poligono sao pontos de inteseccao de diagonais
> ?
> 
> OBS : E dado que tres ou mais diagonais nunca se cruzam em um mesmo ponto.
> 
> >Leia a1 como a indice 1.
> >Observe inicialmente que a diferença entre dois elementos
> >distintos(maior-menor) do conjunto é ainda um relemento do conjunto.
> >Fixe a1=1. Considere as 48 diferenças a2-a1,..., a48-a1.Algum dos três
> >conjuntos conterá pelo menos dezesseis dessas 48 diferenças. Sejam b1,
> >b2,...,b16 essas diferenças e seja X o conjunto ao qual elas pertencem.
> >Considere as 15 diferenças b2-b1=c1,...,b16-b1=c15.
> >Se alguma dessa diferenças pertencer a X, X conterá b1, bk-b1 e bk, isto
> >é, as-a1, aj-a1-(as-a1)=aj-as e aj-a1; fim, pois o terceiro é a soma dos
> >dois primeiros.
> >
> >Caso contrário as 15 diferenças pertencerao aos outros dois conjuntos Y
> >e Z, havendo em um dos conjuntos, digamos Y, pelo menos 8 dessas
> >diferenças.Chamemos essas diferenças de d1,...,d8.Considere as 7
> >diferenças d2-d1,...,d8-d1.Note que essas diferenças sao diferenças
> >entre bês e portanto diferenças entre elementos da sequencia dos a,
> >estando ja excluida a possibilidade de alguma delas pertencer a X.
> >Se alguma dessa diferenças pertencer a Y, Y conterá d1, dp-d1 e dp, isto
> >é, bm-b1=ar-a1-(as-a1)=ar-as, bn-a1-(bm-b1)=bn-bm=(au-a1)-(ar-a1)=au-ar
> >e bn-b1=(au-a1)-(as-a1)=au-as; fim, pois o terceiro é a soma dos dois
> >primeiros.
> >Caso contrário, as 7 diferenças d2-d1=e1,...,d8-d1=e7 pertencerao a Z.
> >As seis diferenças e2-e1,...,e7-e1 pertencerao a Z pois sao diferenças
> >entre termos da sequencia dos d, estando ja excluida a possibilidade de
> >pertencerem a Y. Entao Z contera e1, ef-e1, ef ...fim, pois o terceiro é
> >a soma dos dois primeiros.
> >
> >
> >
> >Alexandre Tessarollo wrote:
> > >
> > > Marcelo Rufino de Oliveira wrote:
> > >
> > > > Abaixo vão 2 problemas de combinatória/jogos que eu ainda não consegui
> > > > fazer.
> > > > Já mandei estas mesmas duas questões anteriormente para a lista mas
> > > > infelizmente ninguém se manifestou... vamos ver se desta vez alguém
> >pode me
> > > > ajudar.
> > > > Já agradeço, de antemão, aos participantes da lista que tentarem fazer
> >algum
> > > > dos problemas, pois estes não são elementares.
> > > >
> > > > 1) O conjunto {1, 2, ..., 49} é particionado em 3 subconjuntos
> >disjuntos.
> > > > Mostre que ao menos um dos subconjuntos possui três números a, b e c
> >tais
> > > > que a + b = c.
> > > >
> > >
> > > Hum, vamos ver...
> > > 1a hipótese: Separamos de acordo com o resto na divisão por 3.
> > >
> > > Assim, temos o grupo que resta 1, o que resta 2 e o que não resta nada.
> >Neste
> > > último, basta pegar números a=3k, b=3j e c=3(k+j). Naturalmente, k e j
> >são
> > > naturais não-nulos, k é diferente de j e k+j<17. (Isto para que a,b e c
> >estejam
> > > no conjunto original {1,..,49})
> > >
> > >     Ih, tô vendo que vai dar um certo trabalho e eu tenho aula daqui a
> >dez
> > > minutos... Bem, veja se consegue mostrar o que o problema pede pensando
> >nessas
> > > possibilidades. Talvez tenha uma maneira mais direta, não sei. Vou ver
> >se até
> > > amanhã eu consigo resolver e digitar tudo.
> > >
> > > []'s
> > >
> > > Alexandre Tessarollo
> > >
> > > PS: Sei que não é a resolução completa, mas de repente ajuda... :-)
> > >
> > > >
> > > > 2) Dado um retângulo 1993x1994, dois jogadores (um de cada vez)
> >escreve os
> > > > números 0 ou 1 nas casas. Quando o tabuleiro  está completo seja A o
> >máximo
> > > > valor das somas das 1993 linhas e B o máximo valor das somas das
> >colunas. No
> > > > caso em que A > B o primeiro ganha, no outro caso B ganha. Quem possui
> >uma
> > > > estratégia vencedora?
> > > >
> > > > Falou,
> > > > Marcelo Rufino
> 
> _________________________________________________________________________
> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.