I quadrati da distruggere

Osservate la figura che segue: 40 stuzzicadenti sono sistemati su un piano in modo da formare lo schema di una scacchiera di ordine quattro.

Il problema consiste nel rimuovere il più piccolo numero di stuzzicadenti necessario a spezzare il perimetro di ogni quadrato. “Ogni quadrato” significa non solo i 16 piccoli quadratini con un solo stuzzicadente per lato, ma anche i nove quadrati di lato due stuzzicadenti, i quattro quadrati di lato tre stuzzicadenti e quello grande di lato quattro stuzzicadenti che costituisce il “perimetro esterno”. In tutto si hanno quindi 30 quadrati da “distruggere”.

In generale per una griglia quadrata di ordine N, ovvero per scacchiere quadrate di N stuzzicadenti per lato, il numero totale dei quadrati distinti è pari alla somma degli interi al quadrato da uno ad N, ovvero in formula:

N·(N + 1)·(2·N + 1)/6

Per un quadrato siffatto quanti stecchini occorre rimuovere?

Soluzione

Prima di rispondere alla domanda generale con quadrati di ordine N, cerchiamo quella particolare quando il suddetto ordine è pari a quattro, come il quadrato riportato nella figura del testo. E prima di rispondere a questa vediamo cosa accade anche nei quadrati di ordine inferiore: la scacchiera 1·1 è un caso banalissimo in quanto è immediato vedere che per spezzare il perimetro basta togliere un solo stuzzicadente; è anche facile provare graficamente che basta rimuovere solamente tre stuzzicadenti dalla scacchiera 2·2 per distruggere tutti i quadtati, e sei stuzzicadenti dalla scacchiera 3·3. Il caso di ordine quattro proposto è alquanto più complesso da risultare interessante: a conti fatti il minimo numero di stuzzicadenti da rimuovere in questo caso è nove! Un modo per far questo è mostrato nella parte interna del quadrato 4·4 colorato in bianco della figura che segue:

Per provare che tale numero è il minimo osserviamo che le otto caselle colorate in grigio non hanno lati in comune fra loro; per poter spezzare i perimetri di tutte e otto le caselle, occorre rimuovere, quindi, almeno otto segmenti unitari. Lo stesso ragionamento si applica alle restanti otto caselle della scacchiera lasciate in nero. Possiamo tuttavia distruggere tutte le 16 caselle 1·1 estromettendo i medesimi otto segmenti se vengono rimossi i lati in comune a caselle adiacenti in modo tale che ciascun segmento cancellato distrugge simultaneamente una casella grigia ed una nera. Inoltre nel modo raffigurato sopra sono stati distrutti contemporaneamente anche tutti i perimetri dei nove quadrati 2·2 e dei quattro 3·3. Ma lo stesso non possiamo dire del quadrato più grande 4·4, perchè nessuno dei segmenti rimossi si trova sul perimetro esterno della scacchiera bianca, visto che questi non sono tali da essere in comune a due caselle adiacenti. Ne deduciamo che occorre togliere almeno un altro segmento su tale perimetro e, quind,i almeno nove devono essere i segmenti da rimuovere in una scacchiera di ordine quattro, per distruggere tutti e 30 i quadrati che si generano.

La stessa argomentazione prova che ogni quadrato di ordine pari ammette una soluzione almeno uguale a 1 + N²/2, ove N indica l’ordine del quadrato. Una dimostrazione per induzione è implicita nella procedura eseguita nell’illustrazione stessa e riportata in giallo attorno alla scacchiera 4·4. Basta, infatti, inserire una tessera di domino, ovvero una “bicasella” 2·1 formata da una casella grigia e una nera senza lo stuzzicadente separatore, nella casella perimetrale aperta sul bordo della scacchiera 4·4 e poi proseguire la catena di tessere lungo il bordo stesso così come indicato in giallo nella figura precedente. Ciò dà una soluzione minima di 19 stuzzicadenti da rimuovere in una scacchiera 6·6. La stessa procedura, non riportata in figura, viene applicata ancora una volta per ottenere la soluzione minima di 33 stuzzicadenti per la scacchiera di ordine otto. È ovvio che questa stessa procedura può essere ripetuta indefinitamente, e che ogni volta il bordo formato dalle tessere del domino alza la casella perimetrale aperta di due unità in entrambe le direzioni, così come indica la freccia colorata in verde.

Sulla scacchiera 5·5 la situazione è complicata dal fatto che c’è una casella grigia in più rispetto alle nere (13 sono grigie e 12 nere). Occorrerà allora rimuovere almeno 12 segmenti, per distruggere simultaneamente 12 caselle grigie e 12 bianche, e ciò forma le 12 tessere di domino. Se a questo punto la casella grigia non demolita ancora fosse sul bordo esterno dell’intera scacchiera, basterebbe estromettere un solo segmento per distruggere anche tale quadratino di lato unitario assieme al quadrato più grande 5·5. Ciò suggerisce che le scacchiere di ordine dispari debbano ammettere una soluzione minima di (N² + 1)/2 di stecchini da eliminare, per distruggere tutti i quadrati generati, ma per fare ciò, tuttavia, le tessere di domino dovrebbero essere disposte in modo tale da non spezzare mai un quadrato di ordine maggiore di uno. Si può provare che ciò non è mai possibile, cosicché la soluzione minima diventa 1 + (N² + 1)/2 e quindi per la scacchiera di ordine cinque occorre estromettere 14 stuzzicadenti, per demolire i perimetri di tutti i quadrati. Nella figura sottostante è presentata, colorata in bianco, una procedura che ottiene questo minimo per tale scacchiera e, colorata in giallo, quella per tutti i quadrati di ordine dispari superiore.

Affrontando l’analogo problema di ottenere configurazioni distruggendo tutti i possibili rettangoli distinti generati da scacchiere quadrate, si è visto che la tessera ad “L” gioca, in questo problema, lo stesso ruolo che la tessera di domino gioca nel problema in cui non compaiono quadrati, che sono considerati casi “particolari” dei rettangoli, ora risolto. Per scacchiere di ordine da due a 12, il minimo numero di stuzzicadenti che devono essere soppressi per demolire tali rettangoli sono rispettivamente tre, sette, 11, 18, 25, 34, 43, 55, 67, 82 e 97. La figura che segue mostra una configurazione relativa alla scacchiera di ordine otto.