La scacchiera malata
La scacchiera malata
Un bel problemino pre-cesenatico:
Una classica scacchiera 8x8 viene attaccata da 7 microbi, ognuno dei quali si posiziona dentro un quadratino.
Se un quadratino è attaccato dai microbi da almeno due lati, allora dopo un secondo scatta la riproduzione e si trova un antipatico microbo anche in questa casella!
Riusciranno i microbi ad occupare tutta la scacchiera?
Una classica scacchiera 8x8 viene attaccata da 7 microbi, ognuno dei quali si posiziona dentro un quadratino.
Se un quadratino è attaccato dai microbi da almeno due lati, allora dopo un secondo scatta la riproduzione e si trova un antipatico microbo anche in questa casella!
Riusciranno i microbi ad occupare tutta la scacchiera?
Dopo 2 minuti di riflessione...
Affinchè una casella possa essere infettata è necessario che sia presente un microbo nella sua colonna e un altro nella sua riga. Oppure bastano (in casi particolari) anche 2 microbi sulla sua riga o sulla sua colonna. Visto però che quest'ultima configurazione è chiaramente svantaggiosa (penso), non rimane che disporre i microbi su righe e colonne differenti...
La migliore configurazione con 7 microbi copre 7 righe e 7 colonne, per cui in ogni caso rimangono delle caselle non infette (che direi sono 15)...
Non mi meraviglierebbero clamorose smentite
Affinchè una casella possa essere infettata è necessario che sia presente un microbo nella sua colonna e un altro nella sua riga. Oppure bastano (in casi particolari) anche 2 microbi sulla sua riga o sulla sua colonna. Visto però che quest'ultima configurazione è chiaramente svantaggiosa (penso), non rimane che disporre i microbi su righe e colonne differenti...
La migliore configurazione con 7 microbi copre 7 righe e 7 colonne, per cui in ogni caso rimangono delle caselle non infette (che direi sono 15)...
Non mi meraviglierebbero clamorose smentite
Parlare oscuramente lo sa fare ognuno, ma chiaro pochissimi. (G. Galilei)
Credo non ce la facciano i tuoi microbi (perchè ti stanno così antipatici?)
Per occupare tutta la scacchiera è necessario che ci sia almeno un microbo in ogni riga e un microbo in ogni colonna. Quindi ne servirebbero almeno 8 (disposti per esempio sulla diagonale della scacchiera)
Tentiamo ora di spiegare perchè ne serve almeno uno per riga e almeno uno per colonna.
Supponendo che un microbo voglia riprodursi nella riga superiore, la casella figlia dev'essere contagiata da un altro microbo non della stessa riga (che non avrebbe nessun lato in comune con la casella figlia) e quindi o della riga superiore o della riga ancora superiore (a patto che che sia allineato con l'altro microbo "genitore").
Nel primo caso si vede appunto come sia necessario un microbo per riga ed equivalentemente per colonna.
Nel secondo caso dimostriamo che per i 7 microbi è impossibile occupare l'intera scacchiera.
Infatti perché i microbi possano conquistare una riga n in partenza vuota devono possedere un microbo nella riga n+1 e l'intera riga sottostante n-1.
Ma se possedessero l'intera riga n-1 allora sarebbero riusciti ad impossessarsi anche di una casella della colonna che era vuota in partenza (visto che i 7 microbi lasciano una riga ma anche una colonna sane, almeno all'inizio). Ma questo è impossibile, perché per conquistarla avrebbero avuto bisogno almeno di due microbi sulla stessa riga, e quindi avrebbero dovuto essere almeno in 8.
Spero di essere stato chiaro...
Per occupare tutta la scacchiera è necessario che ci sia almeno un microbo in ogni riga e un microbo in ogni colonna. Quindi ne servirebbero almeno 8 (disposti per esempio sulla diagonale della scacchiera)
Tentiamo ora di spiegare perchè ne serve almeno uno per riga e almeno uno per colonna.
Supponendo che un microbo voglia riprodursi nella riga superiore, la casella figlia dev'essere contagiata da un altro microbo non della stessa riga (che non avrebbe nessun lato in comune con la casella figlia) e quindi o della riga superiore o della riga ancora superiore (a patto che che sia allineato con l'altro microbo "genitore").
Nel primo caso si vede appunto come sia necessario un microbo per riga ed equivalentemente per colonna.
Nel secondo caso dimostriamo che per i 7 microbi è impossibile occupare l'intera scacchiera.
Infatti perché i microbi possano conquistare una riga n in partenza vuota devono possedere un microbo nella riga n+1 e l'intera riga sottostante n-1.
Ma se possedessero l'intera riga n-1 allora sarebbero riusciti ad impossessarsi anche di una casella della colonna che era vuota in partenza (visto che i 7 microbi lasciano una riga ma anche una colonna sane, almeno all'inizio). Ma questo è impossibile, perché per conquistarla avrebbero avuto bisogno almeno di due microbi sulla stessa riga, e quindi avrebbero dovuto essere almeno in 8.
Spero di essere stato chiaro...
Lol, scusa. Siccome il problema è stato dichiarato pre-Cesenatico, davo per scontato che fossi un partecipante. Altrimenti sarei stato meno "duro".MateCa ha scritto:Per me vale di sicuro 0 punti, visto che a Cesenatico al massimo ci vado in vacanza
Cmq non ho il tempo di fare un'argomentazione rigorosa...Lascio agli olimpici l'onere
Infetta tutta la scacchiera, tranne una riga di quelle centrali.Zok ha scritto:Per occupare tutta la scacchiera è necessario che ci sia almeno un microbo in ogni riga e un microbo in ogni colonna.
La scacchiera si infetta interamente in 1 secondo, ma inizialmente non tutte le righe avevano un microbo.
-
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Abbastanza noto... c'è una dimostrazione molto elegante
OT: che sofferenza non avere internet a casa...
Ciao a tutti!
[/size]hint: considerare il perimetro della zona infetta
OT: che sofferenza non avere internet a casa...
Ciao a tutti!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO