{"id":31397,"date":"2025-02-12T04:51:28","date_gmt":"2025-02-12T03:51:28","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=31397"},"modified":"2025-02-10T14:50:12","modified_gmt":"2025-02-10T13:50:12","slug":"cantor-vs-kronecker","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2025\/02\/12\/cantor-vs-kronecker\/","title":{"rendered":"Cantor vs Kronecker"},"content":{"rendered":"

\"stringhe\" Il mese scorso, nella mailing list “Problem of the Week” di Stan Wagon, \u00e8 apparso un problema che non sono riuscito a risolvere (shame on me). La vergogna \u00e8 che quando ho visto la soluzione mi sono detto che avrei dovuto arrivarci, perch\u00e9 usava la stessa logica che avevo trovato in un altro problema. Visto che qui non si butta via nulla, vi propongo il problema, direttamente con la soluzione perch\u00e9 non \u00e8 giusto far penare anche voi. Ecco il problema:<\/p>\n

Alice ha un insieme di $n+1$ stringhe binarie di lunghezza $n \\; ( \\ge 2 )$. Bob sa che Alice ha queste stringhe, ma non sa nulla su come sono fatte. Il suo scopo \u00e8 indicare una stringa, sempre di lunghezza $n$, che Alice non possiede, e per farlo pu\u00f2 fare delle domande del tipo “qual \u00e8 il bit $j$ della stringa $k$?”. Qual \u00e8 il numero minimo di domande che Bob deve fare per essere certo di trovare la sua stringa?<\/p><\/blockquote>\n

Per i curiosi, il problema \u00e8 stato proposto da Noga Alon, Oliver Boisquet, Kasper Green Larsen, Shay Moran, e Shlomo Moran nel numero di dicembre 2024 dell’American Mathematical Monthly. Se volete provare a risolvere il problema, non proseguite la lettura.<\/p>\n

Il titolo del post dovrebbe farvi subito pensare al procedimento diagonale di Cantor: se Alice avesse solo $n$ stringhe non ci sarebbero infatti difficolt\u00e0. Bob farebbe le $n$ domande “qual \u00e8 il bit $i$ della stringa $i$?”, e costruirebbe la sua stringa prendendo il bit opposto a quello che ha avuto come risposta. In questo modo sarebbe sicuro che il primo bit della sua stringa \u00e8 diverso da quello della stringa 1 di Alice, il secondo bit \u00e8 diverso da quello della stinga 2, e cos\u00ec via. Peccato che Alice abbia una stringa in pi\u00f9, e se Bob \u00e8 sfortunato quella stringa \u00e8 proprio quella che lui ha costruito. Anche testare tutti i bit di quella stringa serve a poco: se sono tutti uguali bisogna ricominciare da capo. Insomma la strada che sembrava promettente si \u00e8 rivelata una specie di circolo vizioso. Come procedere, dunque? Ecco un secondo aiuto, quello che se mi fosse venuto in mente mi avrebbe permesso di arrivare alla soluzione: considerate un piccolo sottoinsieme delle stringhe di Alice e trovate un modo per sceglierne una specifica da cui partire per la diagonalizzazione. Avete capito come?<\/p>\n

Il trucco per riuscire a trovare una stringa “nuova” con $n+2$ domande consiste nello scegliere opportunamente il suo primo bit. Le prime tre domande di Bob saranno dunque “qual \u00e8 il primo bit della stringa 1, quello della stringa 2 e quello della stringa 3”. Di questi tre bit, almeno due devono essere uguali tra loro: senza perdita di generalit\u00e0 possiamo supporre che ci siano almeno due bit 0. (Se ci fossero due bit 1, il ragionamento \u00e8 ovviamente simmetrico). Bob allora costruir\u00e0 la sua stringa partendo con 1. La sua quarta domanda sar\u00e0 “qual \u00e8 il secondo bit della stringa $k$?”, scegliendo quella eventuale il cui primo bit \u00e8 1 (se tutte e tre le stringhe cominciavano con 0 salter\u00e0 la domanda), e metter\u00e0 l’altro valore binario come secondo bit. Da qui continua con il metodo diagonale, chiedendo il bit $k$ della stringa $k+1$ e scrivendo l’altro valore. In tutto far\u00e0 quindi $n+2$ domande. Come dimostrare che non si pu\u00f2 fare di meglio? Beh, innanzitutto avendo Alice $n+1$ stringhe Bob dovr\u00e0 fare almeno $n+1$ domande. Ma per il principio dei cassetti dovr\u00e0 chiedere almeno due volte il bit nella stessa posizione di due stringhe distinte. Se Alice dice che questi bit sono distinti allora Bob non pu\u00f2 sapere che bit mettere in quella posizione, perch\u00e9 rischia di trovare la stringa di Alice con quel bit l\u00ec.<\/p>\n

Essendo i matematici gente che ama le generalizzazioni, un problema correlato \u00e8 quello “chiedere tutto subito” in cui Bob deve fare tutte le domande in anticipo, e quindi non pu\u00f2 sfruttare le risposte di Alice per scegliere quale domanda successiva fare (la quarta domanda nella soluzione che ho riportato qui sopra). In questo caso non ci sarei arrivato nemmeno con l’aiuto di cui sopra: per\u00f2 in effetti la soluzione \u00e8 molto simile, e permette di trovare una stringa “nuova” con al pi\u00f9 $n+4$ domande. Eppure la strategia \u00e8 molto simile. Riuscite a trovarla?<\/p>\n

In questo caso Bob comincia a chiedere i primi due bit<\/i> delle stringhe 1, 2, 3: in tutto sei domande, poi continua come prima chiedendo il bit 3 della stringa 4, il bit 4 della stringa 5 e cos\u00ec via. Una volta avute tutte le risposte da Alice, Bob comincia a fare i suoi conti: ci sono quattro possibilit\u00e0 per la coppia di bit (00, 01, 10, 11), Alice pu\u00f2 averne usate al massimo tre e Bob sceglie pertanto la quarta, usando per gli altri bit l’opposto di quanto indicato da Alice. \u00c8 anche possibile dimostare che $n+4$ domande \u00e8 il valore minimo, ma non ho abbastanza spazio in questo post :-) e quindi vi rimando a questo sito<\/a> con la dimostrazione completa. <\/p>\n

Morale di tutto qusto post? Il principio dei cassetti ha giocato un ruolo fondamentale nel trovare una soluzione, sia nel caso semplice che in quello con le domande fatte a priori: la cosa \u00e8 almeno per me un po’ inaspettata.<\/p>\n","protected":false},"excerpt":{"rendered":"

Trovare una stringa binaria di n bit che sia diversa da un insieme di altre n stringhe \u00e8 facile. Ma se l’insieme ha n+1 stringhe? La risposta \u00e8 interessante, e sfrutta in maniera inaspettata il principio dei cassetti.<\/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":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"federated","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":[1005,214],"tags":[],"class_list":["post-31397","post","type-post","status-publish","format-standard","hentry","category-matelight-2025","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-8ap","jetpack-related-posts":[{"id":19329,"url":"https:\/\/xmau.com\/notiziole\/2019\/10\/13\/quizzino-della-domenica-indovinare-il-numero\/","url_meta":{"origin":31397,"position":0},"title":"Quizzino della domenica: Indovinare il numero","author":".mau.","date":"2019-10-13","format":false,"excerpt":"Alice e Bob sono logici perfetti, e ciascuno di loro sa che anche l'altro lo \u00e8. In un'urna ci sono i numeri da 1 a 9: i due amici ne estraggono uno senza farlo vedere all'altro. Segue un curioso dialogo: Alice: - non so chi di noi abbia estratto il\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2019\/10\/q411a.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":24046,"url":"https:\/\/xmau.com\/notiziole\/2022\/06\/05\/quizzino-della-domenica-il-gioco-della-divisibilita\/","url_meta":{"origin":31397,"position":1},"title":"Quizzino della domenica: Il gioco della divisibilit\u00e0","author":".mau.","date":"2022-06-05","format":false,"excerpt":"Alice sceglie un numero intero maggiore di 100 senza dirlo a Bob, e lo scrive su un foglietto (per mostrare alla fine del gioco che non ha barato...) Il gioco funziona cos\u00ec: a ogni turno Bob sceglie un numero intero k, diverso da tutti quelli che aveva gi\u00e0 scelto e\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2022\/04\/q589a.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":13240,"url":"https:\/\/xmau.com\/notiziole\/2016\/06\/12\/quizzino-della-domenica-caccia-al-colpevole\/","url_meta":{"origin":31397,"position":2},"title":"Quizzino della domenica: caccia al colpevole","author":".mau.","date":"2016-06-12","format":false,"excerpt":"In una delle isole dell'arcipelago di Smullyandia ci sono quattro categorie di persone: i Sinceri Assoluti, che dicono sempre la verit\u00e0; i Quasi Sinceri, che dicono la verit\u00e0 con l'unica eccezione che non affermeranno mai di essere colpevoli; i Mentitori Patologici, che dicono sempre il falso, e i Mentitori Responsabili,\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":32198,"url":"https:\/\/xmau.com\/notiziole\/2025\/04\/23\/insiemi-di-ulam\/","url_meta":{"origin":31397,"position":3},"title":"Insiemi di Ulam","author":".mau.","date":"2025-04-23","format":false,"excerpt":"Una generalizzazione dei numeri di Ulam visti la volta scorsa.","rel":"","context":"In "mate-light-2025"","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"percentuale di stringhe di lunghezza n che sono nell'insieme di Ulam","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/04\/ulam-words.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":11782,"url":"https:\/\/xmau.com\/notiziole\/2015\/09\/06\/quizzino-della-domenica-svicolatori\/","url_meta":{"origin":31397,"position":4},"title":"Quizzino della domenica: svicolatori","author":".mau.","date":"2015-09-06","format":false,"excerpt":"Vi siete scocciati dei quizzini logici dove la gente o dice sempre la verit\u00e0 oppure mente sempre? Siete fortunati! Qui trovate anche una terza categoria: quella degli svicolatori. Uno svicolatore \u00e8 uno che di per s\u00e9 dice la verit\u00e0, ma non tutta la verit\u00e0, evitando di dire qualcosa a suo\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":27166,"url":"https:\/\/xmau.com\/notiziole\/2023\/09\/10\/quizzino-della-domenica-il-sistema-miu\/","url_meta":{"origin":31397,"position":5},"title":"Quizzino della domenica: Il sistema MIU","author":".mau.","date":"2023-09-10","format":false,"excerpt":"Avete a disposizione un alfabeto che comprende solo tre lettere: M, I, U. Potete comporre stringhe con queste lettere a partire da una stringa gi\u00e0 presente, ma seguendo queste regole obbligatorie: (a) Se una stringa termina con una I, si pu\u00f2 aggiungere una U; quindi da UMI si ottiene UMIU,\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/09\/q660a.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/31397","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=31397"}],"version-history":[{"count":4,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/31397\/revisions"}],"predecessor-version":[{"id":31404,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/31397\/revisions\/31404"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=31397"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=31397"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=31397"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}