{"id":32915,"date":"2025-06-25T20:07:18","date_gmt":"2025-06-25T18:07:18","guid":{"rendered":"https:\/\/xmau.com\/wp\/notiziole\/?p=32915"},"modified":"2025-06-25T20:07:18","modified_gmt":"2025-06-25T18:07:18","slug":"il-problema-di-langford-ii","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2025\/06\/25\/il-problema-di-langford-ii\/","title":{"rendered":"Il problema di Langford (II)"},"content":{"rendered":"

La scorsa settimana avevo presentato il problema di Langford<\/a>: mettere in fila $2n$ coppie di numeri da $1$ a $n$ in modo che tra i due numeri $i$ ci siano esattamente $i$ altri numeri. Per $n=3$ e $n=4$ le soluzioni (essenzialmente uniche) sono rispettivamente 3-1-2-1-3-2 e 4-1-3-1-2-4-3-2. Ho anche detto che una soluzione era possibile solo se il numero di coppie era della forma $4k$ oppure $4k+3$, come \u00e8 stato dimostrato da Roy O. Davies. La dimostrazione \u00e8 molto semplice: eccola qua.<\/p>\n

Numeriamo da $1$ a $2n$ i numeri dell’elenco, e per ciascun numero $k \\in {1, … n}$ consideriamo le due posizioni $P_k < Q_k$ dei due numeri nell'elenco. Nel caso $n=3$ abbiamo per esempio $P_1 = 2, Q_1 = 4, P_2 = 3, Q_2 = 6, P_3 = 1, Q_3 = 5.$ Chiaramente abbiamo $Q_k = P_k + k + 1$ per definizione di coppia $k$. La somma di tutti questi valori \u00e8 $\\sum_{k=1}^{n} (2P_k + k + 1) = 2\\sum_{k=1}^{n} P_k + n + n(n+1)\\!\/\\!2$, ma visto che sono i valori da $i$ a $2n$ sappiamo che la somma \u00e8 anche $n(2n+1).$ Poich\u00e9 la somma dei $P_k$ \u00e8 evidentemente un numero intero, ci accorgiamo subito che se $n = 4q + 1$ oppure $n = 4q +2$ abbiamo che gli altri termini danno una somma frazionaria e quindi non ci sono soluzioni. \u25a1\n\nQuesto \u00e8 un risultato negativo, nel senso che ci dice quando non<\/b> si pu\u00f2 risolvere il problema ma non quando lo si pu\u00f2 fare. Per\u00f2 le soluzioni negli altri casi sono tantissime, a parte quella unica nei casi visti sopra. Davies pensava che per $n=7$ ci fossero 25 soluzioni, e Martin Gardner nel 1967 riport\u00f2 quel valore: in realt\u00e0 ce ne sono 26. John Miller, come scrive nel suo sito<\/a>, programm\u00f2 un computer nel 1968 e trov\u00f2 le 26 soluzioni per $n=7$ e le 150 per $n=8$. (Due persone riuscirono a trovare tutte le soluzioni nel primo caso a mano…). E.J. Groth ottenne anche il numero di soluzioni per $n=11$ (17792) e $n=12$ (108144). Altri valori si possono trovare come sempre su OEIS<\/a>: quelli per 15 e 16 sono stati computati negli anni ’80; il 19 nel 1999, il 20 nel 2002, il 23 nel 2004, il 24 nel 2005, il 27 e il 28 nel 2015… e poi non si sa pi\u00f9. Del resto, le soluzioni per $n=28$ sono 1607383260609382393152, diciamo parecchie! <\/p>\n

Si pu\u00f2 anche decidere di accettare solo le soluzioni “planari” al problema, nel senso che i numeri uguali si possono connettere tra loro e ottenere un grafo planare. La soluzione generale per $n=3$ \u00e8 planare, quella per $n=4$ e quelle per $n=7$ non lo sono, ci sono quattro soluzioni planari per $n=8$ e cos\u00ec via. Come al solito, OEIS ha la successione<\/a>. C’\u00e8 poi la “variante Tanton”, da James Tanton: in questo caso ci sono $n$ studenti seduti in circolo, e si chiede che si pu\u00f2 dare un numero da 1 a $n$ agli studenti in modo tale che se lo studente $k$ si sposta di $k$ posti in senso orario (quindi quello $n$ non si sposta…) alla fine non ci sia nessuno seduto sulle ginocchia di un altro. In questo caso si pu\u00f2 dimostrare con semplici sistemi di parit\u00e0 che il numero di studenti deve essere dispari: stranamente la successione dei possibili valori (0, 0, 1, 0, 3, 0, 19, 0, 225, 0, 3441, 0, 79259, 0, 2424195…) non si trova su OEIS!<\/p>\n","protected":false},"excerpt":{"rendered":"

Ancora sul problema di Langford<\/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-32915","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-8yT","jetpack-related-posts":[{"id":29485,"url":"https:\/\/xmau.com\/notiziole\/2024\/08\/14\/e-allora-cose-una-dimostrazione-elegante\/","url_meta":{"origin":32915,"position":0},"title":"E allora cos’\u00e8 una dimostrazione elegante?","author":".mau.","date":"2024-08-14","format":false,"excerpt":"questo \u00e8 pi\u00f9 difficile da definire, almeno per me","rel":"","context":"In "mate-light-2024"","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/08\/quadrato-300x289.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":32831,"url":"https:\/\/xmau.com\/notiziole\/2025\/06\/18\/il-problema-di-langford\/","url_meta":{"origin":32915,"position":1},"title":"Il problema di Langford","author":".mau.","date":"2025-06-18","format":false,"excerpt":"Mai fare giocare il bimbo di un matematico coi cubetti colorati!","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":"soluzione del problema di Langford con n=3 e n=4","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/06\/Langford_blocks.svg_.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/06\/Langford_blocks.svg_.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/06\/Langford_blocks.svg_.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":7749,"url":"https:\/\/xmau.com\/notiziole\/2010\/03\/11\/fibonacci_e_lin\/","url_meta":{"origin":32915,"position":2},"title":"Fibonacci e l’induzione","author":".mau.","date":"2010-03-11","format":false,"excerpt":"un teorema sui numeri di Fibonacci dimostrabile con l'induzione","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":30274,"url":"https:\/\/xmau.com\/notiziole\/2025\/01\/01\/buon-2025-matematico\/","url_meta":{"origin":32915,"position":3},"title":"Buon 2025 matematico!","author":".mau.","date":"2025-01-01","format":false,"excerpt":"Il 2025 \u00e8 un anno il cui valore ha molte propriet\u00e0 matematiche, come racconta Greg Ross: \u00c8 un quadrato (45\u00b2). \u00c8 il prodotto di due quadrati (9\u00b2 \u00d7 5\u00b2). \u00c8 la somma dei cubi dei primi nove numeri naturali (1\u00b3 + 2\u00b3 + 3\u00b3 + 4\u00b3 + 5\u00b3 + 6\u00b3\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":34475,"url":"https:\/\/xmau.com\/notiziole\/2025\/11\/30\/quizzino-della-domenica-numeri-di-fermat\/","url_meta":{"origin":32915,"position":4},"title":"Quizzino della domenica: Numeri di Fermat","author":".mau.","date":"2025-11-30","format":false,"excerpt":"776 - algebra I numeri di Fermat sono quelli della forma Fn = 2^(2^n)) + 1. Una congettura di Fermat affermava che se n \u00e8 primo, allora Fn \u00e8 primo (\"numero primo di Fermat\"). I primi numeri in effetti lo sono: F0 = 3, F1 = 5, F2 = 17,\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"F_n = 2^(2^n) + 1","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/11\/q776a.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":9423,"url":"https:\/\/xmau.com\/notiziole\/2013\/08\/04\/quizzino-goldbach-alla-rovescia\/","url_meta":{"origin":32915,"position":5},"title":"Quizzino della domenica: Goldbach alla rovescia","author":".mau.","date":"2013-08-04","format":false,"excerpt":"Uno dei problemi di teoria dei numeri pi\u00f9 elusivo \u00e8 il dimostrare la congettura di Goldbach: ogni numero pari maggiore di 2 \u00e8 esprimibile come somma di due numeri primi. Noi stavolta ci accontentiamo di qualcosa di meno: dimostrare che ogni numero dispari maggiore di 11 \u00e8 esprimibile come somma\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":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/32915","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=32915"}],"version-history":[{"count":5,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/32915\/revisions"}],"predecessor-version":[{"id":32921,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/32915\/revisions\/32921"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=32915"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=32915"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=32915"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}