{"id":351,"date":"2019-07-20T12:22:29","date_gmt":"2019-07-20T15:22:29","guid":{"rendered":"https:\/\/www.blogs.unicamp.br\/zero\/?p=351"},"modified":"2023-08-24T17:01:04","modified_gmt":"2023-08-24T20:01:04","slug":"hidra-condicional2","status":"publish","type":"post","link":"https:\/\/www.blogs.unicamp.br\/zero\/351\/","title":{"rendered":"Hidra Condicional"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

(Traduzir)<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

A Hidra na Mitologia Grega era um monstro com corpo de drag\u00e3o e v\u00e1rias cabe\u00e7as de serpente que habitava um p\u00e2ntano perto do lago de Lerna. Em algumas vers\u00f5es da lenda, a Hidra tem uma cabe\u00e7a verdadeira que caso destru\u00edda, a Hidra morreria e outras falsas cabe\u00e7as, que quando destru\u00eddas gerariam duas novas cabe\u00e7as. Para a constru\u00e7\u00e3o do nosso problema, assumiremos esta vers\u00e3o como a verdadeira.<\/p>

Assim, suponha que exista um her\u00f3i cego, incans\u00e1vel e invulner\u00e1vel, capaz de atacar a Hidra por quanto tempo quiser. Mas por defini\u00e7\u00e3o (de acordo com a lenda), cada cabe\u00e7a falsa que \u00e9 cortada gera duas novas cabe\u00e7as falsas. Ent\u00e3o, cada vez que a cabe\u00e7a errada for cortada, sua chance de acertar a cabe\u00e7a certa ser\u00e1 menor.<\/p>

Para ilustrar este problema vamos supor que a Hidra comece com duas cabe\u00e7as (mas ela poderia come\u00e7ar com qualquer N cabe\u00e7as, sendo N maior ou igual a 2).<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Nosso her\u00f3i cego esta diante a Hidra de duas cabe\u00e7as. A chance de acertar a cabe\u00e7a verdadeira \u00e9 50% e a chance de acertar a cabe\u00e7a falsa \u00e9 50%.<\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Ele ataca uma cabe\u00e7a.<\/i><\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

A cabe\u00e7a \u00e9 arrancada.<\/i><\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Mas por azar, era a cabe\u00e7a falsa. Ent\u00e3o nascem duas novas cabe\u00e7as. Agora sua chance de acertar a cabe\u00e7a verdadeira \u00e9 aproximadamente 33% e a chance de acertar uma cabe\u00e7a falsa \u00e9 aproximadamente 67%.<\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Ele ataca uma cabe\u00e7a.<\/i><\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

A cabe\u00e7a \u00e9 arrancada.<\/i><\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Mas por azar, era a cabe\u00e7a falsa. Ent\u00e3o nascem duas novas cabe\u00e7as. Agora sua chance de acertar a cabe\u00e7a verdadeira \u00e9 25% e a chance de acertar uma cabe\u00e7a falsa \u00e9 75%.<\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Ele ataca uma cabe\u00e7a.<\/i><\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

A cabe\u00e7a \u00e9 arrancada.<\/i><\/p>

\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Mas por azar, era a cabe\u00e7a falsa. Ent\u00e3o nascem duas novas cabe\u00e7as. Agora sua chance de acertar a cabe\u00e7a verdadeira \u00e9 20% e a chance de acertar uma cabe\u00e7a falsa \u00e9 80%. Vamos parar com apenas 5 cabe\u00e7as, mas neste problema, aparentemente quanto mais o nosso her\u00f3i demora para matar a Hidra, mais improv\u00e1vel parece a chance dele acertar a cabe\u00e7a verdadeira (dado que o n\u00famero de cabe\u00e7as falsas aumenta). Voc\u00ea pode at\u00e9 pensar que mat\u00e1-la \u00e9 uma quest\u00e3o de sorte, mas infelizmente (para a Hidra) a probabilidade condicional nos diz outra coisa.<\/p>

Se observarmos a chance do nosso her\u00f3i derrotar a Hidra a cada novo golpe, esta probabilidade ser\u00e1 1\/(n\u00famero-total-de-cabe\u00e7as), assim por exemplo, uma Hidra com 100 cabe\u00e7as, a chance do her\u00f3i acertar a cabe\u00e7a verdadeira ser\u00e1 de 1%.<\/p>

Por outro lado (usando probabilidade condicional), vamos observar a chance da Hidra sobreviver a cada golpe. Pois no caso de uma Hidra que comece com duas cabe\u00e7as, ela somente chegar\u00e1 a ter 100 cabe\u00e7as, se o her\u00f3i acertar a cabe\u00e7a errada 98 vezes.<\/p>

Pois para a Hidra alcan\u00e7ar n+2 cabe\u00e7as, o her\u00f3i deve ter errado todos os primeiros n golpes.<\/p>

Analisando ent\u00e3o desde o primeiro dos erros do nosso her\u00f3i, a chance desta Hidra sobreviver ao primeiro golpe e alcan\u00e7ar 3 cabe\u00e7as \u00e9 de 50%.<\/p>

Contudo a chance desta Hidra sobreviver a dois golpes do her\u00f3i, ser\u00e1 a probabilidade dela sobreviver ao segundo golpe dado que ela sobreviveu ao primeiro golpe. Ou seja (50%).(67%), que d\u00e1 33%.<\/p>

Analogamente, a chance desta Hidra sobreviver a tr\u00eas golpes do her\u00f3i, ser\u00e1 a probabilidade dela sobreviver ao terceiro golpe dado que ela sobreviveu ao primeiro e ao segundo golpe. Ou seja (50%).(67%).(75%), que d\u00e1 25%.<\/p>

Sobreviver a quatro golpes: probabilidade de sobreviver ao quarto golpe dado que sobreviveu aos 3 primeiros golpes: (50%).(67%).(75%).(80%), que d\u00e1 20%.<\/p>

Seguiremos apenas com os resultados para os casos seguintes:<\/p>

Sobreviver a cinco golpes: 16%.<\/i><\/p>

Sobreviver a seis golpes: 14%.<\/i><\/p>

Sobreviver a sete golpes: 12%.<\/i><\/p>

Sobreviver a oito golpes: 11%.<\/i><\/p>

Sobreviver a nove golpes: 10%.<\/i><\/p>

Sobreviver a dez golpes: 9%.<\/i><\/p>

\u2026<\/p>

Sobreviver a 98 golpes: 1%.<\/i><\/p>

\u2026<\/p>

Sobreviver a 998 golpes: 0,1%.<\/i><\/p>

Assim, a chance de uma Hidra nestas condi\u00e7\u00f5es chegar a 100 cabe\u00e7as (sobreviver a 98 golpes) \u00e9 de aproximadamente 1%. A chance desta mesma Hidra chegar a 1000 cabe\u00e7as \u00e9 de aproximadamente 0,1%. Dessa forma, podemos perceber que a medida que o n\u00famero de ataques aumenta, a chance da Hidra continuar viva diminui apesar do n\u00famero de cabe\u00e7as aumentar.<\/p>

Apesar das chances da Hidra sobreviver sempre aumentarem (do ponto de vista dos ataques de her\u00f3i), a probabilidade de atingir um n\u00famero muito grande de cabe\u00e7as vai se aproximando cada vez mais de 0%. Ou seja, certamente (mais cedo ou mais tarde ) o her\u00f3i acertar\u00e1 um golpe na cabe\u00e7a verdadeira e a luta terminar\u00e1.<\/p>

Voc\u00ea pode estar pensando que isto s\u00f3 funcionou pois a nossa Hidra era muito fraquinha, se fosse uma \u201cSuper-Hidra\u201d as coisas poderiam ser diferentes. Vamos supor ent\u00e3o que nosso her\u00f3i esteja enfrentando uma \u201cSuper-Hidra\u201d com N cabe\u00e7as e a cada cabe\u00e7a falsa destru\u00edda, surjam M cabe\u00e7as. Sendo N e M n\u00fameros Naturais quaisquer.<\/p>

Da mesma forma, sua chance de sobreviver aos primeiros n ataques de nosso her\u00f3i ser\u00e1:<\/p>

(N-1\/N).(N-2+M\/N-1+M).(N-3+2M\/N-2+2M).(N-4+3M\/N-3+3M) \u2026 (N-n+(n-1)M\/N-(n-1)+(n-1).M).<\/i><\/p>

Agora fica dif\u00edcil perceber para um valor qualquer de M e N, que conforme o n\u00famero de ataques (n) aumenta, a chance de sobreviver da \u201cSuper-Hidra\u201d vai diminuir. Mas observe que o denominador \u00e9 sempre maior que o quociente, ent\u00e3o para cada ataque do her\u00f3i, a chance da \u201cSuper-Hidra\u201d sobreviver \u00e9 menor que 1. Ent\u00e3o quando multiplicamos todos esses n\u00fameros menores que 1, este produto estar\u00e1 sempre em redu\u00e7\u00e3o, ent\u00e3o a chance de a \u201cSuper-Hidra\u201d sobreviver a cada novo ataque, sempre diminuir\u00e1, n\u00e3o importa o tamanho de M e N.<\/p>

Por exemplo, com M = 100 e N = 100.<\/p>

Ap\u00f3s 10 ataques, a chance da \u201cSuper-Hidra\u201d continuar viva \u00e9 de 97%;<\/p>

Ap\u00f3s 100 ataques a chance da \u201cSuper-Hidra\u201d continuar viva \u00e9 de 95%.<\/p>

Esta chance esta diminuindo lentamente, mas para um n suficientemente grande, a chance da \u201cSuper-Hidra\u201d continuar viva ser\u00e1 muito pr\u00f3ximo de 0%.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Voltar para p\u00e1gina principal<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Quem escreve os posts?<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Um her\u00f3i cego e invenc\u00edvel, contra uma Hidra de Lerna que cria cabe\u00e7as extras enquanto a verdadeira n\u00e3o \u00e9 cortada, quem vencer\u00e1?<\/p>\n","protected":false},"author":434,"featured_media":366,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"pgc_sgb_lightbox_settings":"","_vp_format_video_url":"","_vp_image_focal_point":[],"footnotes":""},"categories":[1208],"tags":[],"class_list":["post-351","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-v-2-ed-1"],"_links":{"self":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/351","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/users\/434"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/comments?post=351"}],"version-history":[{"count":20,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/351\/revisions"}],"predecessor-version":[{"id":5197,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/351\/revisions\/5197"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/media\/366"}],"wp:attachment":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/media?parent=351"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/categories?post=351"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/tags?post=351"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}