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