O Jogo do 24 – digressoes com o Maple

Delfim F. M. Torresdelfim@mat.ua.pt

Departamento de MatematicaUniversidade de Aveiro

3810-193 Aveiro, Portugalhttp://www.mat.ua.pt/delfim

1 A guisa de introducao

Ha tempos tomei conhecimento do “Jogo 24”. As regras sao simples: ganha quem primeiroconseguir obter o numero 24 usando todos os numeros dados, uma e uma so vez, e as quatrooperacoes +, −, ×, e ÷. O jogo 24 foi inventado por Robert Sun em 1988, com o objectivo demostrar que “a matematica pode ser poderosa, aliciante e, acima de tudo, divertida”. Parece--me que Robert Sun foi muito bem sucedido. Constatei que o desafio e extremamente popularentre estudantes do ensino basico e secundario. Nao vos vou contar a minha experiencia empormenor para nao ficar embaracado: os pequerruchos gostam tanto do jogo, praticam-no com talentusiasmo, que acabam por desenvolver um “calculo mental 24” verdadeiramente surpreendente.Joguei duas ou tres vezes e tive de desistir para nao fazer ma figura: os pequenos levavam-mesempre a melhor! Afastei-me e liguei o portatil para fazer um programa que jogasse por mime que, acima de tudo, satisfizesse a minha curiosidade. Decidi partilhar convosco as minhasexperiencias: o ano 2004 foi escolhido pela Associacao de Professores de Matematica como o anoda Matematica e Jogo e, quica, alguns de vos se sintam motivados a colocar novas questoes, afazer novas experiencias e a obter respostas novas...

2 O Jogo 24

Na sua versao mais simples sao dados quatro numeros inteiros de um a nove. A tarefa consisteem formar uma expressao matematica, com valor 24, usando os quatro numeros dados uma e umaso vez e qualquer conjunto de operadores aritmeticos +, −, ×, ÷ (e possivelmente parenteses).Por exemplo, dados os numeros 1, 3, 4 e 8 sao possıveis quatro expressoes nao equivalentes comresultado 24. Se introduzirmos a notacao x1 = 1, x2 = 3, x3 = 4, x4 = 8, as 4 expressoes-solucaosao:

• 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 numero de solucoes nao varia se trocarmos a ordem com que indicamos os numeros: ojogo [1, 3, 4, 8] e precisamente o mesmo que o jogo [8, 4, 3, 1] ou qualquer uma das suas permutacoes!

1

3 O Maple

O Maple faz parte de uma famılia de ambientes cientıficos apelidados de “Sistemas de ComputacaoAlgebrica” (Computer Algebra Systems nos paıses anglo-saxonicos). Trata-se de uma ferramentamatematica muito poderosa, que permite realizar uma mirıade de calculos simbolicos e numericos.E o laboratorio de “Matematica Experimental” que tenho adoptado na disciplina de Computadoresno Ensino da Matematica da licenciatura em Ensino de Matematica da Universidade de Aveiro.

Depois de se iniciar uma sessao Maple, o sistema oferece-nos uma “linha de comandos”:

>

O Maple encontra-se entao a espera de ordens... Seguem-se algumas das minhas experiencias. Oleitor interessado em compreender ao pormenor os comandos Maple utilizados, pode encontrartodo o material de estudo necessario em [3].

4 Breve analise do jogo e digressoes em Maple

Comecamos por relembrar um resultado basico de combinatoria.

Teorema 1. Se admitirmos elementos repetidos, ha(n+m−1

n

)combinacoes de n elementos esco-

lhidos de um conjunto de cardinalidade m.

Por exemplo, se considerarmos o conjunto dos numeros inteiros de um a tres (m = 3), existem15 combinacoes diferentes de quatro numeros (n = 4).

> with(combinat):> t := (n,m) -> binomial(n+m-1,n):> t(4,3);

15

E facil, usando o Maple, enumerar todas as combinacoes possıveis mencionadas no Teorema 1.Vamos definir em Maple a funcao P (n, m) que, dado n e m, devolve todas as possıveis combinacoes.

> 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 definicoes, e agora muito facil gerar as 495 diferentes combinacoes de quatro numeros(n = 4) de um a nove (m = 9):

> t(4,9);

495

> nops(P(4,9));

2

495

Para obtermos todas as solucoes possıveis para todas as possıveis configuracoes do Jogo 24 vamosformar, para cada uma das 495 combinacoes acima, todas as possıveis expressoes aritmeticas.

> 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],[‘+‘,‘-‘,‘*‘,‘/‘]);

t2 :=[[[x1 + x2], []], [[x1− x2], []], [[x2− x1], []], [[x1x2], []], [[

x1x2

], []], [[x2x1

], []]]

> 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]],

[[x1x3], [x2]], [[x2x3], [x1]], [[x1x2

], [x3]], [[x2x1

], [x3]], [[x1x3

], [x2]],

[[x3x1

], [x2]], [[x2x3

], [x1]], [[x3x2

], [x1]]]

> f2([x3+x4,x1+x2],[‘+‘,‘-‘,‘*‘,‘/‘]);

[[[x3 + x4 + x1 + x2], []], [[x3 + x4− x1− x2], []], [[x1 + x2− x3− x4], []],

[[(x3 + x4)(x1 + x2)], []], [[x3 + x4x1 + x2

], []], [[x1 + x2x3 + 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, x1x2, x1− x2, x2− x1,

x1x2

,x2x1

}Com 4 incognitas existem 1170 expressoes matematicas nao equivalentes (e possıvel formar maisexpressoes matematicas com os operadores aritmeticos +, −, ∗, /, mas essas expressoes sao equi-valentes a umas destas 1170):

> nops(all([x1,x2,x3,x4],[‘+‘,‘-‘,‘*‘,‘/‘]));

1170

Claro que se algumas das incognitas forem iguais, o numero de expressoes matematicas nao equi-valentes diminui. Se duas das incognitas forem iguais sao possıveis 609:

> nops(all([x1,x1,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));

609

Para certos valores concretos de x1 algumas das 609 possibilidades resultam equivalentes, e onumero total de possibilidades diminui, enquanto para outros nao:

> nops(all([1,1,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));

277

> nops(all([2,2,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));

541

4

> nops(all([3,3,x2,x3],[‘+‘,‘-‘,‘*‘,‘/‘]));

609

Ja vimos que e 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 funcao all permite-nos muito mais. Podemos obter respostas a perguntas como:(i) Quais os inteiros positivos possıveis de serem obtidos a partir dos numeros 1,3,4 e 8 porintermedio das operacoes aritmeticas +, −,× 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 nao positivos possıveis de serem obtidos a partir dos numeros 1,3,4 e 8 porintermedio das operacoes aritmeticas +, −,× 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 nao inteiros, diferentes, sao possıveis de serem obtidos a partirdos numeros 1,3,4 e 8 por intermedio das operacoes aritmeticas +, −,× e ÷?

> nops(select(i->type(i,fraction) and i > 0,all([1,3,4,8],[‘+‘,‘-‘,‘*‘,‘/‘])));

198

(iv) Quantos racionais negativos nao inteiros, diferentes, sao possıveis de serem obtidos a partirdos numeros 1,3,4 e 8 por intermedio das operacoes aritmeticas +, −,× e ÷?

> nops(select(i->type(i,fraction) and i < 0,all([1,3,4,8],[‘+‘,‘-‘,‘*‘,‘/‘])));

120

Ao todo e possıvel obterem-se 427 (= 62 + 47 + 198 + 120) valores diferentes a partir do quaterno[1,3,4,8] por intermedio das operacoes aritmeticas +, −,× e ÷:

> numValores := L -> nops(all(L,[‘+‘,‘-‘,‘*‘,‘/‘])):> numValores([1,3,4,8]);

427

Vamos definir uma funcao NumVal que nos permite associar a cada uma das diferentes com-binacoes, o numero de valores distintos possıveis de serem alcancados por intermedio das operacoesaritmeticas +, −,× e ÷. Antes disso introduzimos uma notacao mais compacta para as com-binacoes 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));

NV 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 combinacoes diferentesde quatro numeros de um a tres, a que conduz a um menor numero de valores possıveis deserem obtidos e a combinacao [1, 1, 1, 1] (11 valores possıveis de serem obtidos por intermedio dasoperacoes +, −, ×, e ÷); enquanto a combinacao que conduz ao maior numero de possibilidadese a [1, 2, 3, 3] (139 valores possıveis). Vamos definir em Maple as funcoes minimo e maximo que nospermitem determinar estas combinacoes (a mais esteril 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 ja sabemos, a combinacao de quatro numeros de 1 a 3 que conduz a um menor numero devalores possıveis e a combinacao [1, 1, 1, 1]: apenas e possıvel, por intermedio das quatro operacoesaritmeticas +, −,× e ÷ obter 11 valores diferentes:

> minimo(NV15);

[1111, 11]

Os valores possıveis de serem obtidos sao:

> all(lista(1111),[‘+‘,‘-‘,‘*‘,‘/‘]);{−2,−1, 0, 1, 2, 3, 4,

12,13,−1

2,32

}Em particular nao e possıvel jogar o Jogo do 24 com a configuracao [1, 1, 1, 1].

A combinacao de quatro numeros de 1 a 3 que conduz a um maior numero de valores possıveis e,como vimos, a combinacao [1, 2, 3, 3]: e possıvel, por intermedio das quatro operacoes aritmeticas+, −,× e ÷, obter 139 valores diferentes:

6

> maximo(NV15);

[1233, 139]

Dos 139 valores possıveis, apenas 40 sao 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 e o “nosso” 24.Vamos agora considerar todas as 495 combinacoes de quatro numeros de 1 a 9.

> NV495 := NumVal(P(4,9)):

A combinacao menos profıcua contınua a ser o quaterno [1, 1, 1, 1], com as seus 11 valores possıveisde serem obtidos:

> minimo(NV495);

[1111, 11]

A combinacao que conduz a mais possibilidades e a [5, 6, 8, 9]

> maximo(NV495);

[5689, 922]

Dos 922 valores possıveis de serem obtidos a partir da combinacao [5,6,8,9], 212 sao inteiros:

> nops(select(i->type(i,integer),all(lista(5689),[‘+‘,‘-‘,‘*‘,‘/‘])));

212

Um deles e o 24:

> member(24,all(lista(5689),[‘+‘,‘-‘,‘*‘,‘/‘]));

true

Ja a partir da combinacao [1,1,1,1], como vimos, nao e possıvel obter 24.

> member(24,all(lista(1111),[‘+‘,‘-‘,‘*‘,‘/‘]));

false

Vamos agora tentar dar resposta a seguinte questao:

Para quais das 495 combinacoes de quatro numeros de um a nove e realmentepossıvel obter 24?

Melhor ainda: quais as combinacoes de quatro numeros de um a nove para as quais nao e possıvelobter 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 solucao para 404 dos 495 possıveis quaternos. Os 91 quaternosque nao admitem solucao sao (logo a cabeca aparece a caso [1, 1, 1, 1] que ja conhecıamos):

> F24 := falham(24);

F24 := 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 configuracoes para as quais nao existe solucao para o Jogo 24, apenas duas possuem osquatro 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 Configuracoespara o Jogo do 24.

> PC := [seq(lista(j),j=sort(tira([F24],[seq(num(i),i=P(4,9))])))]:> nops(PC);

404

A funcao tau(n), disponıvel no Maple por intermedio do package de teoria de numeros numtheory,devolve o numero de divisores positivos de n.

> with(numtheory):> tau(24);

8

Se quisermos saber quais sao os 8 divisores positivos de 24, podemos recorrer a funcao Mapledivisors.

> divisors(24);

{1, 2, 3, 4, 6, 8, 12, 24}

O numero 24 nao foi escolhido, com toda a certeza, ao acaso por Robert Sun. Existirao outraspossibilidades interessantes? O numero 24 e o menor inteiro positivo no intervalo [1, 35] a ter omaior numero 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 nao e, no entanto, o unico ingrediente a ter em conta. O menor inteiropositivo, de entre todos os inteiros positivos com menos de 3 dıgitos, com o maior numero dedivisores positivos e 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 configuracoes admissıveis do que para oJogo do 24: o numero de configuracoes admissıveis e de 495− 219 = 276, contra as 404 possıveisno Jogo 24.

> F60 := falham(60):> nops([F60]);

219

Um jogo interessante, que vou propor como alternativa a proxima vez que for desafiado porpequerruchos bem treinados no Jogo do 24, e o Jogo do 6 ;-) O Jogo do 6 admite solucao para469 dos 495 possıveis quaternos: mais 65 hipoteses de jogo do que no conhecido Jogo do 24. Os26 quaternos para os quais nao existe solucao sao:

> F6 := falham(6);

F6 := 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 nao admitem solucao para o Jogo do 6, exactamentemetade deles admite solucao para o Jogo do 24. As 13 combinacoes que nao admitem solucao parao Jogo do 6, mas admitem solucao para o Jogo do 24, sao:

> tira([F24],[F6]);

[1188, 1559, 1669, 3588, 3667, 4599, 4667, 4778, 5599, 5668, 5669, 5788, 6789]

Vejamos mais alguns valores alem do 6 que conduzem a jogos com um numero de configuracoesadmissı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 sao, por conseguinte, tambem jogos interessantes a considerar.O 30 tem o mesmo numero de divisores que 24 (ambos tem 8 divisores positivos), enquanto 36

e o menor natural com um numero de divisores superior ao de 24 (tem, como vimos, 9 divisorespositivos). O facto de estarmos a considerar apenas configuracoes formadas por numeros de um anove, faz com que estes casos sejam menos interessantes (o numero de configuracoes admissıveis emenor, 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 sera agora o de definir em Maple a funcao jogo24 que, dados 4 numeros,nos devolva todas as solucoes do Jogo 24 para essa combinacao. Ve-se facilmente que muitasexpressoes associadas a uma dada combinacao correspondem, na verdade, ao mesmo metodo desolucao. Vejamos, a tıtulo ilustrativo, o exemplo dado no inıcio deste trabalho: [1, 3, 4, 8]. Oprograma disponibilizado em www.wxs.nl/~edejong/24-game da-nos 12 solucoes! A saber:

24-Game Oplossingen - www.wxs.nl/~edejong/24-game1348 : ((1+3)*4)+8 = 241348 : ((1+8)-3)*4 = 241348 : ((1-3)+8)*4 = 241348 : ((3+1)*4)+8 = 241348 : ((8+1)-3)*4 = 241348 : ((8-3)+1)*4 = 241348 : (4+8)*(3-1) = 241348 : (8+4)*(3-1) = 241348 : 4*(1-(3-8)) = 241348 : 4*(8-(3-1)) = 241348 : 8+(4*(1+3)) = 241348 : 8+(4*(3+1)) = 24

Muitas delas sao repetidas... Para a combinacao [1, 3, 4, 8] apenas existem, na verdade, como indi-cado na Seccao 2, quatro solucoes verdadeiramente distintas. O programa “24-Game Oplossingen”parece dar muitas solucoes, mas na verdade nao as descobre todas! Apenas indica 3 das 4 possıveis– podemos agrupar as 12 solucoes acima em tres grupos, de tal modo que as formulas associadasao primeiro grupo sao todas elas equivalentes a expressao x4+x3*(x1+x2); as do segundo grupo ax3*(x1+x4-x2); e as do ultimo 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 solucao x4/(x3/x2 − x1) = 8/(4/3 − 1). Poderıamospensar que este programa apenas considera solucoes que envolvam inteiros. Isso nao e, no entanto,verdade, como rapidamente se confirma, por exemplo, com a combinacao [1, 4, 5, 6]:

24-Game Oplossingen - www.wxs.nl/~edejong/24-game1456 : 4/(1-(5/6)) = 24

Tambem aqui existe uma solucao que nao e descoberta pelo “24-Game Oplossingen”: 6/((5/4)-1).Nos estamos interessados em obter, apenas, as solucoes estruturalmente diferentes. Como

explicado por Xu X.J. em http://eppe.tamu.edu/~xuxj/prog/download/24game.htm, eliminaros casos duplicados nao e uma tarefa facil. Xu X.J. desenvolveu, no ano 2000, um programa parao Jogo do 24, disponibilizando o seu codigo fonte em C e o respectivo executavel, que faz algumaeliminacao, usando para isso uma representacao das expressoes em arvore (vide [1, Cap. 5]). Aeliminacao nao e, no entanto, completa e o autor apresenta, inclusive, alguns exemplos em que oseu metodo de eliminacao nao funciona bem. Para a combinacao [1, 3, 4, 8] este programa da-nos8 solucoes:

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

Nos so estamos interessados em obter as 4 solucoes verdadeiramente diferentes (que provem deexpressoes matematicas nao equivalentes):

(4+8)*(3-1)4*(1+8-3)8+4*(1+3)8/(4/3-1)

O Maple, com as suas capacidades simbolicas, permite-nos verificar facilmente a igualdade deexpressoes matematicas que, sendo equivalentes, estao escritas de forma diferente, permitindo-nosabordar o problema de uma maneira alternativa, na nossa opiniao mais simples, elegante e comalgumas vantagens.

A nossa definicao em Maple do jogo24 e feita de modo incremental. Comecamos por introduzirprimeiro algumas funcoes auxiliares. O modus operandi destas funcoes auxiliares e explicado porintermedio 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});

false

> 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 funcoes afecta, divisaoZero e variaveis, que acabamos de definir, estamosagora em condicoes de implementar o tao 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 solucoes para todas as possıveis configuracoes do Jogo 24, basta agoraexecutar o seguinte comando:

> for c in PC do jogo24(c) od:

12

Nao apresentamos o resultado, apenas porque ele ocupa varias (muitas!) paginas (sao 404 asconfiguracoes possıveis e cada uma tem, em geral, mais do que uma solucao). Mostramos aquiapenas alguns exemplos. A combinacao [1, 1, 2, 7] tem apenas uma solucao.

> jogo24([1,1,2,7]);

-------------[x1, x1, x2, x3] = [1, 1, 2, 7]Solucao 1: (x1+x2)*(x1+x3)

O proximo exemplo mostra que a simplificacao das expressoes exige, por vezes, uma analise doresultado da nossa parte:

> jogo24([1,1,3,8]);

-------------[x1, x1, x2, x3] = [1, 1, 3, 8]Solucao 1: x2*x3/x1^2Solucao 2: x1^2*x2*x3Solucao 3: x2*x3

A expressao x2*x3 resulta da simplificacao de expressoes 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 nao digam que ando a treinar paraconseguir fazer boa figura entre os alunos do Liceu :-) quero avancar para outras questoes. Vamosdefinir em Maple uma funcao que nos permite obter o numero de solucoes distintas associadas auma dada configuracao.

> 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 e sermos capazes de descobrir uma configuracao do Jogo 24 com exactamente umdado numero de solucoes 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 configuracao com apenas uma solucao distinta e a [1, 1, 1, 8]:

> descobre(1);

[1, 1, 1, 8]

A unica solucao e (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 expressao matematica (x1+x1+x1)×x2 e equivalente a 3x1x2. A primeira configuracaocom exactamente duas solucoes distintas e a [1, 1, 2, 6]:

> descobre(2);

[1, 1, 2, 6]

com solucoes 2*6*(1+1) e 6*(1+1+2). Com tres solucoes distintas temos a configuracao [1, 1, 3, 8]

> descobre(3);

[1, 1, 3, 8]

cujas solucoes foram ja analisadas anteriormente. As combinacoes com mais solucoes sao a[1, 2, 4, 8], com 14 solucoes, e a [1, 7, 8, 9] com 15 (e capaz de descobrir essas solucoes sem recorrerao nosso jogo24?):

> descobre(14);

[1, 2, 4, 8]

> descobre(15);

[1, 7, 8, 9]

Uma analise ao resultado do comando

> for c in PC do jogo24(c) od:

que devolve todas as solucoes para todas as possıveis combinacoes do Jogo 24, revela que naoexistem outras configuracoes com 14 e 15 solucoes, e nenhuma com mais de 15 solucoes.

14

5 Generalizacoes do Jogo 24

O seguinte paradoxo e bem conhecido entre os matematicos e os cientistas da computacao: e,muitas vezes, mais facil e natural demonstrar um resultado mais geral, ou resolver um problemagenerico, do que um seu caso particular... O nosso programa Maple jogo(LN,LO,v) recebe umaLista LN de “Numeros”; uma Lista LO de Operadores aritmeticos binarios; e o valor final v preten-dido. Podemos, deste modo, resolver muitos outros problemas para alem da colocacao inicial doproblema do Jogo 24. Vejamos alguns. Podemos considerar (e respectivas combinacoes):

(i) numeros 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) numeros positivos e negativos

> jogo([13,-4,5,-6],[‘+‘,‘-‘,‘*‘,‘/‘],24);

-------------[x1, x2, x3, x4] = [13, -4, 5, -6]Solucao 1: (x3-x1-x2)*x4

(iii) numeros 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 aritmeticos binarios

> 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) configuracoes com mais ou menos que quatro numeros

> 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 nao 24 (inteiros ou nao, 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) incognitas

> 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 variantemuito conhecida entre os alunos do 2o ciclo sao os “Cartoes Misterio”. Trata-se do Jogo 24introduzido no inıcio do nosso estudo, mas em que apenas sao dados 3 numeros de 1 algarismo.O aluno deve entao encontrar um quarto numero entre 1 e 9, que esta em falta, e depois formaruma expressao matematica que lhe permita chegar a 24. O interessante e considerar varios cartoesmisterio em simultaneo, e encontrar um unico numero de um algarismo que permita resolver oJogo 24 para todos os cartoes misterio em jogo. No liceu consideram-se apenas dois, mas naocusta muito mais implementar uma solucao generica que permita n cartoes misterio, 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]]);

false

> 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 misterio: [1, 1, 1] e [4, 5, 6]. Neste caso existe apenas umapossibilidade: 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 proximo exemplo sao dadas 5 cartas misterio: [4, 4, 4], [4, 5, 6], [5, 5, 7], [2, 3, 4] e [1, 2, 1]. Exis-tem 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 sao boas auxiliares neste tipo de investigacoes (vide [2]). Fico aespera das vossas experiencias e das vossas descobertas.

Agradecimentos

Agradeco a Professora Rosa Amelia Martins, Coordenadora da Licenciatura em Ensino de Ma-tematica da Universidade de Aveiro, e responsavel pela disciplina de Pratica Pedagogica, o conviteque me enderecou para, em 29 de Marco de 2004, proferir uma palestra aos Estagiarios e Orien-tadores das Escolas e Universidade.

17

Referencias

[1] Delfim F. M. Torres, Introducao a Programacao em Logica, Universidade de Aveiro, 2000(ISBN 972–8021–93–3).

[2] Delfim F. M. Torres, Numeros Felizes e Sucessoes Associadas: Digressoes com o Maple, revistaEducacao e Matematica da Associacao de Professores de Matematica, No 77, Marco/Abril2004.

[3] Delfim F. M. Torres, Notas da disciplina de Computadores no Ensino da Matematicahttp://webct.ua.pt/public/cem1sem/index.htmlhttp://webct.ua.pt/public/cem2sem/index.html

18