INdAM 2007/2008 Problema 3

[ngshya]

Abbiamo a disposizione piastrelle quadrate di due colori: rosso e blu.

1. In quanti modi posso formare una fila di $ \displaystyle 8 $ piastrelle, in modo che vi sia un numero dispari di piastrelle blu.
2. Quante sono le possibili colorazioni di un pavimento rettangolare formato da $ \displaystyle 7 $ file di $ \displaystyle 8 $ piastrelle ciascuna, tali che in ogni fila da $ \displaystyle 8 $ vi sia un numero dispari di piastrelle blu?
3. Quante sono le possibili colorazioni di un pavimento $ \displaystyle 8\times 8 $ privato di una piastrella in un angolo, tali che in ogni riga ed in ogni colonna vi sia un numero dispari di piastrelle blu?
4. Quante sono le possibili colorazioni di un pavimento $ \displaystyle 8\times 8 $, tali che in ogni riga ed in ogni colonna vi sia un numero dispari di piastrelle blu?

5. Sia $ \displaystyle d $ un numero dispari. Quante sono le possibili colorazioni di un pavimento $ \displaystyle 8\times d $ tali che in ogni riga ed in ogni colonna vi sia un numero dispari di piastrelle blu?

Buon lavoro

[Drago96]

Soluzione 1

Abbiamo 4 casi: 1 blu e 7 rosse; 3 blu e 5 rosse; 5 blu e 3 rosse; 7 blu e 1 rossa
Notiamo che ci basta sommare i primi due casi e raddoppiare.

Nel caso 1 blu e 7 rosse abbiamo 8 possibilità.
Nel caso 3 blu e 5 rosse la possibilità sono $\binom{8}{3}=56$

Dunque le possibilità totali sono 128.

[exodd]

Soluzione 2

Dal punto a, sappiamo che una riga può essere piastrellata in 128 modi diversi.. Dato che le righe sono indipendenti tra loro, i possibili piastrellamenti sono
$ 128^7 $

Soluzione 4,5
In generale, se dobbiamo piastrellare un 8xN in modo che vi siano un numero di piastrelle blu dispari in ogni riga e colonna, allora tasselliamo le prime N-1 righe, così l'N-esima riga è già determinata. Quindi abbiamo
$ 128^{N-1} $ possibili tassellamenti

[exodd]

Soluzione 3

Stavolta, se tasselliamo le 7 righe come fatto prima, l'ottava è determinata, ma non è detto che l'ottava colonna abbia un numero dispari di caselle blu.
Notiamo quindi che tra le 128 combinazioni di una riga ve ne sono 64 che terminano con una casella blu e 64 che terminano con una casella rossa (non è troppo ovvio, ma è abbastanza facile.. dimostratelo )
Se contiamo le possibili tassellazioni dell'ottava colonna, notiamo che $ 2^6 $ di esse fanno sì che ci siano un numero dispari di caselle blu.
Ciò vuol dire che le possibili tassellazioni totali sono
$ 2^664^7=64^8 $


Bonus

Quante sono le possibili tassellazioni di una scacchiera NxM, con N e M numeri naturali maggiori di uno e con la stessa parità, tali che in ogni riga e colonna vi sia un numero dispari di caselle blu?

[ngshya]

Soluzione 3
Stavolta, se tasselliamo le 7 righe come fatto prima, l'ottava è determinata, ma non è detto che l'ottava colonna abbia un numero dispari di caselle blu.
Notiamo quindi che tra le 128 combinazioni di una riga ve ne sono 64 che terminano con una casella blu e 64 che terminano con una casella rossa (non è troppo ovvio, ma è abbastanza facile.. dimostratelo )
Se contiamo le possibili tassellazioni dell'ottava colonna, notiamo che $ 2^6 $ di esse fanno sì che ci siano un numero dispari di caselle blu.
Ciò vuol dire che le possibili tassellazioni totali sono
$ 2^664^7=64^8 $

Ok, anche a me viene così, dunque, credo che ci sia un piccolo errore di battitura nella soluzione ufficiale proposta da loro.

http://www.altamatematica.it/sites/defa ... m07-08.pdf l'ultima pagina.

[exodd]

No, invece se ho capito la soluzione, c'è un'incomprensione nel testo:
nel punto 3) loro non considerano l'ultima riga e l'ultima colonna come.. riga o colonna.. Il testo esatto dovrebbe essere questo:
"Quante sono le possibili colorazioni di un pavimento 8×8 privato di una piastrella in un angolo, tali che in ognuna delle prime 7 righe ed in ognuna delle prime 7 colonne vi sia un numero dispari di piastrelle blu?

[ngshya]

Ah, ok... beh, pensa a quelli che erano in gara... farsi fregare dei punti così!

Soluzione 4,5
In generale, se dobbiamo piastrellare un 8xN in modo che vi siano un numero di piastrelle blu dispari in ogni riga e colonna, allora tasselliamo le prime N-1 righe, così l'N-esima riga è già determinata. Quindi abbiamo
$ 128^{N-1} $ possibili tassellamenti

Sicuro? Prendiamo il caso N=3. Se la colorazione fosse possibile contandando le piastrelle per righe avremo $ d_1+d_2+d_3 $ che fa un numero dispari (essendo $ d_i $ dispari), contando per colonne avremo $ b_1+b_2+b_3+...+b_8 $ che fa un numero pari (perché anche i $ b_i $ sono dispari).

[exodd]

uhm.. in effetti.. Allora probabilmente anche la soluzione del punto 3 è sbagliata..

Comunque il punto 4 è ancora valido
E' solo il tuo bonus ad essere.. impossibile.. Letteralmente

[ngshya]

No, in quel caso funziona perché hai un numero pari. Basta mettere la riga con sette piastrelle all'inizio e hai $ \displaystyle \binom{7}{1}+\binom{7}{3}+\binom{7}{5}+\binom{7}{7}=2^{6} $ possibilità per la prima riga. $ \displaystyle 2^7 $ per tutte le righe che seguono lasciando l'ultima riga che si autocompleta. E notiamo che l'ultima riga ha sempre un numero dispari di piastrelle blu perché contando le prime $ \displaystyle 7 $ righe abbiamo un numero dispari di dispari, contando le colonne quando abbiamo già finito di tassellare abbiamo un numero pari di dispari e quindi per sottrazione nell'ultima riga c'è un numero dispari di piastrelle blu. Questo risponde praticamente anche al tuo bonus.

[exodd]

Sì, me ne sono accorto solo ora..
Beh, prova a dare una risposta al mio bonus, allora!

[ngshya]

Bonus
Quante sono le possibili tassellazioni di una scacchiera NxM, con N e M numeri naturali maggiori di uno e con la stessa parità, tali che in ogni riga e colonna vi sia un numero dispari di caselle blu?

Ok... Allora per di casi in cui uno dei due numeri è pari e l'altro è dispari abbiamo detto che è impossibile e quindi rimangono i casi in cui o sono entrambi pari o sono entrambi dispari.

Supponiamo che sia $ \displaystyle N $ il numero delle righe ed $ \displaystyle M $ il numero delle colonne.

Per colorare una riga di lunghezza $ \displaystyle M $ nel modo richiesto dal problema ci sono $ \displaystyle 2^{M-1} $ possibilità.

Adesso possiamo colorare le prime $ \displaystyle N-1 $ righe in $ \displaystyle (2^{M-1})^{N-1}=2^{(M-1)(N-1)} $ modi.

Vediamo adesso l'ultima riga.
Se N fosse un numero pari, allora alla fine avremo un numero pari di piastrelle blu, ma fino all' $ \displaystyle N-1 $ esima riga abbiamo un numero dispari di piastrelle blu, e quindi l'ultima riga che serve da auto-completamento ha un numero dispari di piastrelle blu (e naturalmente è quasi ovvio che data ogni colonna di lunghezza $ \displaystyle N-1 $ c'è sempre un modo solo per completarla facendola rispettare le condizioni del problema).
Nel caso in cui $ \displaystyle N $ fosse dispari, avremo alla fine un numero dispari di piastrelle blu, fino all' $ \displaystyle N-1 $ un numero pari di piastrelle blu e quindi anche in questo caso l'ultima riga ha un numero dispari di piastrelle blu.

[ngshya]

Stavo pensando... lo stesso problema forse può essere generalizzato anche nello spazio.

[exodd]

Uhm.. Penso proprio di sì.. E se non mi sbaglio la formula diviene $ 2^{(x-1)(y-1)(z-1)} $stando attenti alle parità di x,y e z però..