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

[Augusto Morgado <morgado@xxxxxxxxxxxxxxx>]

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