\n
Jogo dos Jarros \u2013 caso {8, 5, 3} <\/strong><\/p>\nNessa tradicional configura\u00e7\u00e3o, o jarro A<\/strong> de 8 L est\u00e1 cheio e os jarros B<\/strong> e C<\/strong> de 5 L e 3 L, respectivamente, est\u00e3o vazios. Nossa tarefa \u00e9 encontrar uma sequ\u00eancia de a\u00e7\u00f5es (ou jogadas) que nos permitam obter a quantidade de 4 L em algum dos jarros, a partir das regras anteriormente estabelecidas.<\/center><\/p>\n
\n
➤<\/span> Atividade 1:<\/strong><\/span> Quais possibilidades de jogadas voc\u00ea possui para a sua primeira a\u00e7\u00e3o? E para a segunda? <\/p>\n <\/p>\n
\n
\n
\nH\u00e1 duas possibilidades de jogadas para a primeira a\u00e7\u00e3o (encher o jarro B<\/strong> ou o jarro C<\/strong>):1)<\/strong> [8,0,0]\u2192[3,5,0]2)<\/strong> [8,0,0]\u2192[5,0,3]<\/li>\nPara cada uma delas, existem 3 possibilidades de jogadas para a segunda a\u00e7\u00e3o:1.1)<\/strong> [8,0,0]\u2192[3,5,0]\u2192[3,2,3]1.2)<\/strong> [8,0,0]\u2192[3,5,0]\u2192[0,5,3]1.3)<\/strong> [8,0,0]\u2192[3,5,0]\u2192[8,0,0] (Retorno ao estado inicial)2.1)<\/strong> [8,0,0]\u2192[5,0,3]\u2192[5,3,0]2.2)<\/strong> [8,0,0]\u2192[5,0,3]\u2192[0,5,3]2.3)<\/strong> [8,0,0]\u2192[5,0,3]\u2192[8,0,0] (Retorno ao estado inicial)<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n\n<\/div>\n
\n
\n
➤<\/span> Atividade 2:<\/strong><\/span> Quantas possibilidades de jogadas voc\u00ea possui para a sua terceira a\u00e7\u00e3o? E para a quarta? <\/p>\n <\/p>\n
\n
\n
\nPara a configura\u00e7\u00e3o final de 1.1<\/strong>, apresentada na atividade anterior, de um total de 6 jogadas poss\u00edveis dentro do jogo (como p\u00f4de ser observado nos jogos disponibilizados para o t\u00f3pico III<\/strong>) podemos realizar 4 delas (ou seja, todas aquelas que n\u00e3o envolvem encher o jarro C<\/strong>, que j\u00e1 est\u00e1 completamente cheio). <\/li>\nPara 1.2<\/strong> e 2.2<\/strong> temos 2 jogadas (usar os jarros B<\/strong> ou C<\/strong> para encher o jarro A<\/strong>).<\/li>\nPara 1.3<\/strong> e 2.3<\/strong>, temos 2 jogadas poss\u00edveis, pois retornamos \u00e0 configura\u00e7\u00e3o inicial. <\/li>\nPara 2.1<\/strong>, temos 3 jogadas poss\u00edveis.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n\n<\/div>\n
\n
\n
➤<\/span> Atividade 3:<\/strong><\/span> Voc\u00ea consegue perceber alguma rela\u00e7\u00e3o entre o total de jarros completamente vazios ou completamente cheios e a quantidade de jogadas poss\u00edveis que voc\u00ea pode fazer? <\/p>\n <\/p>\n
\n
\nJarros vazios ou completamente cheios s\u00e3o limitantes; no entanto, eles s\u00e3o inevit\u00e1veis, tendo em vista que ap\u00f3s toda jogada, pelas regras, teremos um jarro vazio e\/ou um jarro cheio. Perceba que o caso em que temos uma maior possibilidade de realizar diferentes jogadas \u00e9 quando temos um \u00fanico jarro cheio ou vazio (como no caso do estado final da primeira possibilidade de jogada representada na resolu\u00e7\u00e3o da Atividade 1). Para tais casos, temos 4 possibilidades de jogada (o que pode ser verificado pela pr\u00f3pria configura\u00e7\u00e3o anteriormente mencionada).
\n
Observa\u00e7\u00e3o:<\/em><\/strong> Essa rela\u00e7\u00e3o entre a quantidade de jarros cheios e vazios e o n\u00famero de a\u00e7\u00f5es poss\u00edveis \u00e9 o que nos permitir\u00e1, ao montarmos um grafo para resolver o jogo dos jarros, saber quantos s\u00e3o os caminhos poss\u00edveis para um \u00fanico v\u00e9rtice.\n<\/div>\n<\/div>\n<\/div>\n\n<\/div>\n
\n
\n
➤<\/span> Atividade 4:<\/strong><\/span> Para o caso {8, 5, 3}, o que garante que, ao longo do jogo, estejamos fazendo uma sequ\u00eancia de jogadas eficazes?<\/p>\n <\/p>\n
\n
\nO que garante o sucesso da resolu\u00e7\u00e3o \u00e9 n\u00e3o retornarmos a estados anteriores: se a \u00fanica a\u00e7\u00e3o que nos permite evoluir no jogo nos obriga a retornar a uma configura\u00e7\u00e3o ainda mais anterior do que a \u00faltima, ent\u00e3o a jogada n\u00e3o foi eficaz e devemos, portanto, seguir outro caminho.
\n
Observa\u00e7\u00e3o:<\/em><\/strong> Isso nos permitir\u00e1, ao analisarmos um grafo que represente o jogo em quest\u00e3o, sabermos qual ser\u00e1 a solu\u00e7\u00e3o \u00f3tima, ou seja, o caminho em que percorremos o menor n\u00famero de arestas poss\u00edvel para chegar a uma solu\u00e7\u00e3o.\n<\/div>\n<\/div>\n<\/div>\n\n<\/div>\n
\n
\n
➤<\/span> Atividade 5:<\/strong><\/span> Agora, vamos jogar o jogo de verdade! Conclu\u00eddas as atividades anteriores, pense nas possibilidades de resolu\u00e7\u00e3o de um jogo de 3 jarros de 8, 5 e 3 litros, estando o de 8 litros cheio. Quais s\u00e3o eficazes? H\u00e1 mais de uma possibilidade? Caso voc\u00ea n\u00e3o consiga resolv\u00ea-lo agora, sem problemas!<\/p>\n <\/p>\n
\n
\n
Sim, h\u00e1 mais de uma possibilidade. <\/strong> [8,0,0]\u2192[3,5,0]\u2192[3,2,3]\u2192[6,2,0]\u2192[6,0,2]\u2192[1,5,2]\u2192[1,4,3]<\/strong>Observa\u00e7\u00e3o:<\/strong><\/em> A an\u00e1lise do jogo a partir de um grafo (objeto matem\u00e1tico a ser definido mais adiante) nos permitir\u00e1 encontrar o caminho mais eficaz, realizando o menor n\u00famero poss\u00edvel de a\u00e7\u00f5es.\n<\/div>\n<\/div>\n<\/div>\n\n<\/div>\n
\n
\n
➤<\/span> Atividade 6:<\/strong><\/span> Voc\u00ea considera eficaz montar uma \u00e1rvore de possibilidades convencional, como a utilizada dentro da an\u00e1lise combinat\u00f3ria, para descobrir o total de jogos poss\u00edveis? Se a resposta for negativa, por que n\u00e3o?<\/p>\n <\/p>\n
\n
\nA \u00e1rvore de possibilidades pode n\u00e3o ser a melhor estrat\u00e9gia de representa\u00e7\u00e3o para o Jogo dos Jarros, justamente devido ao fato de cada jogada permitir um n\u00famero diferente de a\u00e7\u00f5es, de modo que n\u00e3o h\u00e1 regularidade nos ramos da \u00e1rvore. Al\u00e9m disso, a possibilidade de retornarmos a um estado anterior torna o uso desse artif\u00edcio matem\u00e1tico pouco eficaz.\n<\/div>\n<\/div>\n<\/div>\n
\n<\/div>\n
\n
\n
➤<\/span> Atividade 7:<\/strong><\/span> Monte um tri\u00e2ngulo equil\u00e1tero ABC<\/strong> de lado 8 e insira pontos em seus lados e em seu interior, com 1 unidade de medida de espa\u00e7amento entre eles, como na imagem abaixo. Cada ponto da imagem est\u00e1 associado a uma configura\u00e7\u00e3o poss\u00edvel ou imposs\u00edvel do Jogo dos Jarros<\/strong>, como voc\u00ea pode verificar em algumas ternas inseridas como exemplos na imagem. Esse padr\u00e3o de v\u00e9rtices \u00e9 chamado de sistema de coordenadas trilineares<\/strong>.A<\/strong> perde 1 litro (ternas (7,1,0) e (7,0,1)). De maneira similar, podemos associar a cada ponto do tri\u00e2ngulo uma configura\u00e7\u00e3o (poss\u00edvel ou imposs\u00edvel) do jogo. Al\u00e9m disso, perceba que a quantidade de \u00e1gua no sistema, dada pela soma das coordenadas de cada terna, est\u00e1 preservada.A<\/strong> tem a<\/strong> litros, o jarro B<\/strong> tem b<\/strong> litros e o jarro C<\/strong> tem c<\/strong> litros. <\/p>\n\n
\n
a)<\/strong> Quais configura\u00e7\u00f5es exibidas no tri\u00e2ngulo ABC s\u00e3o, na verdade, imposs\u00edveis, tendo em vista a capacidade de cada jarro? Apague os pontos associados a tais configura\u00e7\u00f5es.b)<\/strong> Apagados os pontos das configura\u00e7\u00f5es imposs\u00edveis, temos um novo pol\u00edgono com pontos em seus lados e em seu interior. Os pontos no interior do pol\u00edgono representam estados alcan\u00e7\u00e1veis, tendo em vista as regras do jogo? Por qu\u00ea?c)<\/strong> Agora, vamos passear por esse pol\u00edgono! Voc\u00ea consegue encontrar uma maneira de resolver o Jogo dos Jarros utilizando os pontos do pol\u00edgono constru\u00eddo no item a)<\/strong>? Qual o caminho com menor n\u00famero de a\u00e7\u00f5es?<\/p>\n\n
Para ajudar na obten\u00e7\u00e3o das coordenadas dos pontos definidos a partir do tri\u00e2ngulo ABC<\/strong>, utilize o esquema ilustrado na imagem a seguir.<\/p>\n
<\/p>\n
\n
\n
a)<\/strong> As configura\u00e7\u00f5es imposs\u00edveis s\u00e3o aquelas que, como o enunciado j\u00e1 diz, representam quantidades de \u00e1gua maiores do que os jarros conseguem comportar (Ex.: [0,4,4<\/strong>], [0, 8<\/strong>, 0]… etc.). A vers\u00e3o do tri\u00e2ngulo sem as configura\u00e7\u00f5es imposs\u00edveis est\u00e1 representada na imagem a seguir.<\/p>\n
b)<\/strong> N\u00e3o.\n
c)<\/strong> Voc\u00ea pode caminhar pelo pol\u00edgono constru\u00eddo, conectando seus pontos utilizando segmentos orientados. Partindo do v\u00e9rtice A, uma sequ\u00eancia de pontos e segmentos conectados simula uma sequ\u00eancia de a\u00e7\u00f5es realizadas no Jogo dos Jarros. A sequ\u00eancia mais curta pode ser interpretada como a resolu\u00e7\u00e3o do jogo com o menor n\u00famero de jogadas.\n<\/div>\n
\nO que voc\u00ea achou do diagrama constru\u00eddo na Atividade 7 para representar o Jogo dos Tr\u00eas Jarros?T\u00f3pico VI<\/strong> uma pequena apresenta\u00e7\u00e3o desse tipo de objeto.<\/p>\nVI – Um pouco sobre Grafos<\/p>\n
Informalmente, um grafo \u00e9 uma estrutura matem\u00e1tica que descreve conex\u00f5es entre objetos. \u00c9 comum representarmos um grafo geometricamente e, para isso, utilizamos pontos e linhas que os conectam:<\/p>\n
\n os pontos s\u00e3o chamados de v\u00e9rtices <\/strong>ou n\u00f3s<\/strong> e s\u00e3o utilizados na representa\u00e7\u00e3o dos objetos;<\/li>\n as linhas s\u00e3o chamadas de arestas<\/strong> ou arcos <\/strong>e s\u00e3o utilizadas para indicar a exist\u00eancia de conex\u00f5es entre os objetos.<\/li>\n<\/ul>\n
– v\u00e9rtices utilizados para representar pessoas e arestas para indicar quais pessoas s\u00e3o amigas;O conceito de grafo surge a partir da abstra\u00e7\u00e3o matem\u00e1tica de situa\u00e7\u00f5es desse tipo. Sua origem \u00e9 relativamente recente na hist\u00f3ria da Matem\u00e1tica (s\u00e9culo XVIII); entretanto, possui grande import\u00e2ncia n\u00e3o s\u00f3 como objeto de estudo das ci\u00eancias exatas, mas tamb\u00e9m como artif\u00edcio para a resolu\u00e7\u00e3o de problemas modernos.Leonhard Euler<\/strong> (1707-1783) de encontrar a solu\u00e7\u00e3o para o seguinte problema: \u00c9 poss\u00edvel realizar um trajeto pelas sete pontes de K\u00f6nigsberg<\/em> (atual Kaliningrado<\/em>, na R\u00fassia), sem cruzar nenhuma delas duas vezes?<\/strong><\/span><\/p>\n\n
As Sete Pontes de K\u00f6nigsberg<\/em><\/strong><\/p>\nA cidade de K\u00f6nigsberg<\/em> tinha sete pontes que conectavam as quatro \u00e1reas de terra dessa cidade cortada pelo Rio Pregel. <\/p>\n\nPontes de K\u00f6nigsberg<\/strong> <\/span>Wikip\u00e9dia<\/strong><\/a>. (Acesso em 02\/02\/2024.)<\/p>\nA possibilidade de atravessar cada uma das sete pontes uma \u00fanica vez tornou-se uma lenda popular da cidade, at\u00e9 que Euler comprovou a inviabilidade desse trajeto. Euler iniciou assumindo que cada ponte s\u00f3 poderia ser cruzada uma \u00fanica vez e que, cada vez que se entrasse numa \u00e1rea de terra, seria tamb\u00e9m necess\u00e1rio sair. Desse modo, cada \u00e1rea de terra precisava estar conectada por um n\u00famero par de pontes, com a poss\u00edvel exce\u00e7\u00e3o do in\u00edcio e do fim (caso eles fossem locais diferentes). Por\u00e9m, como pode ser observado nas imagens, nenhum dos pontos (ou v\u00e9rtices) do diagrama montado por Euler como representa\u00e7\u00e3o do problema \u00e9 o ponto final de um n\u00famero par de pontes.Teoria de Grafos<\/strong>.<\/p>\n\n
<\/center><\/p>\n
\n
Apesar da grande relev\u00e2ncia dos trabalhos de Euler ao estudo de grafos, \u00e9 apenas no s\u00e9culo XX que a Teoria de Grafos<\/strong> chega \u00e0 maturidade como um ramo da Matem\u00e1tica. O pr\u00f3prio termo grafo <\/strong>s\u00f3 foi cunhado em 1877, em um artigo de James Joseph Sylvester.<\/p>\n\n➤<\/span> H\u00e1 v\u00e1rios modos de definir o conceito de grafo. Aqui nesta breve apresenta\u00e7\u00e3o, adotaremos que um grafo<\/strong> \u00e9 um par [tex]G=(V , E)[\/tex] formado por um conjunto [tex]V[\/tex] de v\u00e9rtices <\/strong> e um conjunto [tex]E[\/tex] de arestas<\/strong>, sendo cada aresta um par n\u00e3o necessariamente ordenado de v\u00e9rtices (utiliza-se a letra E<\/em> pois arestas s\u00e3o traduzidas como \u201cedges<\/em>\u201d em Ingl\u00eas).<\/p>\nEm situa\u00e7\u00f5es particulares, \u00e9 necess\u00e1rio modelar conex\u00f5es de “um objeto para outro” e n\u00e3o simplesmente “entre objetos”, como no caso das Pontes. Nestes casos, arestas s\u00e3o definidas por pares ordenados de v\u00e9rtices e s\u00e3o representadas por setas (segmentos orientados). Esse tipo de grafo recebe a denomina\u00e7\u00e3o de grafo orientado ou direcionado<\/strong>.c) da Atividade 7<\/strong> \u00e9 um exemplo de grafo orientado<\/strong>. Esse grafo \u00e9 tamb\u00e9m um exemplo do que se denomina um grafo simples <\/strong> e conexo<\/strong>; veja as pr\u00f3ximas defini\u00e7\u00f5es:<\/p>\n\n Um grafo \u00e9 dito simples<\/strong>, se cada par de v\u00e9rtices corresponde a, no m\u00e1ximo, uma aresta e n\u00e3o existem arestas com v\u00e9rtices iguais (os chamados la\u00e7os<\/strong>). Um grafo \u00e9 dito conexo<\/strong>, quando qualquer par de v\u00e9rtices est\u00e1 conectado por uma sequ\u00eancia cont\u00ednua de arestas, chamada de passeio<\/strong>. <\/li>\n<\/ul>\n
\n
Observe que para completar o Jogo dos Jarros temos interesse em executar o menor n\u00famero de jogadas. O passeio do grafo que representa esse jogo \u00e9 denominado na Teoria de Grafos de caminho<\/strong>, isto \u00e9, um passeio por v\u00e9rtices todos distintos.K\u00f6nigsberg<\/em>, podemos observar que o gr\u00e1fico desse problema n\u00e3o \u00e9 orientado, \u00e9 conexo e n\u00e3o \u00e9 simples (note que temos duas arestas ligando os v\u00e9rtices A<\/strong> e B<\/strong>, assim como duas arestas ligando os v\u00e9rtices B<\/strong> e C<\/strong>.)<\/p>\n
![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/02\/fig_14_1.png\")
Imagem extra\u00edda do site wikiHow<\/strong><\/a>. (Acesso em 02\/02\/2024.)<\/p>\n<\/div>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/02\/fig_15.png\")
Objetivo:<\/strong>![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/02\/fig_17.png\")
![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_28.png\")
<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_29.png\")
<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_19.png\")
\n<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_23.png\")
<\/div>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_24.png\")
<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_30.png\")
<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_25.png\")
<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_31.png\")
![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/04\/fig_32.png\")
\n<\/div>\n<\/div>\n<\/div>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/05\/fig031.png\")
![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/05\/fig036.jpg\")
![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/05\/fig032.jpg\")
Imagem extra\u00edda da ![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/05\/fig037.png\")
<\/div>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/05\/fig034.png\")
![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/05\/fig038.jpg\")
<\/li>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/05\/fig039.png\")
<\/p>\n