Problema di combinatoria - Test SGSS

[Feed1]

Salve,
Oggi ho letto questo problema:

Consideriamo una scacchiera 4x4. Vogliamo mettere nelle sue caselle i numeri 0,1,2,3 in modo tale che la somma dei numeri di ogni riga e di ogni colonna sia un multiplo di 4. In quanti modi è possibile farlo?

In generale i problemi di combinatoria che si svolgono su una scacchiera mi rendono tutto più difficile.
So che affinchè la somma di una quaterna sia un multiplo di 4 deve necessariamente esserci una quaterna che ho scritto sotto oppure una sua permutazione.

- Le quaterne la cui somma è multiplo di 4 sono 10: 0000 - 1111 - 1102 - 1300 - 2200 - 2222 - 2231 - 2330 - 1331 - 3333 ( dovrebbero essere tutte)
- Le combinazioni totali (anche se forse qui è meglio dire disposizioni) dovrebbero essere \(\displaystyle 4^{16} \) perchè ad ogni casella posso sempre scegliere fra quattro possibili numeri
- Le 'combinazioni' possibili (quelle che si attengono alla traccia) sono quindi 64 (cioè tutte le permutazioni delle quaterne scritte)

Per il resto non so proprio come andare avanti.

Spero di trovare anche solo un 'indizio' per risolverlo. Grazie in anticipo a tutti

[axpgn]

Te ne manca una: $0000$ ...

[Feed1]

Grazie, non sono mai sicuro che 0 venga inteso come multiplo di tutti i numeri, però di regola dovrebbe essere così. Comunque ora correggo.

[axpgn]

Lo zero è sicuramente multiplo di tutti gli interi quindi a meno di esplicita esclusione deve essere considerato ... IMHO ...
Peraltro con $0000$ oltre ad avere le quattro scacchiere "uniformi" hai la garanzia che qualsiasi di quelle combinazioni tu scelga per una riga (e qualsiasi permutazione della stessa) puoi sempre riempire il resto con gli stessi numeri ...
Un metodo sistematico (ma laborioso) per "costruirle" tutte l'avrei trovato, troppo lungo però ...

[Feed1]

Bè se vuoi mostrare il tuo ragionamento io non ho nulla in contrario

[orsoulx]

Beh! Considerando tutte le caselle distinguibili, cioè senza operare riduzioni per simmetrie, questo problema, che a prima vista mi pareva troppo complicato per le mie possibilità, si è invece rivelato una sorta di uovo di Colombo.

Il numero di soluzioni è 262144.

Ciao

[axpgn]

@feed
Troppo lungo, anche per spiegarlo ... ... avevo iniziato ma ho lasciato perdere ...

Una cosa che è notato è una certa simmetria ... chissà se orsoulx l'ha utilizzata nel suo ragionamento ...

Poniamo $a'=0$ e $a''=2$ e poi $z'=1$ e $z''=3$ allora le "righe" (e "colonne") avranno le seguenti forme:

$2a'+2a', 2a''+2a'', 2a'+2a'', 2a'+(z'+z''), 2a''+(z'+z'')$ e le duali scambiando $a$ con $z$

... speravo di ricavarci qualcosa ...

Cordialmente, Alex

[orsoulx]

@Alex
è moooolto più semplice.... e il risultato numerico è un megahint
Ciao

[axpgn]

Penso di aver capito ma non ho verificato ...

$4^9$ ovvero tutti i modi in cui puoi disporre i quattro numeri in una scacchiera $3 xx 3$ tanto poi completi col quarto che esiste sempre ed è unico ... non ho ancora capito come si dimostra che le "quarte" siano corrette ... o meglio che l'ultimo "quadratino" sia lo stesso per le due "quarte" ...

Cordialmente, Alex

[orsoulx]

@Alex

Nel settimo quadratino deve esserci la cifra, unica ed esistente, che porta ad un multiplo di 4 la somma delle 15 già inserite.

Ciao

[Feed1]

:O... Non ci sarei mai arrivato Comunque grazie per l'aiuto ad entrambi

EDIT
Non sono riuscito a capire la 'dimostrazione' del perchè il settimo quadratino esiste sempre...

[axpgn]

Poniamo sia $Q$ la somma dei nove numeri della scacchiera $3 xx 3$, chiamiamo $c_1, c_2, c_3$ i primi tre numeri della quarta colonna (ovvero i "quarti" delle prime tre righe) e $r_1, r_2, r_3$ i primi tre numeri della quarta riga (ovvero i "quarti" delle prime tre colonne).
Avremo che $Q+c_1+c_2+c_3=R_3$ dove $R_3$ è la somma dei numeri che compongono le prime tre righe (e multiplo di quattro); avremo anche che $Q+r_1+r_2+r_3=C_3$ dove $C_3$ è la somma dei numeri che compongono le prime tre colonne (e anche questo è multiplo di quattro).
Proseguendo avremo $R_3+r_1+r_2+r_3+x=T$ dove $T$ è la somma di tutti e sedici i numeri e $x$ rappresenta il "settimo" (o "sedicesimo" se preferite ... ); avremo anche $C_3+c_1+c_2+c_3+y=T$ dove $y$ è sempre il "settimo" (non so ancora se è uguale a $x$ quindi lo denomino diversamente).
Uguagliando otteniamo $R_3+r_1+r_2+r_3+x=C_3+c_1+c_2+c_3+y$ e sostituendo $Q+c_1+c_2+c_3+r_1+r_2+r_3+x=Q+r_1+r_2+r_3+c_1+c_2+c_3+y$, semplifichiamo e ... voilà! $x=y$, è lo stesso!.

[Feed1]

Grazie mille sei stato molto chiaro