Quizzino della domenica: carri armati

Un carro armato è nascosto in un quadrato di una scacchiera 9×9 e un bombardiere deve distruggerlo, lanciandogli delle bombe. Ogni bomba colpisce una singola casella: per distruggere il carro armato occorre colpirlo due volte, ma dopo che è stato colpito la prima volta esso si muove in una casella adiacente. Inoltre il bombardiere non ha la possibilità di capire se il carro armato è stato colpito oppure no.
Un pilota metodico potrebbe spazzare due volte le 81 caselle e assicurarsi così di aver colpito il carro armato: si può fare di meglio oppure no?

(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p180.html; la risposta verrà postata lì il prossimo mercoledì. Problema tratto dalle Olimpiadi Matematiche russe 2015, vedi Tanya Khovanova)

8 comments

  1. Chiamo pari le caselle di indice (i, j) con i+j numero pari. Queste comprendono le caselle d’angolo e le diagonali. Siano dispari le altre.
    E’ chiaro che il carro armato, dopo essere stato colpito la prima volta, cambia classe di parità.
    Il cannoniere può sparare dapprima su tutte le caselle dispari (perché sono una di meno e risparmio un colpo), poi su tutte le pari e poi ancora su tutte le dispari.
    Se il carro armato parte da una casella pari, lo colpisco sicuramente nel secondo e terzo round di bombardamenti.
    Se invece parta da una dispari, lo si distrugge tra il primo e il secondo round.

    Il totale dei colpi nel caso peggiore è 81 + 40 = 121.

    • In altre parole: bombarda le bianche, poi le nere, poi le bianche (?)

    • Dimostro che è il minimo.
      Distribuiamo 120 colpi sulla griglia e vediamo che il carro armato si salva.
      Naturalmente ogni casella deve ricevere almeno un colpo, cosicché 81 sono già sistemati e ne rimangono da assegnare 39.
      Ora, posso tassellare la griglia con 40 tessere di domino 1×2 lasciando fuori un angolo. Per il principio dei cassetti, almeno una di queste tessere non riceverà il colpo addizionale. Perciò avrò due caselle adiacenti che ricevono un solo colpo ciascuna.
      Il carro armato deve posizionarsi su quella delle due che sarà colpita per seconda, poi spostarsi sull’altra: la strategia fallisce.

  2. Definisca “adiacente”, dacché io lo avevo inteso nel senso della mossa del re, ritenendo il problema impossibile. Dopodiché il Suo aiutino mi ha fatto capire che non è la mossa del re, bensì quella di una torre azzoppata.

    • Per un matematico, e presumo anche per un latinista, “adiacente” implica che il contatto non sia un semplice punto ma almeno un segmento.

    • Quando ero ragazzo c’erano il Carrarmato (cioccolato al latte) e il Cingolato (cioccolato bianco) Perugina