{"id":2624,"date":"2013-07-08T17:05:20","date_gmt":"2013-07-08T15:05:20","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2624"},"modified":"2022-10-11T12:40:49","modified_gmt":"2022-10-11T10:40:49","slug":"basta-saperlo","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2013\/07\/08\/basta-saperlo\/","title":{"rendered":"Basta saperlo&#8230;"},"content":{"rendered":"<p>Lo so, \u00e8 estate, ma non fa poi cos\u00ec caldo: insomma, potete anche lavorare un po&#8217;. Eccovi due problemi matematici: come fareste per risolverli?<\/p>\n<ul>\n<li>Quante sono le stringhe binarie &#8211; quindi composte di 0 e 1 &#8211; B<sub>n<\/sub> di lunghezza <i>n<\/i> che non contengano all&#8217;interno due cifre 1 consecutive? Per esempio, 000101 \u00e8 valida, mentre 001101 no.<\/li>\n<li>Quanti sono i sottoinsiemi S<sub>n<\/sub> dell&#8217;insieme {1, 2, &#8230;, <i>n<\/i>} in cui non ci sono mai due numeri consecutivi? Per esempio, con i numeri da 1 a 6 il sottoinsieme vuoto {} e {1,3,6} sono validi mentre {2,3,5} no, perch\u00e9 ci sono 2 e 3.<\/li>\n<\/ul>\n<p>&nbsp;<br \/>\nVisti cos\u00ec, i due problemi sembrano piuttosto ostici: d&#8217;altra parte questa dovrebbe essere la situazione tipica di quando ci si trova di fronte a un problema. Certo che se un&#8217;anima pia ci dicesse &#8220;Dimostrate che il numero di stringhe B<sub>n<\/sub> \u00e8 dato dalla formula blablabla&#8221; sarebbe tutta un&#8217;altra cosa, vero? Devo fare l&#8217;anima pia? Mass\u00ec, su: leggete qui sotto, se non volete fermarvi a risolverlo completamente per conto vostro.<\/p>\n<p><!--more--> Per la cronaca, ho trovato questi due problemi nel libro di Martin Erickson <i>Pearls of Discrete Mathematics<\/i>, come una noticina sul fatto che i numeri di Fibonacci spuntano dove meno uno se lo aspetta. In pratica, data la successione definita come <\/p>\n<blockquote><p>&nbsp;F<sub>0<\/sub>=0,<br \/>\n&nbsp;F<sub>1<\/sub>=1,<br \/>\n&nbsp;F<sub><i>n<\/i>+2<\/sub>=F<sub><i>n<\/i>+1<\/sub>+F<sub><i>n<\/i><\/p><\/blockquote>\n<p>abbiamo che sia B<sub>n<\/sub> che S<sub>n<\/sub> sono pari a F<sub><i>n<\/i>+2<\/sub>. Uno dei due risultati \u00e8 anche dimostrato nel testo, il secondo no: ma questo non \u00e8 cos\u00ec importante, visto che una volta che si capisce come dimostrarne uno si arriva direttamente al secondo. <\/p>\n<p>Abbiamo dunque un punto di partenza piuttosto importante. Onestamente, un Vero Matematico non avrebbe nemmeno avuto bisogno di questo aiutino, perch\u00e9 si sarebbe messo a contare a manina il valore delle due successioni per <i>n<\/i> piccolo, e da l\u00ec avrebbe intuito la formula. Mettiamoci subito a fare i conti, allora!<\/p>\n<p>Per B<sub><i>n<\/i><\/sub>, la tabella \u00e8 la seguente:<br \/>\n&#8211; B<sub>0<\/sub>=1: per le <a href=\"https:\/\/www.ilpost.it\/mauriziocodogno\/2010\/12\/10\/le-mirabolanti-proprieta-dellinsieme-vuoto\/\">mirabolanti propriet\u00e0 dell&#8217;insieme vuoto<\/a>, c&#8217;\u00e8 un solo modo di avere una stringa di zero caratteri, e sicuramente essa non contiene due cifre 1 consecutive.<br \/>\n&#8211; B<sub>1<\/sub>=2: le stringhe sono &#8220;0&#8221; e &#8220;1&#8221;.<br \/>\n&#8211; B<sub>2<\/sub>=3: le stringhe sono &#8220;00&#8221;, &#8220;01&#8221; e &#8220;10&#8221;, visto che &#8220;11&#8221; \u00e8 da cassare.<br \/>\n&#8211; B<sub>3<\/sub>=5: alle tre stringhe qui sopra possiamo aggiungere a destra uno 0 e un 1, ma &#8220;011&#8221; \u00e8 da togliere. Le stringhe sono quindi &#8220;000&#8221;, &#8220;001&#8221;, &#8220;010&#8221;, &#8220;100&#8221;, &#8220;101&#8221;.<br \/>\n&#8211; B<sub>4<\/sub>=8: lascio al lettore la facile verifica :-) <\/p>\n<p>Per gli S<sub><i>n<\/i><\/sub>, la tabella \u00e8 la seguente:<br \/>\n&#8211; S<sub>0<\/sub>=1 per le stesse ragioni di cui sopra (di insiemi vuoti ce n&#8217;\u00e8 uno solo, {});<br \/>\n&#8211; S<sub>1<\/sub>=2: i sottoinsiemi sono {} e {1};<br \/>\n&#8211; S<sub>2<\/sub>=3: i sottoinsiemi sono {}, {1}, {2};<br \/>\n&#8211; S<sub>3<\/sub>=5: i sottoinsiemi sono {}, {1}, {2}, {3}, {1,3};<br \/>\n&#8211; S<sub>4<\/sub>=8: i sottoinsiemi sono {}, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}. (E non dite che non sono bravo, stavolta ve li ho scritti tutti, e anche nel modo migliore per dimostrare la propriet\u00e0!)<\/p>\n<p>Occhei, supponiamo che di riffa o di raffa siate riusciti a intuire qual \u00e8 la formula da dimostrare, e quindi abbiate fatto met\u00e0 del lavoro. Generalmente, per dimostrare una formula generale per ogni <i>n<\/i>, il sistema pi\u00f9 &#8220;naturale&#8221; \u00e8 quello di usare <a href=\"http:\/\/xmau.com\/notiziole\/arch\/201003\/006416.html\">l&#8217;induzione<\/a>. Naturale tra virgolette, perch\u00e9 se uno matematico non \u00e8 non gli verrebbe mai in mente, e anche se \u00e8 un matematico usare l&#8217;induzione \u00e8 sempre un modo per nascondere il fatto che non sa assolutamente qual \u00e8 il significato intrinseco del problema e si rifugia nelle trasformazioni algebriche che si possono fare senza azionare neuroni se non per controllare che i conti siano giusti. Ma con Fibonacci c&#8217;\u00e8 un&#8217;altra via, che sotto sotto \u00e8 sempre induzione ma \u00e8 un po&#8217; meno scollegata dalla realt\u00e0: quella di dimostrare direttamente che vale la relazione indicata sopra, che cio\u00e8 F<sub><i>n<\/i>+2<\/sub>=F<sub><i>n<\/i>+1<\/sub>+F<sub><i>n<\/i><\/sub>. Detto in altro modo, si cerca di associare a tutti gli elementi di ordine <i>n<\/i>+2 un elemento di ordine <i>n<\/i>+1 oppure uno di ordine <i>n<\/i>, senza lasciarne da parte nessuno; la relazione si ottiene cos\u00ec immediatamente.<\/p>\n<p>Nel primo caso, immaginiamo di avere una stringa binaria di lunghezza <i>n<\/i>+2: essa pu\u00f2 terminare solo per 00, 10, oppure 01. Bene. Raggruppiamo i primi due casi, e otteniamo che la nostra stringa pu\u00f2 terminare per 0 oppure per 01. Beh, le stringhe binarie di lunghezza <i>n<\/i>+2 che terminano per 0 e che non hanno due 1 consecutivi sono evidentemente B<sub><i>n<\/i>+1<\/sub>, e quelle che terminano per 01 e non hanno due 1 consecutivi sono B<sub><i>n<\/i><\/sub>; i casi <i>n<\/i>=0 e <i>n<\/i>=1 li abbiamo provati a mano, e quindi siamo a posto. Nel secondo caso, il sottoinsieme dei numeri da 1 a <i>n<\/i>+2 pu\u00f2 non contenere <i>n<\/i>+2 (e in quel caso vanno bene tutti gli elementi di S<sub><i>n<\/i>+1<\/sub>) oppure, se contiene <i>n<\/i>+2, allora non deve contenere <i>n<\/i>+1 (e in quel caso vanno bene tutti gli elementi di S<sub><i>n<\/i><\/sub>). Di nuovo, aggiungendo i casi 0 e 1 trattati a mano sopra, abbiamo riscoperto la formula di base di Fibonacci. Notate come in entrambi i casi, seguendo tra l&#8217;altro uno dei dettami della combinatorica, abbiamo effettivamente <b>contato<\/b> gli elementi dei nostri insiemi: una dimostrazione insomma costruttiva.<\/p>\n<p>Morale della storia? Che nella risoluzione di problemi matematici (che \u00e8 cosa ben diversa dal fare matematica, ricordatevelo&#8230; ma che comunque qualche punto in comune ce l&#8217;ha) il Vero Matematico sa come cercare un&#8217;ipotesi facendo un po&#8217; di prove a manina, e che per certi tipi di ipotesi (nel nostro caso, la successione di Fibonacci) ha nel suo Opportuno Manuale qualche tecnica standard, che allo studente tipico sembra tanto una magia ma non lo \u00e8 affatto.<\/p>\n<p>Post Scriptum: naturalmente un Vero Matematico <b>non<\/b> avrebbe mai dimostrato la seconda propriet\u00e0. Non perch\u00e9 l&#8217;avrebbe &#8220;lasciata come esercizio allo studente&#8221;, ma perch\u00e9 avrebbe mostrato un <b>isomorfismo<\/b> tra i due problemi: avrebbe cio\u00e8 mostrato come si pu\u00f2 associare a ciascun sottoinsieme dei numeri da 1 a <i>n<\/i> una stringa binaria di <i>n<\/i> numeri. Avete capito come? E ve ne sareste accorti se non ve l&#8217;avessi segnalato?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Spesso in matematica sapere qual \u00e8 il risultato da dimostrare fa anche intuire qual \u00e8 la strada da prendere per dimostrarlo. Il guaio \u00e8 appunto riuscire a saperlo&#8230;<\/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-2624","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\/phh2yP-Gk","jetpack-related-posts":[{"id":2432,"url":"https:\/\/xmau.com\/ilpost\/2011\/08\/31\/numeri-razionali-irrazionali-algebrici-e-trascendenti\/","url_meta":{"origin":2624,"position":0},"title":"Numeri razionali, irrazionali, algebrici e trascendenti","author":".mau.","date":"31\/08\/2011","format":false,"excerpt":"I numeri pi\u00f9 naturali dopo i naturali sono i razionali. Lo dice la parola stessa, no?","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2476,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/08\/la-magia-delle-soluzioni\/","url_meta":{"origin":2624,"position":1},"title":"La magia delle soluzioni","author":".mau.","date":"08\/02\/2012","format":false,"excerpt":"Spesso la soluzione di un problema matematico sembra uscire come per magia da un cappello. Ma in fin dei conti il bello della matematica \u00e8 che un problema pu\u00f2 magicamente essere visto da un altro punto di vista!","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2422,"url":"https:\/\/xmau.com\/ilpost\/2011\/07\/12\/6174-196-e-altri-numeri\/","url_meta":{"origin":2624,"position":2},"title":"6174, 196 e altri numeri","author":".mau.","date":"12\/07\/2011","format":false,"excerpt":"Alcuni numeri sono pi\u00f9 interessanti di altri, almeno per chi ama cercare le loro propriet\u00e0 strane.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":449,"url":"https:\/\/xmau.com\/ilpost\/2011\/12\/20\/il-primo-teorema-di-incompletezza-di-godel\/","url_meta":{"origin":2624,"position":3},"title":"Il primo teorema di incompletezza di G\u00f6del","author":".mau.","date":"20\/12\/2011","format":false,"excerpt":"La dimostrazione del teorema di incompletezza di G\u00f6del non \u00e8 complicatissima, ma \u00e8 cos\u00ec autoreferenziale che a volte sembra di vedere Ritorno al futuro II. Ho provato a sminuzzarla e descriverla.","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":2434,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/07\/i-numeri-immaginari-e-complessi\/","url_meta":{"origin":2624,"position":4},"title":"I numeri immaginari e complessi","author":".mau.","date":"07\/09\/2011","format":false,"excerpt":"Gi\u00e0 chiamare dei numeri \u201cimmaginari\u201d fa capire che i matematici non erano poi cos\u00ec convinti che esistessero davvero. Per\u00f2 ne avevano bisogno, e quindi non si facevano troppi problemi.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":621,"url":"https:\/\/xmau.com\/ilpost\/2015\/09\/16\/numeri-che-forse-non-esistono\/","url_meta":{"origin":2624,"position":5},"title":"Numeri che forse non esistono","author":".mau.","date":"16\/09\/2015","format":false,"excerpt":"Nessuno sa se i numeri di Lychrel esistano davvero, almeno in base 10. Per\u00f2 se ne pu\u00f2 lo stesso parlare.","rel":"","context":"In \"numeri\"","block_context":{"text":"numeri","link":"https:\/\/xmau.com\/ilpost\/tag\/numeri\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2624","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=2624"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2624\/revisions"}],"predecessor-version":[{"id":2625,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2624\/revisions\/2625"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2624"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2624"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2624"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}