[L03] Celle di memoria (SNS 2016-2)

[mr96]

Ometto l'ambientazione dato che non è così fondamentale.

i) Data una tabella [tex]a \times l[/tex] si riempie ogni casella con uno $0$ o con un $1$ in modo tale che ogni riga e ogni colonna abbia somma dispari. Quante diverse configurazioni è possibile creare?

ii) Dato un parallelepipedo $a \times l \times p$ si riempie ogni "cubetto" di lato $1$ con uno $0$ o un $1$ in modo che in tutte e $3$ le direzioni (altezza, larghezza, profondità) caselle contigue abbiano somma dispari. In quanti modi è possibile farlo?

[matematto]

Testo nascosto:

i) Dimostriamo che le configurazioni che soddisfano la tesi sono $2^{(a-1)(l-1)}$

Consideriamo una generica tabella $a \times l$ a cui sono state rimosse l'ultima riga e l'ultima colonna. Sarà dunque di dimensioni $(a-1) \times (l-1)$.
Avremo che per ogni configurazione di questa tabella si potrà sempre arrivare a una e una sola configurazione di tabella $a \times l$ che rispetta la tesi.
Basta procedere nel seguente modo:

• Si riempiono le prime $l-1$ caselle dell'$a-$esima riga con un $1$ o uno $0$ a secondo che la colonna corrispondente abbia rispettivamente somma pari o dispari.
  Questa scelta è univoca e se non si rispettasse non si rispetterebbe la tesi.
• Si riempiono in modo analogo tutte le $a$ caselle dell'$l-$esima colonna. Analogamente a prima anche qui le scelte sono univoche.

Per ogni casella della tabella $(a-1) \times (l-1)$ possiamo dunque scegliere indifferentemente se mettere un $1$ o uno $0$, Ci saranno dunque $2^{(a-1)(l-1)}$ configurazioni.

ii) Del tutto analogamente a prima le configurazioni che soddisfano la tesi sono $2^{(a-1)(l-1)(p-1)}$

Si dovranno considerare i parallelepipedi $a \times l \times (p-1)$ e per quanto dimostrato prima sono $\left(2^{(a-1)(l-1)}\right)^{(p-1)}=2^{(a-1)(l-1)(p-1)}$. A questo punto basterà riempire le ultime $a*l$ caselle in modo unvoco come fatto in precedenza.

[Rho33]

Fatto abbastanza in fretta ma dovrebbe essere:

Testo nascosto:

$2^{(a-1) \cdot (l-1)}$ e $2^{(a-1) \cdot (l-1) \cdot (p-1)}$

EDIT: Anticipato da matematico di un nulla, comunque sì! Chiaramente il risultato non cambia se tutte le righe/colonne devono essere pari. Attenzione che $a,l$ devono avere la stessa parità!

[mr96]

C'è qualcosa che non mi quadra nella soluzione: se io inizio una 2x3 con 1 e 0 nella prima riga e completo seguendo lo schema di matematto ho una cosa tipo

1 0 0
0 1 0

Dove l'ultima colonna ha somma pari... Dove sbaglio?

Edit: ho visto dopo il messaggio di Rho che spoilera il tutto

[alexthirty]

C'è una condizione da imporre sulle dimensioni...