Untitled - Arquivo Escolar

O Jogo do 24 – digressões com o Maple
Delfim F. M. Torres
[email protected]
Departamento de Matemática
Universidade de Aveiro
3810-193 Aveiro, Portugal
http://www.mat.ua.pt/delfim
1
À guisa de introdução
Há tempos tomei conhecimento do “Jogo 24”. As regras são simples: ganha quem primeiro
conseguir obter o número 24 usando todos os números dados, uma e uma só vez, e as quatro
operações +, −, ×, e ÷. O jogo 24 foi inventado por Robert Sun em 1988, com o objectivo de
mostrar que “a matemática pode ser poderosa, aliciante e, acima de tudo, divertida”. Parece-me que Robert Sun foi muito bem sucedido. Constatei que o desafio é extremamente popular
entre estudantes do ensino básico e secundário. Não vos vou contar a minha experiência em
pormenor para não ficar embaraçado: os pequerruchos gostam tanto do jogo, praticam-no com tal
entusiasmo, que acabam por desenvolver um “cálculo mental 24” verdadeiramente surpreendente.
Joguei duas ou três vezes e tive de desistir para não fazer má figura: os pequenos levavam-me
sempre a melhor! Afastei-me e liguei o portátil para fazer um programa que jogasse por mim
e que, acima de tudo, satisfizesse a minha curiosidade. Decidi partilhar convosco as minhas
experiências: o ano 2004 foi escolhido pela Associação de Professores de Matemática como o ano
da Matemática e Jogo e, quiçá, alguns de vós se sintam motivados a colocar novas questões, a
fazer novas experiências e a obter respostas novas...
2
O Jogo 24
Na sua versão mais simples são dados quatro números inteiros de um a nove. A tarefa consiste
em formar uma expressão matemática, com valor 24, usando os quatro números dados uma e uma
só vez e qualquer conjunto de operadores aritméticos +, −, ×, ÷ (e possivelmente parênteses).
Por exemplo, dados os números 1, 3, 4 e 8 são possı́veis quatro expressões não equivalentes com
resultado 24. Se introduzirmos a notação x1 = 1, x2 = 3, x3 = 4, x4 = 8, as 4 expressões-solução
são:
• x4 + x3 × (x1 + x2 ) = 8 + 4 × (1 + 3),
• x4 /(x3 /x2 − x1 ) = 8/(4/3 − 1),
• x3 × (x1 + x4 − x2 ) = 4 × (1 + 8 − 3),
• (x3 + x4 ) × (x2 − x1 ) = (4 + 8) × (3 − 1).
Claro que o número de soluções não varia se trocarmos a ordem com que indicamos os números: o
jogo [1, 3, 4, 8] é precisamente o mesmo que o jogo [8, 4, 3, 1] ou qualquer uma das suas permutações!
1
3
O Maple
O Maple faz parte de uma famı́lia de ambientes cientı́ficos apelidados de “Sistemas de Computação
Algébrica” (Computer Algebra Systems nos paı́ses anglo-saxónicos). Trata-se de uma ferramenta
matemática muito poderosa, que permite realizar uma mirı́ade de cálculos simbólicos e numéricos.
É o laboratório de “Matemática Experimental” que tenho adoptado na disciplina de Computadores
no Ensino da Matemática da licenciatura em Ensino de Matemática da Universidade de Aveiro.
Depois de se iniciar uma sessão Maple, o sistema oferece-nos uma “linha de comandos”:
>
O Maple encontra-se então à espera de ordens... Seguem-se algumas das minhas experiências. O
leitor interessado em compreender ao pormenor os comandos Maple utilizados, pode encontrar
todo o material de estudo necessário em [3].
4
Breve análise do jogo e digressões em Maple
Começamos por relembrar um resultado básico de combinatória.
Teorema 1. Se admitirmos elementos repetidos, há n+m−1
combinações de n elementos escon
lhidos de um conjunto de cardinalidade m.
Por exemplo, se considerarmos o conjunto dos números inteiros de um a três (m = 3), existem
15 combinações diferentes de quatro números (n = 4).
> with(combinat):
> t := (n,m) -> binomial(n+m-1,n):
> t(4,3);
15
É fácil, usando o Maple, enumerar todas as combinações possı́veis mencionadas no Teorema 1.
Vamos definir em Maple a função P (n, m) que, dado n e m, devolve todas as possı́veis combinações.
> L := (n,m) -> [seq(op(j),j=seq([seq(i,k=1..n)],i=1..m))]:
> L(4,3);
[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]
> P := (n,m) -> choose(L(n,m),n):
> P(4,3);
[[1, 2, 2, 2], [1, 2, 2, 3], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 1, 3], [1, 1, 1, 2], [1, 2, 3, 3], [3, 3, 3, 3],
[2, 2, 2, 2], [1, 1, 1, 1], [1, 1, 3, 3], [1, 3, 3, 3], [2, 2, 2, 3], [2, 2, 3, 3], [2, 3, 3, 3]]
> nops(P(4,3));
15
Com as nossas definições, é agora muito fácil gerar as 495 diferentes combinações de quatro números
(n = 4) de um a nove (m = 9):
> t(4,9);
495
> nops(P(4,9));
2
495
Para obtermos todas as soluções possı́veis para todas as possı́veis configurações do Jogo 24 vamos
formar, para cada uma das 495 combinações acima, todas as possı́veis expressões aritméticas.
> tira := proc(T,L)
>
local t, i, R:
>
R := L:
>
for t in T do
>
for i to nops(R) while R[i] <> t do od:
>
if i <= nops(R) then R := subsop(i=NULL,R) fi:
>
od:
>
return(R);
> end proc:
> tira([1,2,2],[1,2,1,2,3,1]);
[1, 3, 1]
> tira([3],[1,2]);
[1, 2]
> f2 := proc(LN,LO)
>
local i, j, L, o1, o2, t, z1, z2:
>
L := NULL:
>
for i in LO do
>
for j in choose(LN,2) do
>
z1 := false: z2 := false:
>
if i <> ‘/‘ or not(simplify(j[2] = 0)) then
>
o1 := simplify(apply(i,j[1],j[2])):
>
else
>
z1 := true:
>
fi:
>
if i <> ‘/‘ or not(simplify(j[1] = 0)) then
>
o2 := simplify(apply(i,j[2],j[1])):
>
else
>
z2 := true:
>
fi:
>
t := tira(j,LN):
>
if (z2 and not(z1)) or (simplify(o1 = o2)) then
>
L := L, [[o1],t]:
>
elif not(z1) and not(z2) and not(simplify(o1 = o2)) then
>
L := L, [[o1],t], [[o2],t]:
>
elif not(z2) then
>
L := L, [[o2],t]:
>
fi:
>
end do:
>
end do:
>
return([L]);
> end proc:
> t2 := f2([x1,x2],[‘+‘,‘-‘,‘*‘,‘/‘]);
x2
x1
t2 := [[x1 + x2], []], [[x1 − x2], []], [[x2 − x1], []], [[x1x2], []], [[ ], []], [[ ], []]
x2
x1
> t3 := f2([x1,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]);
3
t3 := [[[x1 + x2], [x3]], [[x1 + x3], [x2]], [[x2 + x3], [x1]], [[x1 − x2], [x3]], [[x2 − x1], [x3]],
[[x1 − x3], [x2]], [[x3 − x1], [x2]], [[x2 − x3], [x1]], [[x3 − x2], [x1]], [[x1x2], [x3]],
x1
x2
x1
[[x1x3], [x2]], [[x2x3], [x1]], [[ ], [x3]], [[ ], [x3]], [[ ], [x2]],
x2
x1
x3
x2
x3
x3
[[ ], [x2]], [[ ], [x1]], [[ ], [x1]]]
x1
x3
x2
> f2([x3+x4,x1+x2],[‘+‘,‘-‘,‘*‘,‘/‘]);
[[[x3 + x4 + x1 + x2], []], [[x3 + x4 − x1 − x2], []], [[x1 + x2 − x3 − x4], []],
x3 + x4
x1 + x2
[[(x3 + x4)(x1 + x2)], []], [[
], []], [[
], []]]
x1 + x2
x3 + x4
> todos := proc(LP,LO)
>
local i, R:
>
if LP[1][2] = [] then
>
R := {seq(op(LP[i][1]),i=1..nops(LP))};
>
else
>
R := [];
>
for i in LP do
>
R := [op(R),op(f2([op(i[1]),op(i[2])],LO))];
>
od:
>
R := todos(R,LO);
>
fi:
>
return(R);
> end proc:
> all := (LN,LO) -> todos(f2(LN,LO),LO):
> all([x1,x2],[‘+‘,‘-‘,‘*‘,‘/‘]);
x1 x2
x1 + x2, x1x2, x1 − x2, x2 − x1, ,
x2 x1
Com 4 incógnitas existem 1170 expressões matemáticas não equivalentes (é possı́vel formar mais
expressões matemáticas com os operadores aritméticos +, −, ∗, /, mas essas expressões são equivalentes a umas destas 1170):
> nops(all([x1,x2,x3,x4],[‘+‘,‘-‘,‘*‘,‘/‘]));
1170
Claro que se algumas das incógnitas forem iguais, o número de expressões matemáticas não equivalentes diminui. Se duas das incógnitas forem iguais são possı́veis 609:
> nops(all([x1,x1,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));
609
Para certos valores concretos de x1 algumas das 609 possibilidades resultam equivalentes, e o
número total de possibilidades diminui, enquanto para outros não:
> nops(all([1,1,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));
277
> nops(all([2,2,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));
541
4
> nops(all([3,3,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));
609
Já vimos que é possı́vel obter 24 a partir de [1, 3, 4, 8]. Podemos facilmente verificar este facto:
> member(24,all([1,3,4,8],[‘+‘,‘-‘,‘*‘,‘/‘]));
true
A nossa função all permite-nos muito mais. Podemos obter respostas a perguntas como:
(i) Quais os inteiros positivos possı́veis de serem obtidos a partir dos números 1,3,4 e 8 por
intermédio das operações aritméticas +, −,× e ÷?
> select(i->type(i,posint),all([1,3,4,8],[‘+‘,‘-‘,‘*‘,‘/‘]));
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 39, 40, 43, 44, 45, 48, 49, 55, 56, 57, 63, 64, 72, 84, 88, 92, 93,
95, 96, 97, 99, 100, 104, 108, 120, 128}
(ii) Quais os inteiros não positivos possı́veis de serem obtidos a partir dos números 1,3,4 e 8 por
intermédio das operações aritméticas +, −,× e ÷?
> select(i->type(i,nonposint),all([1,3,4,8],[‘+‘,‘-‘,‘*‘,‘/‘]));
{−95, −93, −92, −88, −84, −72, −64, −55, −49, −48, −43, −40, −37, −35, −34, −33,
−32, −31, −30, −29, −28, −27, −25, −24, −23, −22, −21, −20, −19, −17, −16, −15,
−14, −13, −12, −11, −10, −9, −8, −7, −6, −5, −4, −3, −2, −1, 0}
(iii) Quantos racionais positivos não inteiros, diferentes, são possı́veis de serem obtidos a partir
dos números 1,3,4 e 8 por intermédio das operações aritméticas +, −,× e ÷?
> nops(select(i->type(i,fraction) and i > 0,all([1,3,4,8],[‘+‘,‘-‘,‘*‘,‘/‘])));
198
(iv) Quantos racionais negativos não inteiros, diferentes, são possı́veis de serem obtidos a partir
dos números 1,3,4 e 8 por intermédio das operações aritméticas +, −,× e ÷?
> nops(select(i->type(i,fraction) and i < 0,all([1,3,4,8],[‘+‘,‘-‘,‘*‘,‘/‘])));
120
Ao todo é possı́vel obterem-se 427 (= 62 + 47 + 198 + 120) valores diferentes a partir do quaterno
[1,3,4,8] por intermédio das operações aritméticas +, −,× e ÷:
> numValores := L -> nops(all(L,[‘+‘,‘-‘,‘*‘,‘/‘])):
> numValores([1,3,4,8]);
427
Vamos definir uma função NumVal que nos permite associar a cada uma das diferentes combinações, o número de valores distintos possı́veis de serem alcançados por intermédio das operações
aritméticas +, −,× e ÷. Antes disso introduzimos uma notação mais compacta para as combinações do Jogo 24.
> num := L -> add(j,j=seq(L[i]*10^(nops(L)-i),i=1..nops(L))):
> num([1,2,3]);
123
5
> lista := n -> [seq(iquo(irem(n,10^(length(n)-i+1)),10^(length(n)-i)),
>
i=1..length(n))]:
> lista(123);
[1, 2, 3]
> ordena := LL -> [seq(lista(j),j=sort([seq(num(i),i=LL)]))]:
> ordena(P(4,3));
[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 3, 3], [1, 2, 2, 2], [1, 2, 2, 3],
[1, 2, 3, 3], [1, 3, 3, 3], [2, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3, 3], [2, 3, 3, 3], [3, 3, 3, 3]]
> NumVal := LL -> [seq([num(q),numValores(q)],q=ordena(LL))]:
> NV15 := NumVal(P(4,3));
N V 15 := [[1111, 11], [1112, 20], [1113, 36], [1122, 38], [1123, 66], [1133, 83], [1222, 46], [1223, 101],
[1233, 139], [1333, 99], [2222, 24], [2223, 65], [2233, 118], [2333, 108], [3333, 49]]
Olhando para o resultado anterior, concluı́mos que de entre todas as 15 combinações diferentes
de quatro números de um a três, a que conduz a um menor número de valores possı́veis de
serem obtidos é a combinação [1, 1, 1, 1] (11 valores possı́veis de serem obtidos por intermédio das
operações +, −, ×, e ÷); enquanto a combinação que conduz ao maior número de possibilidades
é a [1, 2, 3, 3] (139 valores possı́veis). Vamos definir em Maple as funções minimo e maximo que nos
permitem determinar estas combinações (a mais estéril e a mais fecunda) no caso geral.
> minMax := proc(f,LNV)
>
local i,m,R:
>
m := apply(f,seq(i[2],i=LNV));
>
R := NULL:
>
for i in LNV do
>
if i[2] = m then
>
R := R,i:
>
fi:
>
od:
>
return(R):
> end proc:
> minimo := L -> minMax(min,L):
> maximo := L -> minMax(max,L):
Como já sabemos, a combinação de quatro números de 1 a 3 que conduz a um menor número de
valores possı́veis é a combinação [1, 1, 1, 1]: apenas é possı́vel, por intermédio das quatro operações
aritméticas +, −,× e ÷ obter 11 valores diferentes:
> minimo(NV15);
[1111, 11]
Os valores possı́veis de serem obtidos são:
> all(lista(1111),[‘+‘,‘-‘,‘*‘,‘/‘]);
1 1 1 3
−2, −1, 0, 1, 2, 3, 4, , , − ,
2 3 2 2
Em particular não é possı́vel jogar o Jogo do 24 com a configuração [1, 1, 1, 1].
A combinação de quatro números de 1 a 3 que conduz a um maior número de valores possı́veis é,
como vimos, a combinação [1, 2, 3, 3]: é possı́vel, por intermédio das quatro operações aritméticas
+, −,× e ÷, obter 139 valores diferentes:
6
> maximo(NV15);
[1233, 139]
Dos 139 valores possı́veis, apenas 40 são inteiros:
> select(i->type(i,integer),all(lista(1233),[‘+‘,‘-‘,‘*‘,‘/‘]));
{−17, −16, −15, −14, −12, −11, −10, −9, −8, −7, −6, −5, −4, −3, −2, −1, 0, 1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 24, 27}
Vemos que um dos valores possı́veis de ser obtido é o “nosso” 24.
Vamos agora considerar todas as 495 combinações de quatro números de 1 a 9.
> NV495 := NumVal(P(4,9)):
A combinação menos profı́cua contı́nua a ser o quaterno [1, 1, 1, 1], com as seus 11 valores possı́veis
de serem obtidos:
> minimo(NV495);
[1111, 11]
A combinação que conduz a mais possibilidades é a [5, 6, 8, 9]
> maximo(NV495);
[5689, 922]
Dos 922 valores possı́veis de serem obtidos a partir da combinação [5,6,8,9], 212 são inteiros:
> nops(select(i->type(i,integer),all(lista(5689),[‘+‘,‘-‘,‘*‘,‘/‘])));
212
Um deles é o 24:
> member(24,all(lista(5689),[‘+‘,‘-‘,‘*‘,‘/‘]));
true
Já a partir da combinação [1,1,1,1], como vimos, não é possı́vel obter 24.
> member(24,all(lista(1111),[‘+‘,‘-‘,‘*‘,‘/‘]));
f alse
Vamos agora tentar dar resposta à seguinte questão:
Para quais das 495 combinações de quatro números de um a nove é realmente
possı́vel obter 24?
Melhor ainda: quais as combinações de quatro números de um a nove para as quais não é possı́vel
obter v? O seguinte procedimento permite-nos obter as respostas desejadas.
> falham := proc(v)
>
local L495,q,R:
>
L495 := ordena(P(4,9)):
>
R := NULL:
>
for q in L495 do
>
if not(member(v,all(q,[‘+‘,‘-‘,‘*‘,‘/‘]))) then
>
# printf("%a\n",q):
>
R := R,q:
>
fi:
>
od:
>
return(seq(num(q),q=[R])):
> end proc:
7
Descobrimos que o Jogo 24 admite solução para 404 dos 495 possı́veis quaternos. Os 91 quaternos
que não admitem solução são (logo à cabeça aparece a caso [1, 1, 1, 1] que já conhecı́amos):
> F24 := falham(24);
F 24 := 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1119, 1122, 1123, 1124, 1125, 1133, 1159, 1167,
1177, 1178, 1179, 1189, 1199, 1222, 1223, 1299, 1355, 1499, 1557, 1558, 1577, 1667, 1677, 1678,
1777, 1778, 1899, 1999, 2222, 2226, 2279, 2299, 2334, 2555, 2556, 2599, 2677, 2777, 2779, 2799,
2999, 3358, 3467, 3488, 3555, 3577, 4459, 4466, 4467, 4499, 4779, 4999, 5557, 5558, 5569, 5579,
5777, 5778, 5799, 5899, 5999, 6667, 6677, 6678, 6699, 6777, 6778, 6779, 6788, 6999, 7777, 7778,
7779, 7788, 7789, 7799, 7888, 7899, 7999, 8888, 8889, 8899, 8999, 9999
> nops([F24]);
91
Das 91 configurações para as quais não existe solução para o Jogo 24, apenas duas possuem os
quatro algarismos diferentes:
> select(i->nops({op(lista(i))})=4,[F24]);
[1678, 3467]
Vamos guardar, de modo ordenado, numa lista de nome PC, todas as 404 Possı́veis Configurações
para o Jogo do 24.
> PC := [seq(lista(j),j=sort(tira([F24],[seq(num(i),i=P(4,9))])))]:
> nops(PC);
404
A função tau(n), disponı́vel no Maple por intermédio do package de teoria de números numtheory,
devolve o número de divisores positivos de n.
> with(numtheory):
> tau(24);
8
Se quisermos saber quais são os 8 divisores positivos de 24, podemos recorrer à função Maple
divisors.
> divisors(24);
{1, 2, 3, 4, 6, 8, 12, 24}
O número 24 não foi escolhido, com toda a certeza, ao acaso por Robert Sun. Existirão outras
possibilidades interessantes? O número 24 é o menor inteiro positivo no intervalo [1, 35] a ter o
maior número de divisores.
> seq(tau(i),i=1..36);
1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9
A quantidade de divisores não é, no entanto, o único ingrediente a ter em conta. O menor inteiro
positivo, de entre todos os inteiros positivos com menos de 3 dı́gitos, com o maior número de
divisores positivos é o 60 (tem 12 divisores positivos):
> LD := seq(tau(i),i=1..99):
> max(LD);
8
12
> member(12,[LD],’p’):
> p;
60
No entanto para o “Jogo do 60” existem muito menos configurações admissı́veis do que para o
Jogo do 24: o número de configurações admissı́veis é de 495 − 219 = 276, contra as 404 possı́veis
no Jogo 24.
> F60 := falham(60):
> nops([F60]);
219
Um jogo interessante, que vou propor como alternativa a próxima vez que for desafiado por
pequerruchos bem treinados no Jogo do 24, é o Jogo do 6 ;-) O Jogo do 6 admite solução para
469 dos 495 possı́veis quaternos: mais 65 hipóteses de jogo do que no conhecido Jogo do 24. Os
26 quaternos para os quais não existe solução são:
> F6 := falham(6);
F 6 := 1111, 1179, 1188, 1189, 1199, 1559, 1669, 1999, 3588, 3667, 4499, 4599, 4667, 4778, 5599, 5668,
5669, 5788, 6789, 7779, 7788, 7799, 7899, 8889, 8899, 9999
> nops([F6]);
26
Notamos, no entanto, que dos 26 quaternos que não admitem solução para o Jogo do 6, exactamente
metade deles admite solução para o Jogo do 24. As 13 combinações que não admitem solução para
o Jogo do 6, mas admitem solução para o Jogo do 24, são:
> tira([F24],[F6]);
[1188, 1559, 1669, 3588, 3667, 4599, 4667, 4778, 5599, 5668, 5669, 5788, 6789]
Vejamos mais alguns valores além do 6 que conduzem a jogos com um número de configurações
admissı́veis maior que no Jogo 24.
> F8 := falham(8):
> nops([F8]);
40
> F12 := falham(12):
> nops([F12]);
51
> F18 := falham(18):
> nops([F18]);
90
Os jogos do 8, do 12 e do 18 são, por conseguinte, também jogos interessantes a considerar.
O 30 tem o mesmo número de divisores que 24 (ambos têm 8 divisores positivos), enquanto 36
é o menor natural com um número de divisores superior ao de 24 (tem, como vimos, 9 divisores
positivos). O facto de estarmos a considerar apenas configurações formadas por números de um a
nove, faz com que estes casos sejam menos interessantes (o número de configurações admissı́veis é
menor, em ambos os casos, do que no Jogo do 24):
9
> F30 := falham(30):
> nops([F30]);
158
> F36 := falham(36):
> nops([F36]);
120
O nosso objectivo será agora o de definir em Maple a função jogo24 que, dados 4 números,
nos devolva todas as soluções do Jogo 24 para essa combinação. Vê-se facilmente que muitas
expressões associadas a uma dada combinação correspondem, na verdade, ao mesmo método de
solução. Vejamos, a tı́tulo ilustrativo, o exemplo dado no inı́cio deste trabalho: [1, 3, 4, 8]. O
programa disponibilizado em www.wxs.nl/~edejong/24-game dá-nos 12 soluções! A saber:
24-Game Oplossingen
1348 : ((1+3)*4)+8 =
1348 : ((1+8)-3)*4 =
1348 : ((1-3)+8)*4 =
1348 : ((3+1)*4)+8 =
1348 : ((8+1)-3)*4 =
1348 : ((8-3)+1)*4 =
1348 : (4+8)*(3-1) =
1348 : (8+4)*(3-1) =
1348 : 4*(1-(3-8)) =
1348 : 4*(8-(3-1)) =
1348 : 8+(4*(1+3)) =
1348 : 8+(4*(3+1)) =
- www.wxs.nl/~edejong/24-game
24
24
24
24
24
24
24
24
24
24
24
24
Muitas delas são repetidas... Para a combinação [1, 3, 4, 8] apenas existem, na verdade, como indicado na Secção 2, quatro soluções verdadeiramente distintas. O programa “24-Game Oplossingen”
parece dar muitas soluções, mas na verdade não as descobre todas! Apenas indica 3 das 4 possı́veis
– podemos agrupar as 12 soluções acima em três grupos, de tal modo que as fórmulas associadas
ao primeiro grupo são todas elas equivalentes à expressão x4+x3*(x1+x2); as do segundo grupo a
x3*(x1+x4-x2); e as do último grupo a (x3+x4)*(x2-x1); com x1=1, x2=3, x3=4, x4=8:
((1+3)*4)+8 = ((3+1)*4)+8 = 8+(4*(1+3)) = 8+(4*(3+1))
((1+8)-3)*4 = ((1-3)+8)*4 = ((8+1)-3)*4 = ((8-3)+1)*4 = 4*(1-(3-8)) = 4*(8-(3-1))
(4+8)*(3-1) = (8+4)*(3-1)
O “24-Game Oplossingen” deixa de fora a solução x4 /(x3 /x2 − x1 ) = 8/(4/3 − 1). Poderı́amos
pensar que este programa apenas considera soluções que envolvam inteiros. Isso não é, no entanto,
verdade, como rapidamente se confirma, por exemplo, com a combinação [1, 4, 5, 6]:
24-Game Oplossingen - www.wxs.nl/~edejong/24-game
1456 : 4/(1-(5/6)) = 24
Também aqui existe uma solução que não é descoberta pelo “24-Game Oplossingen”: 6/((5/4)-1).
Nós estamos interessados em obter, apenas, as soluções estruturalmente diferentes. Como
explicado por Xu X.J. em http://eppe.tamu.edu/~xuxj/prog/download/24game.htm, eliminar
os casos duplicados não é uma tarefa fácil. Xu X.J. desenvolveu, no ano 2000, um programa para
o Jogo do 24, disponibilizando o seu código fonte em C e o respectivo executável, que faz alguma
eliminação, usando para isso uma representação das expressões em árvore (vide [1, Cap. 5]). A
eliminação não é, no entanto, completa e o autor apresenta, inclusive, alguns exemplos em que o
seu método de eliminação não funciona bem. Para a combinação [1, 3, 4, 8] este programa dá-nos
8 soluções:
10
Please input 4 integer numbers: 1 3 4 8
((1+3)*4)+8
((1-3)+8)*4
(1-(3-8))*4
((1+8)-3)*4
(1+(8-3))*4
(3-1)*(4+8)
4*(8-(3-1))
8/((4/3)-1)
total 8 solutions
Nós só estamos interessados em obter as 4 soluções verdadeiramente diferentes (que provêm de
expressões matemáticas não equivalentes):
(4+8)*(3-1)
4*(1+8-3)
8+4*(1+3)
8/(4/3-1)
O Maple, com as suas capacidades simbólicas, permite-nos verificar facilmente a igualdade de
expressões matemáticas que, sendo equivalentes, estão escritas de forma diferente, permitindo-nos
abordar o problema de uma maneira alternativa, na nossa opinião mais simples, elegante e com
algumas vantagens.
A nossa definição em Maple do jogo24 é feita de modo incremental. Começamos por introduzir
primeiro algumas funções auxiliares. O modus operandi destas funções auxiliares é explicado por
intermédio de alguns exemplos.
> afecta := (LN,LX) -> {seq(LX[i]=LN[i],i=1..nops(LN))}:
> afecta([1,2,3],[x1,x2,x3]);
{x1 = 1, x2 = 2, x3 = 3}
> afecta([4,4,7,8],[x1,x1,x2,x3]);
{x1 = 4, x2 = 7, x3 = 8}
> divisaoZero := proc(e,a)
>
local d, D, flag:
>
flag := false:
>
D := [seq(denom(j),j=select(i->denom(i)<>1,[op(e)]))];
>
for d in D while not flag do
>
if simplify(subs(a,d) = 0) then
>
flag := true
>
fi:
>
od:
>
if not(flag) and whattype(e) = ‘^‘
>
and subs(a,op(2,e)) < 0
>
and subs(a,op(1,e)) = 0 then
>
flag := true:
>
fi:
>
return(flag);
> end proc:
> divisaoZero(x1*x2/x3,{x1=1,x2=2,x3=3});
f alse
> divisaoZero(x1/(x2-x3),{x1=1,x2=2,x3=2});
11
true
> divisaoZero((x1-x2)^(-1),{x1=2,x2=2});
true
> variaveis := proc(LN)
>
local i, j, p,LX:
>
LX := []:
>
j := 0:
>
for i to nops(LN) do
>
if member(LN[i],LN[1..i-1],’p’) then
>
LX := [op(LX), LX[p]]:
>
else
>
j := j + 1:
>
LX := [op(LX), x||j]:
>
fi:
>
od:
>
return(LX);
> end proc:
> variaveis([1,4,6,9]);
[x1, x2, x3, x4]
> variaveis([1,2,1,4]);
[x1, x2, x1, x3]
> variaveis([8,8,4,4]);
[x1, x1, x2, x2]
Com a ajuda das funções afecta, divisaoZero e variaveis, que acabámos de definir, estamos
agora em condições de implementar o tão almejado jogo24.
> jogo := proc(LN,LO,v)
>
local LX, CE, e, a, i:
>
LX := variaveis(LN);
>
CE := todos(f2(LX,LO),LO);
>
a := afecta(LN,LX);
>
i := 0;
>
printf("-------------\n");
>
printf("%a = %a\n",LX,LN);
>
for e in CE do
>
if not(divisaoZero(e,a)) and subs(a,e) = v then
>
i := i + 1:
>
printf("Solucao %a: %a\n",i,e);
>
fi:
>
od:
> end proc:
> jogo24 := L -> jogo(L,[‘+‘,‘-‘,‘*‘,‘/‘],24):
Para obtermos todas as soluções para todas as possı́veis configurações do Jogo 24, basta agora
executar o seguinte comando:
> for c in PC do jogo24(c) od:
12
Não apresentamos o resultado, apenas porque ele ocupa várias (muitas!) páginas (são 404 as
configurações possı́veis e cada uma tem, em geral, mais do que uma solução). Mostramos aqui
apenas alguns exemplos. A combinação [1, 1, 2, 7] tem apenas uma solução.
> jogo24([1,1,2,7]);
------------[x1, x1, x2, x3] = [1, 1, 2, 7]
Solucao 1: (x1+x2)*(x1+x3)
O próximo exemplo mostra que a simplificação das expressões exige, por vezes, uma análise do
resultado da nossa parte:
> jogo24([1,1,3,8]);
------------[x1, x1, x2, x3] = [1, 1, 3, 8]
Solucao 1: x2*x3/x1^2
Solucao 2: x1^2*x2*x3
Solucao 3: x2*x3
A expressão x2*x3 resulta da simplificação de expressões como x1*x2*x3/x1, x2*x3+x1-x1,
x2*(x3+x1-x1), ou x3*(x2+x1-x1).
Podia dar muitos outros exemplos do Jogo 24, mas para que não digam que ando a treinar para
conseguir fazer boa figura entre os alunos do Liceu :-) quero avançar para outras questões. Vamos
definir em Maple uma função que nos permite obter o número de soluções distintas associadas a
uma dada configuração.
> ns := proc(LN,LO,v) # Numero Solucoes
>
local LX, CE, e, a, i:
>
LX := variaveis(LN);
>
CE := todos(f2(LX,LO),LO);
>
a := afecta(LN,LX);
>
i := 0;
>
for e in CE do
>
if not(divisaoZero(e,a)) and subs(a,e) = v then
>
i := i + 1:
>
fi:
>
od:
>
return(i);
> end proc:
> nsj24 := L -> ns(L,[‘+‘,‘-‘,‘*‘,‘/‘],24):
> nsj24([1,3,4,8]);
4
O objectivo é sermos capazes de descobrir uma configuração do Jogo 24 com exactamente um
dado número de soluções distintas.
> digitos := n -> seq(iquo(irem(n,10^i),10^(i-1)),i=1..length(n)):
> digitos(1223);
3, 2, 2, 1
13
> descobre := proc(ns) # ns = numero solucoes
>
local i, f:
>
f := false:
>
i := 1111:
>
while i <= 9999 and not(f) do
>
if (nsj24([digitos(i)]) = ns) then
>
f := true:
>
else
>
i := i + 1:
>
fi:
>
od:
>
return(sort([digitos(i)]));
> end proc:
A primeira configuração com apenas uma solução distinta é a [1, 1, 1, 8]:
> descobre(1);
[1, 1, 1, 8]
A única solução é (1+1+1)*8:
> jogo24([1, 1, 1, 8]);
------------[x1, x1, x1, x2] = [1, 1, 1, 8]
Solucao 1: 3*x1*x2
Notar que a expressão matemática (x1 +x1 +x1 )×x2 é equivalente a 3x1 x2 . A primeira configuração
com exactamente duas soluções distintas é a [1, 1, 2, 6]:
> descobre(2);
[1, 1, 2, 6]
com soluções 2*6*(1+1) e 6*(1+1+2). Com três soluções distintas temos a configuração [1, 1, 3, 8]
> descobre(3);
[1, 1, 3, 8]
cujas soluções foram já analisadas anteriormente. As combinações com mais soluções são a
[1, 2, 4, 8], com 14 soluções, e a [1, 7, 8, 9] com 15 (é capaz de descobrir essas soluções sem recorrer
ao nosso jogo24?):
> descobre(14);
[1, 2, 4, 8]
> descobre(15);
[1, 7, 8, 9]
Uma análise ao resultado do comando
> for c in PC do jogo24(c) od:
que devolve todas as soluções para todas as possı́veis combinações do Jogo 24, revela que não
existem outras configurações com 14 e 15 soluções, e nenhuma com mais de 15 soluções.
14
5
Generalizações do Jogo 24
O seguinte paradoxo é bem conhecido entre os matemáticos e os cientistas da computação: é,
muitas vezes, mais fácil e natural demonstrar um resultado mais geral, ou resolver um problema
genérico, do que um seu caso particular... O nosso programa Maple jogo(LN,LO,v) recebe uma
Lista LN de “Números”; uma Lista LO de Operadores aritméticos binários; e o valor final v pretendido. Podemos, deste modo, resolver muitos outros problemas para além da colocação inicial do
problema do Jogo 24. Vejamos alguns. Podemos considerar (e respectivas combinações):
(i) números com mais que um dı́gito
> jogo([13,4,5,6],[‘+‘,‘-‘,‘*‘,‘/‘],24);
------------[x1, x2, x3, x4] = [13, 4, 5, 6]
Solucao 1: -(x2+x3-x1)*x4
(ii) números positivos e negativos
> jogo([13,-4,5,-6],[‘+‘,‘-‘,‘*‘,‘/‘],24);
------------[x1, x2, x3, x4] = [13, -4, 5, -6]
Solucao 1: (x3-x1-x2)*x4
(iii) números racionais
> jogo([9,2,5/8,4],[‘+‘,‘-‘,‘*‘,‘/‘],24);
------------[x1, x2, x3, x4] = [9, 2, 5/8, 4]
Solucao 1: (x1+x2+x4)/x3
(iv) outro conjunto de operadores aritméticos binários
> jogo([3,7,5,1],[‘+‘,‘-‘,‘*‘],24);
------------[x1, x2, x3, x4] = [3, 7, 5, 1]
Solucao 1: (x3+x4)*(x2-x1)
Solucao 2: -(x4-x1)*(x2+x3)
> jogo([3,7,5,1],[‘+‘,‘-‘,‘*‘,‘/‘],24);
------------[x1, x2, x3, x4] = [3, 7, 5, 1]
Solucao 1: -(x4-x1)*(x2+x3)
Solucao 2: (x3+x4)*(x2-x1)
> jogo([3,7,5,1],[‘+‘,‘-‘,‘*‘,‘/‘,‘^‘],24);
------------[x1, x2, x3, x4] = [3, 7, 5, 1]
Solucao 1: (x3+x4)*(x2-x1)
Solucao 2: -(x4-x1)*(x2+x3)
Solucao 3: x1*(x4^x3+x2)
15
(v) configurações com mais ou menos que quatro números
> jogo([3,7,1],[‘+‘,‘*‘],24);
------------[x1, x2, x3] = [3, 7, 1]
Solucao 1: (x2+x3)*x1
> jogo([3,3,5,5,1],[‘+‘,‘*‘],24);
------------[x1, x1, x2, x2, x3] = [3, 3, 5, 5, 1]
Solucao 1: x1+x2+x3+x1*x2
(vi) outros valores que não 24 (inteiros ou não, positivos ou negativos):
> jogo([13,4,5,6],[‘+‘,‘-‘,‘*‘,‘/‘],20);
------------[x1, x2, x3, x4] = [13, 4, 5, 6]
Solucao 1: x1+x3+x4-x2
> jogo([13,4,5,6],[‘+‘,‘-‘,‘*‘,‘/‘],2/3);
------------[x1, x2, x3, x4] = [13, 4, 5, 6]
Solucao 1: -(x2+x3-x1)/x4
> jogo([13,4,5,6],[‘+‘,‘-‘,‘*‘,‘/‘],-12);
------------[x1, x2, x3, x4] = [13, 4, 5, 6]
Solucao 1: (x3-x1)*x4/x2
(vii) incógnitas
> jogo([2,2,2*a,-4*b],[‘+‘,‘-‘,‘*‘,‘/‘],2*(a+b));
------------[x1, x1, x2, x3] = [2, 2, 2*a, -4*b]
Solucao 1: -(x3-x1*x2)/x1
Outras variantes podem ser facilmente consideradas em Maple. Por exemplo, uma variante
muito conhecida entre os alunos do 2o ciclo são os “Cartões Mistério”. Trata-se do Jogo 24
introduzido no inı́cio do nosso estudo, mas em que apenas são dados 3 números de 1 algarismo.
O aluno deve então encontrar um quarto número entre 1 e 9, que está em falta, e depois formar
uma expressão matemática que lhe permita chegar a 24. O interessante é considerar vários cartões
mistério em simultâneo, e encontrar um único número de um algarismo que permita resolver o
Jogo 24 para todos os cartões mistério em jogo. No liceu consideram-se apenas dois, mas não
custa muito mais implementar uma solução genérica que permita n cartões mistério, n ≥ 1:
> junta := (L,N) -> sort([op(L),N]):
> junta([1,2,3],2);
[1, 2, 2, 3]
> juntaV := LL -> [seq(map(junta,LL,i),i=1..9)]:
> juntaV([[1,2],[3,4]]);
16
[[[1, 1, 2], [1, 3, 4]], [[1, 2, 2], [2, 3, 4]], [[1, 2, 3], [3, 3, 4]], [[1, 2, 4], [3, 4, 4]], [[1, 2, 5], [3, 4, 5]],
[[1, 2, 6], [3, 4, 6]], [[1, 2, 7], [3, 4, 7]], [[1, 2, 8], [3, 4, 8]], [[1, 2, 9], [3, 4, 9]]]
> confBoa := CM -> evalb(nops(select(L->member(L,PC),CM))=nops(CM)):
> confBoa([[1,1,1,1],[1,3,4,5]]);
f alse
> confBoa([[1,1,1,8],[1,3,4,5]]);
true
> confBoas := LL -> select(confBoa,juntaV(LL)):
> misterio := CM -> seq(seq(jogo24(L),L=LL),LL=confBoas(CM)):
Vejamos um exemplo com duas cartas mistério: [1, 1, 1] e [4, 5, 6]. Neste caso existe apenas uma
possibilidade: adicionar um 8.
> confBoas([[1,1,1],[4,5,6]]);
[[[1, 1, 1, 8], [4, 5, 6, 8]]]
> misterio([[1,1,1],[4,5,6]]);
------------[x1, x1, x1, x2] = [1, 1, 1, 8]
Solucao 1: 3*x1*x2
------------[x1, x2, x3, x4] = [4, 5, 6, 8]
Solucao 1: -(x3-x1-x2)*x4
No próximo exemplo são dadas 5 cartas mistério: [4, 4, 4], [4, 5, 6], [5, 5, 7], [2, 3, 4] e [1, 2, 1]. Existem 3 possibilidades: adicionar um 6, um 7 ou um 8.
> confBoas([[4,4,4],[4,5,6],[5,5,7],[2,3,4],[1,2,1]]);
[[[4, 4, 4, 6], [4, 5, 6, 6], [5, 5, 6, 7], [2, 3, 4, 6], [1, 1, 2, 6]],
[[4, 4, 4, 7], [4, 5, 6, 7], [5, 5, 7, 7], [2, 3, 4, 7], [1, 1, 2, 7]],
[[4, 4, 4, 8], [4, 5, 6, 8], [5, 5, 7, 8], [2, 3, 4, 8], [1, 1, 2, 8]]]
Ferramentas como o Maple são boas auxiliares neste tipo de investigações (vide [2]). Fico à
espera das vossas experiências e das vossas descobertas.
Agradecimentos
Agradeço à Professora Rosa Amélia Martins, Coordenadora da Licenciatura em Ensino de Matemática da Universidade de Aveiro, e responsável pela disciplina de Prática Pedagógica, o convite
que me endereçou para, em 29 de Março de 2004, proferir uma palestra aos Estagiários e Orientadores das Escolas e Universidade.
17
Referências
[1] Delfim F. M. Torres, Introdução à Programação em Lógica, Universidade de Aveiro, 2000
(ISBN 972–8021–93–3).
[2] Delfim F. M. Torres, Números Felizes e Sucessões Associadas: Digressões com o Maple, revista
Educação e Matemática da Associação de Professores de Matemática, N o 77, Março/Abril
2004.
[3] Delfim F. M. Torres, Notas da disciplina de Computadores no Ensino da Matemática
http://webct.ua.pt/public/cem1sem/index.html
http://webct.ua.pt/public/cem2sem/index.html
18