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 [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
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.
