{"id":15998,"date":"2025-08-13T09:46:44","date_gmt":"2025-08-13T12:46:44","guid":{"rendered":"https:\/\/www3.unicentro.br\/petfisica\/?p=15998"},"modified":"2025-09-02T13:20:34","modified_gmt":"2025-09-02T16:20:34","slug":"o-problema-dos-100-prisioneiros","status":"publish","type":"post","link":"https:\/\/www3.unicentro.br\/petfisica\/2025\/08\/13\/o-problema-dos-100-prisioneiros\/","title":{"rendered":"O problema dos 100 prisioneiros"},"content":{"rendered":"

[vc_row][vc_column][vc_column_text]<\/span><\/span><\/span><\/p>\n

\u00a0 \u00a0Uma penitenci\u00e1ria tem 100 prisioneiros, e o diretor prop\u00f5e um jogo: em uma sala h\u00e1 cem caixas com tampas numeradas de 1 a 100. Dentro de cada caixa h\u00e1 um papel contendo o n\u00famero de identifica\u00e7\u00e3o de um dos prisioneiros, de 1 a 100, distribu\u00eddos aleatoriamente (sem repeti\u00e7\u00f5es). Um por vez, cada prisioneiro pode entrar na sala e abrir at\u00e9 50 caixas, tentando encontrar o papel com seu pr\u00f3prio n\u00famero. As caixas s\u00e3o fechadas ap\u00f3s cada tentativa, e os prisioneiros n\u00e3o podem se comunicar entre si durante o processo. Se todos encontrarem seus pr\u00f3prios n\u00fameros, todos ser\u00e3o libertados; se qualquer um deles falhar, todos permanecem presos.<\/span><\/p>\n

\u00a0 \u00a0Ao ler esse problema, a primeira impress\u00e3o \u00e9 de que a chance de liberdade dos prisioneiros n\u00e3o \u00e9 nada boa. Cada prisioneiro tem uma chance de 50% de encontrar seu pr\u00f3prio n\u00famero abrindo as caixas aleatoriamente, e a probabilidade de que todos encontrem seus respectivos n\u00fameros \u00e9, portanto, de (<\/span>1\/2)100<\/sup><\/span>. Um prisioneiro que fa\u00e7a essa conta desanimar\u00e1 ao perceber que tem uma chance em <\/span>10<\/span>30<\/span><\/sup>, que \u00e9 equivalente a ganhar na Mega-Sena quatro vezes seguidas!<\/span><\/span><\/p>\n

\u00a0 \u00a0Mas esse problema s\u00f3 \u00e9 digno da aten\u00e7\u00e3o do leitor porque existe uma estrat\u00e9gia que os prisioneiros podem combinar antes de iniciar o jogo, aumentando impressionantemente as suas chances de liberdade para mais de 30%. Caso ainda n\u00e3o conhe\u00e7a esse problema, esse \u00e9 o momento para interromper a leitura e pensar por algum tempo em qual \u00e9 essa estrat\u00e9gia aparentemente milagrosa.<\/span><\/p>\n

\u00a0 \u00a0Em vez de abrir 50 caixas aleat\u00f3rias, cada prisioneiro deve come\u00e7ar abrindo a caixa com o seu pr\u00f3prio n\u00famero \u2014 por exemplo, o prisioneiro 23 abre a caixa 23. Se nela estiver o n\u00famero 23, ele teve sorte e termina sua vez com sucesso. Caso contr\u00e1rio, ele encontra o n\u00famero de outro prisioneiro, digamos 41, e ent\u00e3o abre a caixa 41 na pr\u00f3xima tentativa. Ele repete esse processo, sempre abrindo a caixa cujo n\u00famero acabou de encontrar, at\u00e9 no m\u00e1ximo 50 tentativas.<\/span><\/p>\n

\u00a0 \u00a0Primeiramente, \u00e9 importante notar que, ao utilizar essa estrat\u00e9gia, cada caixa passa a fazer parte de um \u00fanico ciclo fechado. O ciclo mais curto poss\u00edvel cont\u00e9m apenas uma caixa, que aponta para o pr\u00f3prio n\u00famero, enquanto o mais longo envolve todas as 100 caixas. De maneira geral, um arranjo aleat\u00f3rio dos n\u00fameros nas caixas resulta em v\u00e1rios ciclos de diferentes tamanhos. Para que todos os prisioneiros encontrem seus pr\u00f3prios n\u00fameros seguindo a estrat\u00e9gia descrita, basta que nenhum desses ciclos tenha mais do que 50 caixas [1].<\/span><\/p>\n

\u00a0 \u00a0O problema ent\u00e3o se resume a calcular a probabilidade de que nenhum ciclo tenha comprimento maior do que 50. Os detalhes matem\u00e1ticos ser\u00e3o poupados aqui, mas esse c\u00e1lculo resulta na probabilidade de 31% de sucesso para os prisioneiros [1, 2].<\/span><\/p>\n

\u00a0 \u00a0Esse problema foi originalmente proposto em 2003 pelo cientista da computa\u00e7\u00e3o dinamarqu\u00eas Peter Bro Miltersen, com o objetivo de ilustrar conceitos da computa\u00e7\u00e3o, especialmente na \u00e1rea da complexidade de comunica\u00e7\u00e3o [3]. Mesmo conhecendo a estrat\u00e9gia vencedora, o resultado continua surpreendente. Trata-se de mais um exemplo em que a matem\u00e1tica desafia a intui\u00e7\u00e3o, revelando justamente o que a torna t\u00e3o fascinante.<\/span><\/p>\n

\u00a0<\/span>Autor:<\/b> Angelo Zanona Neto<\/span>
\n<\/span><\/span><\/p>\n

\n

Refer\u00eancias:<\/span><\/p>\n

[1] <\/span>Veritasium<\/b>. The Riddle That Seems Impossible Even If You Know The Answer. YouTube, 2022. https:\/\/youtu.be\/iSNsgj1OCLA?si=bdnhrfeModtRoLn3. Acessado em 11 de julho de 2025.<\/span><\/span><\/p>\n

[2] Duarte, P. M. N. R. D. <\/span>Problema dos Cem<\/b>. Dispon\u00edvel em: https:\/\/webpages.ciencias.ulisboa.pt\/~pmduarte\/Problems\/prision_2.pdf. Acessado em 11 de julho de 2025.<\/span><\/span><\/p>\n

[3] G\u00e1l, A., Miltersen, P. B. The Cell Probe Complexity of Succinct Data Structures. <\/span>BRICS Report Series<\/b>, 2003. Dispon\u00edvel em: https:\/\/www.brics.dk\/RS\/03\/44\/BRICS-RS-03-44.pdf. Acessado em 16 de julho de 2025.<\/span><\/span><\/p>\n

[4] (Imagem) Enigma: Salve-se quem puder. <\/span>Hypercubic: um hyperespa\u00e7o de ideias<\/b>, 2013. Dispon\u00edvel em: https:\/\/www.blogs.unicamp.br\/hypercubic\/2013\/04\/enigma-salve-se-quem-puder\/. Acessado em 11 de julho de 2025.<\/span><\/span><\/p>\n

[\/vc_column_text][\/vc_column][\/vc_row][vc_row][vc_column][vc_facebook][\/vc_column][\/vc_row]<\/span><\/p>\n<\/div>","protected":false},"excerpt":{"rendered":"

[vc_row][vc_column][vc_column_text] \u00a0 \u00a0Uma penitenci\u00e1ria tem 100 prisioneiros, e o diretor prop\u00f5e um jogo: em uma sala h\u00e1 cem caixas com tampas numeradas de 1 a 100. Dentro de cada caixa h\u00e1 um papel contendo o n\u00famero de identifica\u00e7\u00e3o de um dos prisioneiros, de 1 a 100, distribu\u00eddos aleatoriamente (sem repeti\u00e7\u00f5es). Um por vez, cada prisioneiro […]<\/p>\n","protected":false},"author":841,"featured_media":15999,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[4],"tags":[1451,1457,1110,965],"class_list":["post-15998","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-geral","tag-angelo-zanona-neto","tag-blog-2025","tag-curiosidade","tag-curiosidades"],"_links":{"self":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/posts\/15998","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/users\/841"}],"replies":[{"embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/comments?post=15998"}],"version-history":[{"count":1,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/posts\/15998\/revisions"}],"predecessor-version":[{"id":16045,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/posts\/15998\/revisions\/16045"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/media\/15999"}],"wp:attachment":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/media?parent=15998"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/categories?post=15998"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/tags?post=15998"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}