Stack Exchange<\/a>, dove potete trovare due risposte equivalenti. La mia soluzione procede alla rovescia per semplicit\u00e0 espositiva. Ricordo a chi non \u00e8 avvezzo alle dimostrazioni di strategie vincenti nei giochi a due di questo tipo – dove cio\u00e8 chi non ha pi\u00f9 mosse a disposizione perde – che una posizione \u00e8 vincente quando esiste una mossa che lascia l’avversario in una posizione perdente ed \u00e8 perdente quando tutte le mosse possibili lasciano l’avversario in una posizione vincente.<\/p>\nSappiamo che 2×2 \u00e8 una posizione perdente: vediamo cosa possiamo dire per un generico 2×n<\/i>. 2×3 \u00e8 vincente: si mangia un pezzo 2×1 e si lascia 2×2. 2×4 \u00e8 perdente: l’unica possibilit\u00e0 ammessa \u00e8 mangiare un pezzo 2×1 e quindi si lascia l’avversario in una posizione vincente. Quindi le posizioni da 2×5 a 2×7 sono vincenti (si lascia all’avversario la tavoletta 2×4), la 2×8 \u00e8 perdente (si deve lasciare una di quelle da 2×5 a 2×7), e penso sia abbastanza chiaro a tutti che si pu\u00f2 dimostrare per induzione che tutte le posizioni 2×2k<\/i><\/sup>, con k<\/i>≥1, sono perdenti mentre le altre 2×n<\/i> sono vincenti. <\/p>\nOra andiamo avanti: possiamo supporre senza perdita di generalit\u00e0 che m<\/i>≤n<\/i>. 3×3 \u00e8 evidentemente perdente, perch\u00e9 l’unica mossa possibile manda in 2×3 che \u00e8 vincente. 3×4 e 3×5 sono pertanto vincenti, visto che si pu\u00f2 arrivare a 3×3; 3×6 \u00e8 perdente perch\u00e9 si pu\u00f2 andare a 2×6 (che abbiamo visto prima essere vincente) oppure 3×4 o 3×5 che sono anch’esse vincenti; da 3×7 a 3×11 si pu\u00f2 arrivare a 3×6 e quindi tutte quelle sono posizioni vincenti. Immagino che non abbiate problemi a dimostrare – sempre per induzione – che le posizioni 3×(3·2k<\/i><\/sup>) siano perdenti e le altre 3×n<\/i> vincenti, e forse a questo punto siete anche pronti a immaginare la regola generale: le posizioni m<\/i>×(m<\/i>·2k<\/i><\/sup>) sono perdenti, le altre vincenti. Qui sotto uno sketch of proof, sono troppo pigro per mettere tutti i dettagli.<\/p>\nInnanzitutto, da una posizione m<\/i>×m<\/i> con m<\/i>>2 si pu\u00f2 solo arrivare a una posizione r<\/i>×m<\/i> e l’avversario pu\u00f2 giungere a r<\/i>×r<\/i>, lasciandoci quindi in una posizione perdente per ipotesi induttiva. Nel caso di una posizione m<\/i>×(m<\/i>·2k<\/i><\/sup>) i casi sono due: se si tolgono delle colonne arrivando a m<\/i>×w<\/i> il nostro avversario pu\u00f2 sempre passare a m<\/i>×(m<\/i>·2k<\/i>−1<\/sup>) (perch\u00e9?) che \u00e8 perdente sempre per ipotesi induttiva: se invece si tolgono delle righe arrivando a r<\/i>×(m<\/i>·2k<\/i><\/sup>) il nostro avversario pu\u00f2 sempre passare a r<\/i>×(r<\/i>·2k<\/i><\/sup>) (perch\u00e9?) che di nuovo \u00e8 perdente per ipotesi induttiva. Tutto qua.<\/p>\nMorale della favola? Se si inizia con calma a provare i casi facili magari pu\u00f2 venire un’idea della soluzione. Tentar non nuoce :-)<\/p>\n","protected":false},"excerpt":{"rendered":"
Un gioco per cui si pu\u00f2 trovare una strategia vincente senza eccessiva fatica. <\/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":[82,26],"class_list":["post-616","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-induzione","tag-problemi"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-9W","jetpack-related-posts":[{"id":2481,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/23\/quando-i-matematici-sbagliano\/","url_meta":{"origin":616,"position":0},"title":"Quando i matematici sbagliano","author":".mau.","date":"23\/02\/2012","format":false,"excerpt":"Perch\u00e9 preoccuparsi delle smentite in fisica? Persino in matematica una dimostrazione non \u00e8 sempre corretta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2642,"url":"https:\/\/xmau.com\/ilpost\/2013\/10\/07\/il-numero-di-dio\/","url_meta":{"origin":616,"position":1},"title":"Il Numero di Dio","author":".mau.","date":"07\/10\/2013","format":false,"excerpt":"Il cubo di Rubik pu\u00f2 sermpre essere risolto in al pi\u00f9 venti mosse. Come lo si \u00e8 scoperto? Usando la forza bruta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"un cubo di Rubik","src":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/a\/a6\/Rubik%27s_cube.svg\/200px-Rubik%27s_cube.svg.png","width":350,"height":200},"classes":[]},{"id":2648,"url":"https:\/\/xmau.com\/ilpost\/2013\/10\/26\/godel-dio-e-repubblica\/","url_meta":{"origin":616,"position":2},"title":"G\u00f6del, Dio e Repubblica","author":".mau.","date":"26\/10\/2013","format":false,"excerpt":"Stamattina mia moglie mi aveva detto di aver letto qualcosa oggi su Repubblica a riguardo di due ricercatori che avevano \"dimostrato il teorema di G\u00f6del\". Ammetto di non averci fatto troppo caso, non ero nemmeno troppo sveglio. Poi mi \u00e8 capitato di vedere su Facebook la condivisione di questo articolo\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":607,"url":"https:\/\/xmau.com\/ilpost\/2015\/08\/22\/soluzioni-ai-quizzini-di-ferragosto-2015\/","url_meta":{"origin":616,"position":3},"title":"Soluzioni ai quizzini di Ferragosto 2015","author":".mau.","date":"22\/08\/2015","format":false,"excerpt":"Ecco le soluzioni ai quizzini della scorsa settimana! 1. Moltiplicate i puntini Se b fosse 5 oppure 6, la prima cifra del prodotto sarebbe 3. Se b fosse 1, 2 oppure 3, la prima cifra del prodotto sarebbe 0 oppure 1. Dunque b \u00e8 4, e a questo punto \u00e8\u2026","rel":"","context":"In \"quizzini\"","block_context":{"text":"quizzini","link":"https:\/\/xmau.com\/ilpost\/tag\/quizzini\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2658,"url":"https:\/\/xmau.com\/ilpost\/2017\/06\/30\/4-chilometri-cubi-di-rifiuti\/","url_meta":{"origin":616,"position":4},"title":"4 chilometri cubi di rifiuti","author":".mau.","date":"30\/06\/2017","format":false,"excerpt":"Roberto Zanasi (che abita a Modena) ha trovato questo titolo su un giornale locale, ed \u00e8 metaforicamente balzato sulla sedia. Riuscite a vedere al volo cosa c'\u00e8 di strano nell'affermazione \"Vasco, previsti 4 km cubi di rifiuti\"? No, il problema non sono le battute sulle attuali qualit\u00e0 musicali del cantante\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"4km3","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/2017\/06\/4km3.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1503,"url":"https:\/\/xmau.com\/ilpost\/2019\/07\/10\/numeri-felici\/","url_meta":{"origin":616,"position":5},"title":"Numeri felici","author":".mau.","date":"10\/07\/2019","format":false,"excerpt":"una categoria di numeri con propriet\u00e0 facili da studiare... ma non troppo.","rel":"","context":"In \"didattica della matematica\"","block_context":{"text":"didattica della matematica","link":"https:\/\/xmau.com\/ilpost\/tag\/didattica-della-matematica\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/07\/happynumbers.png?resize=350%2C200","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/616","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=616"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/616\/revisions"}],"predecessor-version":[{"id":617,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/616\/revisions\/617"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=616"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}