{"id":127031,"date":"2019-04-26T13:47:03","date_gmt":"2019-04-26T16:47:03","guid":{"rendered":"http:\/\/clubes.obmep.org.br\/blog\/?page_id=127031"},"modified":"2023-05-23T05:37:58","modified_gmt":"2023-05-23T08:37:58","slug":"problemao-caminhos-distintos","status":"publish","type":"page","link":"https:\/\/clubes.obmep.org.br\/blog\/problemao-caminhos-distintos\/","title":{"rendered":".Problem\u00e3o: Caminhos distintos"},"content":{"rendered":"<p style=\"margin:30px\">\n<div class=\"g1n\" style=\"line-height:28px;\">\n<p class=\"tit\" style=\"line-height:20px;margin:10px\">Problema<br \/>\n<span style=\"font-size:12px;color:#800000\"> (Indicado a partir do 2\u00ba ano do E. M.)<\/span><\/p>\n<hr style=\"height:1px; width:100%;background-color:#800000; margin-top: 10px; margin-bottom: 20px;border: 0 none\"\/>\n<p>(<strong>IME<\/strong>&#8211; Adaptado) Em um jogo, quatro cidades, [tex]A[\/tex], [tex]B[\/tex], [tex]C[\/tex] e [tex]D[\/tex], s\u00e3o conectadas por estradas conforme mostra a figura abaixo. <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2019\/04\/Nova-Imagem.png\" \"style=\"border: none;\" alt=\"\" width=\"218\" height=\"219\" class=\"aligncenter size-full wp-image-125580\" srcset=\"https:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2019\/04\/Nova-Imagem.png 218w, https:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2019\/04\/Nova-Imagem-150x150.png 150w\" sizes=\"auto, (max-width: 218px) 100vw, 218px\" \/><\/p>\n<p><strong>Quantos percursos diferentes come\u00e7am e terminam na cidade [tex]A[\/tex], e possuem exatamente [tex]50\\;km[\/tex]?<\/strong><\/p>\n<p style=\"margin:20px\">\n<\/div>\n<p style=\"margin:30px\">\n<div class=\"cb36 g1n\" style=\"margin:30px;line-height:25px; width:75%; margin-left:auto; margin-right:auto; \"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2013\/01\/menino.jpg\" style=\"border:none\"  alt=\"explicador_p\" width=\"90\" height=\"108\" class=\"alignright size-full wp-image-1001\" \/> <\/p>\n<p class=\"c3 ti3\"> Ajuda<\/p>\n<p style=\"margin:20px\">\n<p><span style=\"font-size: 22px;\"><strong> &#9999;<\/strong> <\/span><strong>Princ\u00edpio Fundamental da Contagem, ou Princ\u00edpio Multiplicativo<\/strong>: Se<\/p>\n<ul>\n<li>uma decis\u00e3o <strong>D1<\/strong> puder ser tomada de [tex] m_1 [\/tex] maneiras distintas,<\/li>\n<li> uma decis\u00e3o <strong>D2<\/strong> puder ser tomada de [tex] m_2 [\/tex] maneiras distintas,<\/li>\n<li> [tex]\\cdots[\/tex]<\/li>\n<li> uma decis\u00e3o <strong>Dk<\/strong> puder ser tomada de [tex]m_k [\/tex] maneiras distintas,<\/li>\n<li>e todas essas decis\u00f5es forem independentes entre si (isto \u00e9, a escolha de uma n\u00e3o muda a quantidade de possibilidades para a escolha de outra),<\/li>\n<\/ul>\n<p> ent\u00e3o o n\u00famero total de maneiras de tomarmos sucessivamente essas [tex]k[\/tex] decis\u00f5es \u00e9 igual ao produto<br \/>\n[tex]\\qquad \\qquad \\boxed{m_1\\times m_2 \\times \\cdots \\times m_k}\\, .[\/tex]<br \/>\n<span style=\"font-size: 12px;\"> (Se voc\u00ea n\u00e3o se lembra desse  Princ\u00edpio, seria interessante dar uma passadinha <a href=\"http:\/\/clubes.obmep.org.br\/blog\/?p=22162\" target=\"_blank\" title=\"Sala de Estudo: Princ\u00edpio Fundamental da Contagem\"> <strong>nesta Sala de Estudo<\/strong><\/a>.)<\/span>\n<\/div>\n<div class=\"g1n\" style=\"line-height: 30px;\">\n<p class=\"tit\" style=\"line-height:30px;margin:10px\">Solu\u00e7\u00e3o <\/p>\n<hr style=\"height:1px; width:100%;background-color:#800000; margin-top: 10px; margin-bottom: 20px;border: 0 none\"\/>\n<p>Como devemos percorrer [tex]50\\;km[\/tex], necessariamente passaremos por [tex]6[\/tex] cidades. Obviamente, a primeira e a \u00faltima cidades devem ser a [tex]A[\/tex].<br \/>\nVamos dividir o problema em duas partes:<br \/>\n<strong>1\u00ba) Caminhos que n\u00e3o passam pela cidade [tex]A[\/tex]. <\/strong><br \/>\n  Devemos escolher [tex]6[\/tex] cidades para completar os [tex]50\\;km[\/tex].<\/p>\n<ul>\n<li>Para a primeira cidade s\u00f3 h\u00e1 uma possibilidade ([tex]A[\/tex]);<\/li>\n<li>Para a segunda cidade h\u00e1 tr\u00eas possibilidades ([tex]B[\/tex], [tex]C[\/tex] ou [tex]D[\/tex]);<\/li>\n<li>Para a terceira cidade h\u00e1 duas possibilidades (n\u00e3o pode ser a [tex]A[\/tex] nem a cidade na qual se estava anteriormente);<\/li>\n<li>Para a quarta cidade h\u00e1 duas possibilidades (n\u00e3o pode ser a [tex]A[\/tex] nem a cidade na qual se estava anteriormente);<\/li>\n<li>Para a quinta cidade h\u00e1 duas possibilidades (n\u00e3o pode ser a [tex]A[\/tex] nem a cidade na qual se estava anteriormente) e <\/li>\n<li>Para a sexta cidade s\u00f3 h\u00e1 uma possibilidade ([tex]A[\/tex]).<\/li>\n<\/ul>\n<p>Assim, pelo Princ\u00edpio Multiplicativo, existem<br \/>\n[tex]\\qquad \\qquad 1 \\times 3 \\times 2 \\times 2 \\times 2 \\times 1 = \\boxed{24 \\; caminhos}.[\/tex]<\/p>\n<p style=\"margin:20px\">\n<p><strong>2\u00ba) Caminhos que passam pela cidade [tex]A[\/tex].<\/strong><br \/>\nNote que a passagem pela cidade [tex]A[\/tex], antes de terminar os [tex]50\\;km[\/tex], s\u00f3 pode ocorrer uma vez e deve ser na terceira ou na quarta cidades. Vamos contar separadamente esses dois casos.<\/p>\n<ul>\n<li><strong>Passando por [tex]A[\/tex] na terceira cidade:<\/strong><\/li>\n<ul>\n<li>Para a primeira cidade s\u00f3 h\u00e1 uma possibilidade ([tex]A[\/tex]);<\/li>\n<li>Para a segunda cidade h\u00e1 tr\u00eas possibilidades ([tex]B[\/tex], [tex]C[\/tex] ou [tex]D[\/tex]);<\/li>\n<li>Para a terceira cidade h\u00e1 uma possibilidade ([tex]A[\/tex]);<\/li>\n<li>Para a quarta cidade h\u00e1 tr\u00eas possibilidades ([tex]B[\/tex], [tex]C[\/tex] ou [tex]D[\/tex]);<\/li>\n<li>Para a quinta cidade h\u00e1 duas possibilidades (n\u00e3o pode ser a [tex]A[\/tex] nem a cidade na qual se estava anteriormente) e <\/li>\n<li>Para a sexta cidade s\u00f3 h\u00e1 uma possibilidade ([tex]A[\/tex]).<\/li>\n<\/ul>\n<p>Pelo Princ\u00edpio Multiplicativo:<br \/>\n[tex]\\qquad \\qquad  1 \\times 3 \\times 1 \\times 3 \\times 2 \\times 1 = \\boxed{18 \\;  caminhos}.[\/tex]<\/p>\n<li><strong>Passando por [tex]A[\/tex] na quarta cidade:<\/strong><\/li>\n<ul>\n<li>Para a primeira cidade s\u00f3 h\u00e1 uma possibilidade ([tex]A[\/tex]);<\/li>\n<li>Para a segunda cidade h\u00e1 tr\u00eas possibilidades ([tex]B[\/tex], [tex]C[\/tex] ou [tex]D[\/tex]);<\/li>\n<li>Para a terceira cidade h\u00e1 duas possibilidades (n\u00e3o pode ser a [tex]A[\/tex] nem a cidade na qual se estava anteriormente);<\/li>\n<li>Para a quarta cidade h\u00e1 uma possibilidade ([tex]A[\/tex]);<\/li>\n<li>Para a quinta cidade h\u00e1 tr\u00eas possibilidades ([tex]B[\/tex], [tex]C[\/tex] ou [tex]D[\/tex]) e <\/li>\n<li>Para a sexta cidade s\u00f3 h\u00e1 uma possibilidade ([tex]A[\/tex]).<\/li>\n<\/ul>\n<p>Pelo Princ\u00edpio Multiplicativo:<br \/>\n[tex]\\qquad \\qquad 1 \\times 3 \\times 2 \\times 1 \\times 3 \\times 1 = \\boxed{18 \\; caminhos}.[\/tex]<\/ul>\n<p>Logo, temos no total [tex]\\fcolorbox{black}{#eee0e5}{$24+18+18=60$}[\/tex] caminhos que satisfazem as condi\u00e7\u00f5es do problema.<\/p>\n<hr style=\"height:1px; width:100%;background-color:#800000; margin-top: 10px; margin-bottom: 15px;border: 0 none\"\/>\n<p class=\"g2\" style=\"line-height:20px;\">Solu\u00e7\u00e3o elaborada pelos <strong>Moderadores do Blog<\/strong>.<\/p>\n<\/div>\n<p style=\"margin:10px\">\n","protected":false},"excerpt":{"rendered":"<p>Problema (Indicado a partir do 2\u00ba ano do E. M.) (IME&#8211; Adaptado) Em um jogo, quatro cidades, [tex]A[\/tex], [tex]B[\/tex], [tex]C[\/tex] e [tex]D[\/tex], s\u00e3o conectadas por estradas conforme mostra a figura abaixo.<\/p>\n","protected":false},"author":668,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"template-onecolumn.php","meta":{"footnotes":""},"class_list":["post-127031","page","type-page","status-publish","hentry","nodate","item-wrap"],"_links":{"self":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/127031","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/users\/668"}],"replies":[{"embeddable":true,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/comments?post=127031"}],"version-history":[{"count":11,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/127031\/revisions"}],"predecessor-version":[{"id":191575,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/127031\/revisions\/191575"}],"wp:attachment":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/media?parent=127031"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}