Il teorema di Zorro

Nel seguire gli aggiornamenti di Monday puzzle, il blog di Alex Bellos, sono rimasta indietro di un mese giusto giusto... e proprio oggi che rischiavo di perdere di vista l'enigma pubblicato il 20 maggio scorso con il titolo Can you solve it? The Zorro puzzle (Riesci a risolverlo? L'enigma di Zorro) – questo perché feedly i post più vecchi di un mese me li segna per default come già letti, devo vedere se è possibile modificare questa impostazione – te ne riporto qui di seguito la traduzione!

Oggi avrai la possibilità di dimostrare un teorema che nessuno ha mai dimostrato prima.

Innanzitutto, l'enigma di base:

Qual è il numero minimo di linee rette da tracciare su una griglia quadrata 3×3 in modo che ogni cella della griglia abbia almeno una delle linee che la attraversano?

L'ho chiamato enigma di Zorro perché mi fa pensare a uno spadaccino che affetta tutte le celle della griglia nel modo più efficiente possibile.

Inoltre mi è arrivato dalla Spagna.

Carlos D'Andrea, dell'Università di Barcellona, ​​mi ha detto che la maggior parte dei suoi studenti più brillanti ha risposto in modo errato.

Passiamo al prossimo quesito:

Qual è il numero minimo di linee rette da tracciare su una griglia quadrata 4×4 in modo che ogni cella della griglia abbia almeno una delle linee che la attraversano?

La soluzione corretta è probabilmente minore rispetto a ciò che risponderesti istintivamente.

Adesso facciamo sul serio. Esiste una soluzione al problema generale:

Qual è il numero minimo di linee rette da tracciare su una griglia quadrata n×n in modo che ogni cella della griglia abbia almeno una delle linee che la attraversano?

Né Carlos né io (né nessun altro, per quanto ne sappiamo) abbiamo esaminato griglie più grandi della 4×4.

Dopo qualche ora è arrivata la soluzione – quella più generale possibile! – che puoi leggere scorrendo la pagina un po' più in basso.

Per la griglia 3×3 la risposta è 2 linee.

Per la griglia 4×4 la risposta è 3 linee.

Grazie al lettore Oliver Slay per la codifica a colori di alcune soluzioni di esempio, compresi i casi 5×5 e 6×6. La sua immagine costituisce una "dimostrazione senza parole" che con qualunque griglia n×n ci si può riuscire con n – 1 linee.