Re: Questões de combinatória/jogos

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

Ola Pessoal,

Das duas belas questoes abaixo - aplicacoes de variantes do principio da 
casa dos pombos, apresentadas pelo nosso colega Marcelo Rufino - a segunda 
ainda nao teve uma solucao apresentada aqui na lista. Talvez a observacao 
abaixo possa ajudar ...

Supondo que as linhas estao numeradas de 1 ate 1993 e, as colunas, de 1 ate 
1994, sejam L(i) e C(j) as somas respectivas da linha i e da coluna j. 
Claramente que, apos o encerramento do jogo :

L(1) + L(2) + ... + L(1993) = C(1)+ C(2) + ... + C(1994)

Portanto, um mesmo numero precisara ser distribuido tanto em 1993 casas ( as 
linhas ), quanto em 1994 outras casas ( as colunas ). Evidentemente que se 
este numero for multiplo de 1994 e distribuido uniformemente entre as 
colunas, pelo principio da casa dos pombos, havera ao menos uma linha que 
contera uma ( ou mais ) unidade a mais que a maior quantidade que esta nas 
colunas...

A titulo de exemplificacao:

1994 numeros 1´s, distribuidos uniformemente em 1994 casas (colunas), 
implica em uma unidade em cada coluna. Todavia, quando distribuirmos os 
mesmo 1994 em 1993 casas ( as linhas ), havera ao menos uma casa com mais de 
uma unidade.

Os jogadores jogam alternadamente, logo :

1) Pode algum jogador forcar esta distribuicao uniforme ? Como ?

Um Abraco a Todos
Paulo Santa Rita
5,1302,28062001



>From: "Marcelo Rufino de Oliveira" <marcelo_rufino@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: Questões de combinatória/jogos
>Date: Thu, 21 Jun 2001 10:03:31 -0300
>
>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.
>
>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.