Re: Questões de combinatória/jogos

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

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.