{"id":961,"date":"2017-01-19T22:25:40","date_gmt":"2017-01-19T21:25:40","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=961"},"modified":"2017-01-23T10:14:01","modified_gmt":"2017-01-23T09:14:01","slug":"solo-con-zero-e-uno","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2017\/01\/19\/solo-con-zero-e-uno\/","title":{"rendered":"Solo con zero e uno"},"content":{"rendered":"

Immagino sia noto a tutti che se un numero ha come fattori primi solo 2 e 5, esiste un suo multiplo che \u00e8 una potenza di 10. Sapete anche tutti che 111 \u00e8 un multiplo di 3, e 111.111.111 un multiplo di 9. Combinando quelle propriet\u00e0, vediamo anche che 1110 \u00e8 un multiplo di 6, e magari ricordate anche che 1001 \u00e8 multiplo di 7, di 11 e di 13, essendo il loro prodotto. A questo punto potrete magari chiedervi se \u00e8 vero o no che dato un qualunque numero intero ci sia un suo multiplo che contenga solo le cifre 1 e 0. Che ne dite?<\/p>\n

La risposta \u00e8 affermativa, e una possibile dimostrazione sfrutta una propriet\u00e0 che potrebbe sembrare fuori luogo in questo caso: il principio dei cassetti, quello che afferma che se metto k<\/i>+1 calzini in k<\/i> cassetti allora almeno un cassetto conterr\u00e0 due calzini. (Ne avevo parlato qui sul Post<\/a>). Dato un numero qualunque n<\/i>, prendiamo i numeri 1, 11, 111, … fino a quello composto da n<\/i>+1 cifre 1, e consideriamo il resto della divisione per n<\/i> di ciascuno di questi numeri. Otterremo n<\/i>+1 risultati, tutti compresi per definizione tra 0 e n<\/i>\u22121, e quindi al pi\u00f9 di n<\/i> valori diversi; per il principio dei cassetti almeno due di tali resti, diciamo quello del numero con p<\/i> cifre e di quello con q<\/i> cifre, devono pertanto avere lo stesso valore. Per fissare le idee immaginiamo che p<\/i>>q<\/i> e che il resto comune della divisione dei due numeri per n<\/i> sia r<\/i>. A questo punto basta prendere i due numeri corrispondenti e sottrarli tra loro: avremo un numero della forma 111…111000…000, con p<\/i>−q<\/i> 1 e q<\/i> 0, che per costruzione \u00e8 multiplo di n<\/i>. Infatti esso \u00e8 la differenza di un multiplo di n<\/i> pi\u00f9 r<\/i>, e di un altro multiplo di n<\/i> sempre pi\u00f9 r<\/i>; possiamo raccogliere insieme i due multipli ed eliminare gli r<\/i>.<\/p>\n

Chi ha studiato matematica un po’ pi\u00f9 avanzata (a livello universitario di base) e conosce la funzione totiente \u03c6(n<\/i>) (il numero di numeri inferiori a n<\/i> e primi con esso) e il Piccolo teorema di Fermat nella generalizzazione di Eulero, che afferma che se a<\/i> \u00e8 primo con n<\/i> allora a<\/i>\u03c6(n<\/i>)<\/sup> \u2261 1 (mod n<\/i>) pu\u00f2 anche calcolare una stima superiore per il numero minimo di cifre di un tale multiplo. Se n<\/i> \u00e8 primo con 10, infatti, sappiamo che 10\u03c6(9n<\/i>)<\/sup> \u2261 1 (mod 9n<\/i>), e pertanto (10\u03c6(9n<\/i>)<\/sup>\u22121)\/9 \u00e8 composto da \u03c6(9n<\/i>) cifre 1. Se invece n<\/i> \u00e8 della forma 2a<\/i><\/sup>5b<\/i><\/sup>, a seconda se a<\/i> \u00e8 maggiore o minore di b<\/i> lo possiamo moltiplicare per 5a\u2212b<\/i><\/sup> o 2b\u2212a<\/i><\/sup> e ottenere una potenza di 10 (se a=b<\/i> la potenza ce l’abbiamo gi\u00e0). Combinando i due risultati possiamo dire che un limite superiore per il numero di cifre del multiplo \u00e8 \u03c6(9n<\/i>)|a\u2212b<\/i>|.<\/p>\n","protected":false},"excerpt":{"rendered":"

No, non sto parlando della numerazione binaria, ma di una simpatica propriet\u00e0 dei numeri<\/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":true,"_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":[8,169,168],"class_list":["post-961","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-aritmetica","tag-multipli","tag-principio-dei-cassetti"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-fv","jetpack-related-posts":[{"id":2478,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/13\/una-dimostrazione-errata-e-meglio-che-nessuna-dimostrazione\/","url_meta":{"origin":961,"position":0},"title":"Una dimostrazione errata \u00e8 meglio che nessuna dimostrazione","author":".mau.","date":"13\/02\/2012","format":false,"excerpt":"Certo, in matematica una dimostrazione errata di per s\u00e9 non serve a nulla. Per\u00f2 pu\u00f2 essere un utile punto di partenza.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2598,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/26\/parilandia\/","url_meta":{"origin":961,"position":1},"title":"Parilandia","author":".mau.","date":"26\/04\/2013","format":false,"excerpt":"Noi diamo per scontata la fattorizzazione unica, ma non \u00e8 sempre cos\u00ec.","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":961,"position":2},"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":460,"url":"https:\/\/xmau.com\/ilpost\/2013\/02\/06\/mersenne-48\/","url_meta":{"origin":961,"position":3},"title":"Mersenne 48","author":".mau.","date":"06\/02\/2013","format":false,"excerpt":"\u00c8 stato scoperto un nuovo numero primo di Mersenne, o se preferite un nuovo numero perfetto.","rel":"","context":"In \"attualit\u00e0\"","block_context":{"text":"attualit\u00e0","link":"https:\/\/xmau.com\/ilpost\/tag\/attualita\/"},"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":961,"position":4},"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":[]},{"id":672,"url":"https:\/\/xmau.com\/ilpost\/2015\/12\/03\/teoremi-e-probabilita\/","url_meta":{"origin":961,"position":5},"title":"Teoremi e probabilit\u00e0","author":".mau.","date":"03\/12\/2015","format":false,"excerpt":"Sembrano due concetti agli antipodi, eppure si possono dimostrare alcuni teoremi con metodi probabilistici.","rel":"","context":"In \"dimostrazioni\"","block_context":{"text":"dimostrazioni","link":"https:\/\/xmau.com\/ilpost\/tag\/dimostrazioni\/"},"img":{"alt_text":"cerchi","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2015\/12\/cerchi-300x182.png?resize=350%2C200","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/961","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=961"}],"version-history":[{"count":7,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/961\/revisions"}],"predecessor-version":[{"id":970,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/961\/revisions\/970"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=961"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=961"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=961"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}