{"id":2626,"date":"2013-07-12T07:00:55","date_gmt":"2013-07-12T05:00:55","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2626"},"modified":"2022-10-11T12:41:18","modified_gmt":"2022-10-11T10:41:18","slug":"epidemie","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2013\/07\/12\/epidemie\/","title":{"rendered":"Epidemie"},"content":{"rendered":"

Anche stavolta parlo di un problema tratto da Numberplay. Il matematico ungherese naturalizzato britannico B\u00e9la Bollob\u00e1s racconta<\/a>:<\/p>\n

Un’epidemia si sta propagando in una scacchiera 12\u00d712. Inizialmente solo alcune caselle sono infette: una casella infetta lo rimarr\u00e0 per sempre, e una casella non infetta si infetter\u00e0 se avr\u00e0 almeno due caselle confinanti infette. Per “confinanti” si intende “che la toccano su un lato”, quindi una casella ha al pi\u00f9 quattro caselle confinanti. Qual \u00e8 il numero minimo di caselle inizialmente infette che potr\u00e0 infettare tutta la scacchiera?<\/em><\/p><\/blockquote>\n

Per la cronaca, \u00e8 possibile partire da una configurazione di ben 132 caselle infettate (tutte tranne la riga superiore della scacchiera) e non riuscire a infettare tutta la scacchiera: \u00e8 facile vedere che la riga superiore non verr\u00e0 mai infettata, poich\u00e9 ogni casella ha solo un vicino infetto. Ma il killer della tastiera pu\u00f2 scegliere opportunamente i punti di infezione e usarne molto meno. Volete sapere come?<\/p>\n

\u00c8 abbastanza facile trovare una configurazione di dodici caselle iniziali che porta all’infezione completa: si pu\u00f2 per esempio iniziare con una diagonale maggiore. A ogni passo una diagonale vicina viene infettata: al decimo passo pertanto l’epidemia si sar\u00e0 propagata a tutta la scacchiera. Ci sono per\u00f2 molte altre configurazioni iniziali con dodici caselle che, anche se pi\u00f9 lentamente, riescono a infettare tutta la scacchiera. Quella che ho inizialmente trovato io, per esempio, partiva dalle caselle (1,2n<\/i>) e (2n<\/i>,1) per arrivare in 21 passi allo stesso risultato. A questo punto sorge spontanea la domanda “ma la soluzione ottimale sar\u00e0 proprio dodici?”. La risposta \u00e8 s\u00ec; e la dimostrazione \u00e8 almeno a mio parere bellissima.<\/p>\n

Introduciamo innanzitutto il concetto (generale) di monovariante<\/b>, che \u00e8 una generalizzazione di quello di invariante. Un invariante, lo sappiamo tutti, \u00e8 qualcosa che non varia. Un esempio tipico di invariante \u00e8 la parit\u00e0, che permette di risolvere facilmente questo gioco stupido. Ci sono i numeri da 1 a 15 a disposizione, e ogni giocatore ne sceglie a turno uno, sommandolo o sottraendolo al risultato precedente: se il risultato finale \u00e8 dispari vince il primo giocatore, se \u00e8 pari \u00e8 il secondo. Il gioco \u00e8 stupido perch\u00e9 non importa assolutamente quali numeri si scelgono e se li si somma o li si sottrae! In ogni caso il risultato finale sar\u00e0 pari, perch\u00e9 la parit\u00e0 \u00e8 invariante cambiando i segni della somma alegbrica. Il monovariante \u00e8 quasi come un invariante, nel senso che pu\u00f2 variare ma solo in una direzione: insomma \u00e8 qualcosa che non decresce mai (oppure non cresce mai), anche se pu\u00f2 restare costante.<\/p>\n

Nel nostro problema il monovariante \u00e8 dato dal perimetro della zona infetta. Immaginiamo di aggiungere una nuova casella infetta: il perimetro aumenta di quattro unit\u00e0 ma bisogna togliere i lati in comune. Se la casella ha due vicini infetti, il risultato netto \u00e8 nullo (togliamo due lati dalla nuova casella e altri due dalle vecchie caselle); se ha tre vicini infetti il perimetro sar\u00e0 pi\u00f9 breve di due unit\u00e0; se ha quattro vicini infetti il perimetro sar\u00e0 pi\u00f9 corto di quattro unit\u00e0. Dunque il perimetro \u00e8 un monovariante il cui valore pu\u00f2 solo ridursi o al massimo restare costante. Ma la configurazione finale (tutte le caselle infette) ha ovviamente un perimetro 48, quello della scacchiera; ergo per poterci arrivare \u00e8 necessario avere almeno 12 caselle iniziali (nessuna che si tocchi se non al pi\u00f9 per un vertice), che danno appunto un perimetro iniziale di 48. Fine della dimostrazione.<\/p>\n

Post scriptum: Gary Hewitt ha preparato qui<\/a> un programmino per vedere il diffondersi di un’epidemia a partire da una certa configurazione di partenza. Per la cronaca, l’epidemia pi\u00f9 lenta (ci vogliono 81 passi per riempire la scacchiera) partendo da dodici caselle infette sembrerebbe essere questa:<\/p>\n

\u00a01,0,0,0,0,0,0,0,0,0,0,1|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,1,0,0,0,0,0,0,1,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,1,0,0,1,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,0,0,1,0,0,0,0,0|
\n0,0,0,0,0,0,0,1,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,1,0,0,0,0,1,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,1,0,0,0,0,0,0,0,0,1<\/tt><\/p><\/blockquote>\n

Ma \u00e8 possibile fare di meglio! La configurazione qui sotto parte con 14 caselle infette, ma le occorrono ben 95 passi per completare l’infezione.<\/p>\n

\u00a00,0,0,0,0,0,0,0,0,0,0,1|
\n1,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,1|
\n1,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,1|
\n1,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,0|
\n0,0,0,0,0,0,0,0,0,0,0,1|
\n1,0,0,0,1,0,0,0,1,0,0,0|
\n1,0,1,0,0,0,1,0,0,0,1,0<\/tt><\/p><\/blockquote>\n

Non so se ci sia una morale in tutto questo. So per\u00f2 che la dimostrazione qui sopra \u00e8 sicuramente nel Libro, avrebbe detto Paul Erd\u0151s<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Un problema matematico la cui dimostrazione \u00e8 un’applicazione del concetto di monovariante.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2626","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/shh2yP-epidemie","jetpack-related-posts":[{"id":2470,"url":"https:\/\/xmau.com\/ilpost\/2012\/01\/09\/sudoku-minimali-e-massimali\/","url_meta":{"origin":2626,"position":0},"title":"Sudoku minimali e massimali","author":".mau.","date":"09\/01\/2012","format":false,"excerpt":"Il 2012 si \u00e8 aperto con la dimostrazione che per avere un sudoku risolvibile \u00e8 necessario avere almeno 17 numeri. Come ci si \u00e8 arrivati? Forza (quasi) bruta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2012\/01\/sudoku77.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1459,"url":"https:\/\/xmau.com\/ilpost\/2019\/04\/21\/problemini-per-pasqua-2019\/","url_meta":{"origin":2626,"position":1},"title":"Problemini per Pasqua 2019","author":".mau.","date":"21\/04\/2019","format":false,"excerpt":"Gli usuali cinque problemini da risolvere... stavolta pi\u00f9 semplici del solito","rel":"","context":"In \"quizzini\"","block_context":{"text":"quizzini","link":"https:\/\/xmau.com\/ilpost\/tag\/quizzini\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/04\/q381a.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2652,"url":"https:\/\/xmau.com\/ilpost\/2013\/11\/15\/tavola-periodica-dei-matematici\/","url_meta":{"origin":2626,"position":2},"title":"Tavola periodica dei matematici","author":".mau.","date":"15\/11\/2013","format":false,"excerpt":"Un modo divertente per raccogliere i pi\u00f9 grandi matematici della storia","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":159,"url":"https:\/\/xmau.com\/ilpost\/2014\/03\/11\/come-calcolare-pi-greco-a-furia-di-rimbalzi\/","url_meta":{"origin":2626,"position":3},"title":"Come calcolare pi greco a furia di rimbalzi","author":".mau.","date":"11\/03\/2014","format":false,"excerpt":"un calcolatore analogico per trovare le cifre di pi greco","rel":"","context":"In \"approssimazioni\"","block_context":{"text":"approssimazioni","link":"https:\/\/xmau.com\/ilpost\/tag\/approssimazioni\/"},"img":{"alt_text":"[due palle un soldo]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2014\/03\/pi-palle-300x200.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":445,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/13\/prima-di-godel\/","url_meta":{"origin":2626,"position":4},"title":"Prima di G\u00f6del…","author":".mau.","date":"13\/09\/2011","format":false,"excerpt":"I teoremi di incompletezza di G\u00f6del hanno segnato la fine della sicurezza che i matematici hanno avuto per 2500 anni. Cosa \u00e8 successo prima che arrivasse lui?","rel":"","context":"In \"logica\"","block_context":{"text":"logica","link":"https:\/\/xmau.com\/ilpost\/tag\/logica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":194,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/05\/gira-la-carta\/","url_meta":{"origin":2626,"position":5},"title":"Gira la carta","author":".mau.","date":"05\/09\/2011","format":false,"excerpt":"Una specie di gioco di prestigio matematico: l'asso galleggia sempre e si porta all'inizio del mazzetto di carte...","rel":"","context":"In \"combinatoria\"","block_context":{"text":"combinatoria","link":"https:\/\/xmau.com\/ilpost\/tag\/combinatoria\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2626","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2626"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2626\/revisions"}],"predecessor-version":[{"id":2627,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2626\/revisions\/2627"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}