Programa Delta – DEEC/FEUP
Combinatória e Algoritmos1
Suponha que tem uma caixa branca com 60 bolas brancas e uma caixa preta com 60 bolas
pretas. Considere o seguinte procedimento:
1. Retiram-se 20 bolas da caixa branca, que se colocam na caixa preta.
2. Misturam-se bem as bolas da caixa preta.
3. Retiram-se 20 bolas da caixa preta (provavelmente algumas destas serão brancas e outras
pretas) e colocam-se na caixa branca.
Sem fazer esta experiência, responda à seguinte questão:
No final do procedimento, há mais bolas brancas na caixa preta ou mais bolas pretas na
caixa branca?
Conjetura:
Prova da conjetura:
1
O texto que se segue foi traduzido e adaptado do livro A Decade of the Berkeley Math Circle: The
American Experience (Msri Mathematical Circles Library) (v. 1), de Zvezdelina Stankova e Tom Rike
(Editores).
1
Faça a experiência indicada na página anterior e teste a conjetura. A conjetura verificou-se?
Repita a experiência e, se necessário, reformule a conjetura.
Conjetura∗ :
Prove a Conjetura∗ . Para tal, não basta dizer que o resultado das experiências é sempre o
mesmo! Terá de se questionar: O que é que se está a passar? Porque razão o resultado do
procedimento é sempre este? Uma prova é uma resposta a esta questão. Não só servirá para
convencer amigos e familiares incrédulos que não realizaram a experiência, como – o que é
mais importante ainda – permitirá um conhecimento mais profundo do problema. Esse tipo
de entendimento mais profundo ajudará a resolver outros problemas mais difı́ceis no futuro.
“Uma boa prova é uma prova que nos faz mais sábios.”
Yuri Manin
Tente explicar porque razão o resultado tem necessariamente de ser como a experiência faz
induzir. Escreva todos os argumentos que conceber, mesmo que não os considere satisfatórios.
Pegue em lápis e papel e escreva! Vai perceber que é difı́cil explicar as ideias cruciais. É
frequente que determinada justificação pareça muito mais convincente na sua cabeça do que
no papel. Um dos desafios de uma prova é tornar precisos os palpites vagos e as intuições. Mas
uma prova tem a grande vantagem de permitir comunicar as ideias a outros e, o que é mais
importante ainda, perceber melhor as ideias próprias.
Prova da conjetura∗ :
..
.
..
.
2
..
.
..
.
3
Provas ou Não-Provas?
Nesta altura decerto já chegou à conclusão experimental: “O número de bolas brancas na caixa
preta é sempre igual ao número de bolas pretas na caixa branca.”
Não-Provas camufladas de provas
Vejamos algumas provas inválidas deste resultado. Compare-as com a(s) sua(s) própria(s)
prova(s) e veja se os comentários ajudam a melhorar os seus argumentos.
“Prova” 1. Os dois números são iguais porque o número de bolas pretas que colocarmos
na caixa branca é igual ao número de bolas brancas que têm de ficar na caixa preta.
?
!! Este argumento pode parecer uma explicação, mas se o ler com cuidado verá
que está simplesmente a afirmar de outra forma aquilo que se queira provar! Tenha muito cuidado com “provas” que reformulam a conclusão usando termos que
parecem mais convincentes, mas que não dão nenhum argumento.
“Prova” 2. Quando movemos inicialmente as 20 bolas brancas para a caixa preta, a
proporção de bolas brancas na caixa preta é 20/80 = 1/4. Logo das 20 bolas que movemos
da caixa preta para a caixa branca, um quarto (isto é, 5 bolas) serão brancas e três quartos
(isto é, 15 bolas) serão pretas. Portanto, no final a caixa branca terá 15 bolas pretas e a
caixa preta terá 15 bolas brancas (porque primeiro acrescentámos-lhe 20 bolas brancas e
?
depois retirámos 5).
!! Esta “prova” introduz um elemento irrelevante: probabilidade. Não é por um
quarto das bolas da caixa preta serem brancas que temos a garantia de que das
20 bolas que deslocaremos para a caixa branca, 5 serão brancas. É verdade que
5 é o número mais provável de bolas brancas, mas qualquer número entre 0 e 20
é possı́vel, em teoria. A não ser que a indicação seja outra, um problema não
almeja apenas a solução mais provável, mas todas as soluções possı́veis, mesmo
que improváveis.
4
“Prova” 3. Se no final ficarem menos de 20 bolas pretas na caixa branca, então algumas
das bolas que foram colocadas nessa caixa eram brancas. Assim, a caixa preta terá menos
de 20 bolas brancas, já que algumas regressaram à caixa branca. Estes números têm de
ser iguais, porque das duas vezes foram deslocadas 20 bolas, logo, no final do processo, o
número de bolas da cor errada em cada caixa será o mesmo.
!! Este argumento já está no caminho certo, mas é demasiado vago para ser uma
prova. Porque razão o facto de ambas as caixas terem menos de 20 bolas da cor
errada implica que tenham o mesmo número de bolas da cor errada? Não é dada
uma explicação para a afirmação “Estes números têm de ser iguais”; nem é claro
o significado dessa afirmação.
“Prova” 4. Os dois números são iguais porque, qualquer que seja o número de bolas
pretas que colocarmos na caixa branca, é esse o número de bolas brancas que têm de ficar
na caixa preta. Por exemplo, se movermos 13 bolas pretas e 7 bolas brancas da caixa preta
para a caixa branca, então na caixa preta restarão 13 bolas brancas (porque inicialmente
deslocámos 20 bolas brancas para a caixa preta, das quais 7 regressam a essa caixa). Desta
forma, os números acabam sempre por ser iguais.
!! Provavelmente terá a sensação de que esta explicação revela bastante bem o
processo referido no problema. O problema é que assenta num exemplo especı́fico.
Embora um exemplo possa ser ótimo para desenvolver a intuição e sugerir ideias,
não convencerá o seu amigo mais cético: “Eu entendo que os números serão iguais
nesse exemplo”, dirá ele, “Mas como sabemos que eles serão iguais sempre, em
todos os casos concebı́veis? Não é dada nenhuma explicação para isso.” Pode
parecer uma picuinhice, mas o amigo cético tem razão: o exemplo dá a sensação
de ser representativo; mas o facto de termos de depender desta sensação mostra
que ainda não chegámos ao fundo da questão.
Mas estamos muito próximos!!
Veja se consegue modificar esta última “prova” de forma a que passe a ser uma Prova!
5
Finalmente uma prova! Melhor ainda, duas.
Prova 1. Suponhamos que o conjunto de bolas que foram colocadas na caixa branca era
constituı́do por k bolas pretas e 20 − k bolas brancas. Então a caixa branca terá k bolas
pretas, enquanto que a caixa preta terá 20 − (20 − k) = k bolas brancas, já que inicialmente
lhe pusemos 20 bolas brancas e depois destas retirámos 20 − k, que regressaram à caixa
branca. Logo cada caixa ficou com o mesmo número de bolas da cor errada.
Repare que esta prova é bastante curta! Tal é frequente: assim que entendemos a essência
do problema, podemos dar uma justificação que vai diretamente ao ponto, sem invocar questões
acessórias. Note-se ainda que a prova é muito semelhante ao exemplo da “Prova 4”. A diferença
reside em substituir os números especı́ficos do exemplo (13 bolas pretas e 7 bolas brancas) por
uma variável representativa do caso geral (k bolas pretas e 20 − k bolas brancas). Um exemplo
não é uma prova, mas em determinadas situações é muito fácil adaptá-lo para obter uma prova.
Heurı́stica para resolução de problemas Na presença de uma quantidade desconhecida (como o número de bolas pretas na caixa branca), dê-lhe um nome! Um
nome é como uma pega que podemos agarrar e usar da forma que nos for mais
conveniente. Assim que dermos um nome a uma das quantidades desconhecidas
do problema (por exemplo, k bolas pretas), poderá ser possı́vel determinar outra
quantidade desconhecida (por exemplo, 20 − (20 − k) = k bolas brancas). É
possı́vel repetir a prova acima sem atribuir um nome à quantidade desconhecida,
mas seria mais difı́cil explicar precisamente o argumento.
Prova 2. Há um total de 120 bolas: 60 brancas e 60 pretas. No final, haverá 60 destas
bolas na caixa branca e 60 na caixa preta. Se no final a caixa branca contiver k bolas
pretas e 60 − k bolas brancas, então as restantes 60 − k bolas pretas e as restantes k bolas
brancas têm de estar na caixa preta. Logo o número de bolas da cor errada em cada uma
das caixas é k.
Esta prova é ainda melhor (e um pouco mais curta), porque realmente nos torna mais
conhecedores do que está por trás do problema:
Heurı́stica para resolução de problemas Por vezes há vantagens em esquecermos
os detalhes sobre como determinado processo se desenrola (por exemplo, que bolas
foram movidas e como foram movidas, neste problema) e focarmos a atenção no
resultado final.
Outra forma de pensar no que está envolvido no problema é a seguinte: Deitamos todas
as bolas, brancas e pretas, numa tômbola e depois extraı́mos o mesmo número de bolas para
cada uma das caixas. Logo, não só não temos de pensar em como foi efetuado o movimento
das bolas, como agora entendemos que, seja qual for o número de bolas que transferimos de
6
uma caixa para a outra e seja qual for o número de vezes que efetuamos a transferência de
bolas entre as duas caixas, o resultado será sempre que o número de bolas da “cor errada” em
cada caixa é igual, desde que nos certifiquemos que no final cada caixa tem o mesmo número
total de bolas (e que não foram perdidas bolas!).
Este raciocino permite resolver imediatamente a seguinte variação do problema anterior:
Leite e café
Suponhamos que temos uma chávena branca com leite e uma chávena preta com
a mesma quantidade (volume) de café. Tiramos três colheres de leite da chávena
branca para a chávena preta contendo café, mexemos o conteúdo da chávena
preta e de seguida transferimos três colheres de lı́quido dessa chávena para a
chava branca. Qual das percentagens é maior: café no leite da chávena branca ou
leite no café da chávena preta? Como é que a resposta a esta pergunta varia se
repetirmos o processo?
7