griglie e fiammiferi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

griglie e fiammiferi

Messaggio da ma_go »

rigiro volentieri da scienzematematiche un problema di fry.

su un tavolo ci sono dei fiammiferi disposti a griglia quadrata $n\times n$ (come in figura, nel caso $n = 4$).

Codice: Seleziona tutto

 _ _ _ _
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
arriva un piccolo piromane, e accende una certa quantita` di fiammiferi, che poi butta. poi riguarda la griglia, e osserva che non c'e` piu` nessun quadrato con tutto il perimetro integro (non solo quadrati $1\times 1$, ma anche $2\times 2$, etc.).
quanti fiammiferi ha bruciato, come minimo?
nic.h.97
Messaggi: 195
Iscritto il: 19 giu 2012, 19:24

Re: griglie e fiammiferi

Messaggio da nic.h.97 »

Per il caso $ n $ pari
Si può' dimostrare che come minimo brucerò $ \tfrac{n^2}{2}+1 $ fiammiferi.
Per la dimostrazione aprofitterò del mio bellissimo disegno fatto con un potentissimo strumento di lavoro(paint) ... quindi perdonate il brutto disegno.
-1)Allora , consideriamo un generico quadrato $ n*n $ , ora , se voglio bruciare dei fiammiferi in modo che tutti i quadrati $ 1x1 $ all'interno del quadratone scompaiano (nel modo più vantaggioso possibile) , dovro' necessariamente bruciare $ 1 $ fiammifero per ogni $ 2 $ quadratini . In totale ho $ n*n $ quadrati da $ 1 $ e quindi necessariamente ne brucerò $ \tfrac{n^2}{2} $.
Il fiammifero che vado a bruciare è $ sempre $ all'interno del quadratone $ n*n $ , infatti , se prendo un fiammifero al perimetro , esso mi permetterà di eliminare solo $ 1 $ quadrato $ 1x1 $ e non $ 2 $ quadrati$ 1*1 $ e questo risulta ovviamente svantaggioso.

-2)Ora , però , se devo far scomparire il quadratone $ n*n $ dovrò necessariamente prendere un fiammifero al perimetro , quindi brucerò $ \tfrac{n^2}{2}+1 $ fiammiferi .

-3) dimostriamo che con $ \tfrac{n^2}{2}+1 $ fiammiferi posso ottenere la tesi , con una determinata disposizione dei fiammiferi da bruciare che cercherò di illustrare il meglio possibile.
(*) Allora , consideriamo un generico quadrato $ a*a $ dove $ 1<a<n $ , esso ha sicuramente un lato all'interno del quadratone . Ora posso "raccattare" i fiammiferi bruciati in 1) per non far esistere nessun quadrato $ a*a $ , con la seguente disposizione:
Considerate il disegno sottostante :
Allora la disposizione conta di un alternarsi di 2 sottodisposizioni ( a e b) come sotto in figura .
Ogni quadrato $ a*a $ avrà sicuramente un lato corrispondente ad un fiammifero rosso ( bruciato ) e quindi non esisterà nessun quadrato $ a*a $ , poichè verrà "interrotto" da un fiammifero in rosso.
Ora , la disposizione che ho fatto deve rispettare le seguenti condizioni : consideriamo il quadrato disposto in questo modo ( wlog : girandolo è la stessa situazione )
, ora il lato verticale deve essere tale che $ 2k+1(m)=n $ dove $ 2k $ sono tutte le disposizioni "a" e $ m $ sono tutte le disposizioni "b". $ m $ può essere $ = k+1 , k , k-1 $. notare che posso iniziare , dal lato più basso al lato più alto , a disporre sia con "a" chè con "b" . La scelta è ininfluente, il risultato è lo stesso.
Quindi $ 2k+1(m)=n $ ha soluzioni per qualsiasi $ n $ naturale ( non penso che serva nemmeno dimostrarlo ) .
Il lato orizzontale (wlog) ovviamente non influisce.
Infine , la soluzione , per $ n $ pari è $ \tfrac{n^2}{2}+1 $ . poichè devo aggiungere il fiammifero esterno al perimetro per eliminare il quadratone $ n*n $
Per $ n $ dispari , se conto i fiammiferi rossi ottenuti con la disposizione precedentemente illustrata , ottengo $ \tfrac{n^2+1}{2} $... potrebbe essere dimostrato per induzione , ma è troppo lungo aggiungerlo. Infine aggiungo il fiammifero per bruciare il quadratone e quindi $ \tfrac{n^2+1}{2}+1 $ come minimo
Allegati
Immagine.png
Immagine.png (6.48 KiB) Visto 2739 volte
nic.h.97
Messaggi: 195
Iscritto il: 19 giu 2012, 19:24

Re: griglie e fiammiferi

Messaggio da nic.h.97 »

Scusate , mi sono accorto che nelle linee del modo di disporre "b" ho aggiunto dei fiammiferi bruciati di troppo.(editata immagine)
E poi un'altra cosa , per $ n $ dispari la soluzione non è $ \tfrac{n^2+1}{2}+1 $ , ma $ \tfrac{n^2-1}{2}+1 $ .
Erroneamente avevo considerato distinti i casi "bruciamo tutti i quadratini da 1 " e bruciamo il quadratone.
Infatti posso considerare il quadrato $ nxn $ , per $ n $ dispari, composto da $ n^2-1 $ quadrati $ + 1 $ quadrato.
I primi $ n^2-1 $ posso accoppiarli tutti e quindi necessariamente brucerò fiammiferi all'interno del perimetro del quadrato $ nxn $, invece , per il quadrato rimanente posso bruciare un fiammifero al perimetro! E quindi cosi' tolgo subito il caso del quadrato perimetro massimo.
Ora dimostro che effetivamente con $ \tfrac{n^2-1}{2}+1 $ funziona , ma prima devo fare delle considerazioni:

Prima di tutto , prima ho affermato che $ 2k+m=n $ ( e $ m=k+1,k,k-1 $) . Questo perchè?
Allora , guardiamo un lato verticale del quadrato , allora disponendo come ho precedentemente illustrato possono presentarsi $ 4 $ casi :
$ A,B,A,B.......,B,A $ <===== $ m=k-1 $
$ B,A,B,A........A,B $ <===== $ m=k+1 $
$ A,B,A...........A,B $ <===== $ k=m $
$ B,A,B..........B,A $ <===== $ k=m $
$ A $ rappresenta $ 2 $ linee disposte nel modo "a" e $ B $ rappresenta $ 1 $ linea disposta nel modo "b"
Mentre $ k $ rappresenta tutte le $ A $ e $ m $ rappresenta tutte le $ B $.
Allora , gli ultimi $ 2 $ casi sono identici(ruotare il quadrato di $ 180° $). Dimostriamo che $ 2k+m=n $ per $ m=k+1,k,k-1 $ ha soluzione per ogni naturale , il chè equivale a dire che posso usare questo tipo di disposizione per qualsiasi quadrato.
Allora :
$ k=m \implies 3k=n $ soluzione per qualsiasi $ n \equiv 0 \pmod{3} $
$ k=m+1 \implies 3k+1=n $ soluzione per qualsiasi $ n \equiv 1 \pmod{3} $
$ k=m-1 \implies 3k-1=n $ soluzione per qualsiasi $ n \equiv 2 \pmod{3} $.

Ora , per il quadrato $ nxn $ , consideriamo i quadratini da $ 1 $($ n^2 $) , allora , per $ n^2-1 $ posso bruciare i fiammiferi come ho precedentemente illustrato , però ne rimarrà fuori $ 1 $ . Facciamo che questo $ 1 $ che rimane fuori stia su una linea "b" .
Ho $ 3 $ casi :
(*)la linea "b" non esiste $ \implies n=2 $
(**)La linea o le uniche $ 2 $ linee "b" stanno nella prima riga o nell'ultima del quadrato $ \implies n=3 n=4 $
(***)Esiste almeno una linea "b" all'interno del quadrato .$ \implies n>4 $

Il caso (*) non ci interessa analizzarlo in quanto $ n $ pari ( già analizzato)
Il caso (**) può essere risolto come nella figura sottostante
il caso (***) può essere risolto come nella figura sottostante ( c'è il caso particolare $ n=5 $ , ma ovviamente per ogni n dispari posso ricondurmi a questo caso)
Allegati
22222222.png
22222222.png (17.57 KiB) Visto 2738 volte
Rispondi