{"id":181,"date":"2011-05-10T15:35:31","date_gmt":"2011-05-10T14:35:31","guid":{"rendered":"http:\/\/xmau.com\/relax\/?p=181"},"modified":"2011-05-10T15:35:31","modified_gmt":"2011-05-10T14:35:31","slug":"sul-problema-8","status":"publish","type":"post","link":"https:\/\/xmau.com\/wp\/relax\/2011\/05\/10\/sul-problema-8\/","title":{"rendered":"Sul problema 8"},"content":{"rendered":"<p>La soluzione del problema 8 sar\u00e0 forse sembrata un po&#8217; debole ad alcuni lettori: in fin dei conti \u00e8 teoricamente possibile che non si riesca mai a capire chi vinca, e si debba continuare a lanciare la moneta all&#8217;infinito. Non \u00e8 proprio possibile fare di meglio, e trovare un modo per essere certi di terminare la procedura? Purtroppo no.<\/p>\n<p><!--more-->La dimostrazione non \u00e8 molto difficile: basta accorgersi che tutto quello che possiamo fare \u00e8 assegnare a uno dei giocatori un insieme preciso di successioni di testa e croce, e all&#8217;altro giocatore le successioni restanti. Se questi due insiemi fossero finiti, la probabilit\u00e0 totale sarebbe la somma delle probabilit\u00e0 delle singole successioni. Ma ciascuna successione di lunghezza N ha una probabilit\u00e0 di uscita che \u00e8 rappresentata da una frazione con denominatore 7<sup>N<\/sup>, dato che moltiplichiamo fattori 3\/7 e 4\/7. Ma la somma di frazioni con denominatore 7<sup><i>k<\/i><\/sup> non pu\u00f2 mai fare 1\/2, visto che il denominatore della somma sar\u00e0 comunque una potenza di 7. Fine dei giochi. (Una somma <b>infinita<\/b> ci permette di riuscirci, come spiegato nella risposta al problema).<\/p>\n<p>Quello che si pu\u00f2 fare \u00e8 per\u00f2 minimizzare il numero di lanci necessario per trovare il vincitore. Io cos\u00ec ad occhio userei un algoritmo &#8220;greedy&#8221; come quello indicato qui sotto, ma non ho nessuna idea se \u00e8 davvero ottimo. L&#8217;algoritmo sceglie a ogni passo la probabilit\u00e0 maggiore che non faccia sballare le percentuali, cio\u00e8 superare 1\/2, e la assegna al giocatore in svantaggio. Supponiamo per non avere subito numeri troppo grandi che la moneta lanciata mostri testa una volta su tre e croce due volte su tre: la sequenza funzioner\u00e0 allora cos\u00ec&#8230;<\/p>\n<ul>\n<li>Primo lancio T: vince A (1\/3). Probabilit\u00e0 totale di vincita: A=1\/3, B=0, resto 2\/3<\/li>\n<li>Primo lancio C, secondo lancio C: vince B (4\/9). Probabilit\u00e0 totali: A=3\/9, B=4\/9, resto 2\/9<\/li>\n<li>Primi lanci CT, terzo lancio C: vince A (4\/27). Probabilit\u00e0 totali: A=13\/27, B= 12\/27, resto 2\/27<\/li>\n<li>Primi lanci CTC, quarto lancio C: vince B (4\/81). Probabilit\u00e0 totali: A=39\/81, B=40\/81, resto 2\/81<\/li>\n<\/ul>\n<p>Semplice, no? No che non \u00e8 semplice se dobbiamo fare i conti noi e non un computer. ed \u00e8 per questo che la procedura indicata nel libro, anche se non ottimale, \u00e8 pi\u00f9 comoda!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La soluzione del problema 8 sar\u00e0 forse sembrata un po&#8217; debole ad alcuni lettori: in fin dei conti \u00e8 teoricamente possibile che non si riesca mai a capire chi vinca, e si debba continuare a lanciare la moneta all&#8217;infinito. Non \u00e8 proprio possibile fare di meglio, e trovare un modo per essere certi di terminare [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","jetpack_post_was_ever_published":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":""},"categories":[2],"tags":[],"class_list":["post-181","post","type-post","status-publish","format-standard","hentry","category-approfondimenti"],"modified_by":"xmau","jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6hcSp-2V","_links":{"self":[{"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/posts\/181","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/comments?post=181"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/posts\/181\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/media?parent=181"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/categories?post=181"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/wp\/relax\/wp-json\/wp\/v2\/tags?post=181"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}