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

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

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

Messaggioda mr96 » 26/08/2016, 11:52

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?
mr96
 
Messaggi: 1487
Iscritto il: 11/02/2014, 20:37

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

Messaggioda matematto » 26/08/2016, 17:53

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.
Avatar utente
matematto
 
Messaggi: 137
Iscritto il: 27/11/2014, 17:12

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

Messaggioda Rho33 » 26/08/2016, 18:03

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à!
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

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

Messaggioda mr96 » 27/08/2016, 0:42

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 :lol:
mr96
 
Messaggi: 1487
Iscritto il: 11/02/2014, 20:37

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

Messaggioda alexthirty » 28/08/2016, 13:17

C'è una condizione da imporre sulle dimensioni...
alexthirty
 
Messaggi: 79
Iscritto il: 27/11/2013, 14:49


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti