Problema di combinatoria - Test SGSS

Messaggioda Feed » 28/03/2017, 14:30

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 :)
Ultima modifica di Feed il 29/03/2017, 16:58, modificato 4 volte in totale.
Feed
Starting Member
Starting Member
 
Messaggio: 4 di 16
Iscritto il: 05/02/2017, 20:06

Re: Problema di combinatoria

Messaggioda axpgn » 28/03/2017, 14:56

Te ne manca una: $0000$ ... :-D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 7870 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Problema di combinatoria

Messaggioda Feed » 28/03/2017, 17:35

Grazie, non sono mai sicuro che 0 venga inteso come multiplo di tutti i numeri, però di regola dovrebbe essere così. Comunque ora correggo.
Feed
Starting Member
Starting Member
 
Messaggio: 5 di 16
Iscritto il: 05/02/2017, 20:06

Re: Problema di combinatoria

Messaggioda axpgn » 28/03/2017, 17:51

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 ... :D
Un metodo sistematico (ma laborioso) per "costruirle" tutte l'avrei trovato, troppo lungo però ... :D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 7875 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Problema di combinatoria - Test SGSS

Messaggioda Feed » 29/03/2017, 16:47

Bè se vuoi mostrare il tuo ragionamento io non ho nulla in contrario :-D
Feed
Starting Member
Starting Member
 
Messaggio: 6 di 16
Iscritto il: 05/02/2017, 20:06

Re: Problema di combinatoria - Test SGSS

Messaggioda orsoulx » 29/03/2017, 17:15

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.
Testo nascosto, fai click qui per vederlo
Il numero di soluzioni è 262144.

Ciao
Stephen Wolfram non mi è simpatico, anche perché il malefico Wolfram|Alpha non mi permette di credere che $ e^\pi=(640320^3+744)^(1/\sqrt(163)) $.
"Sono venticinque secoli che la filosofia inquadra i problemi, ma non scatta mai la foto.” - Edoardo Boncinelli, L'infinito in breve.
orsoulx
Cannot live without
Cannot live without
 
Messaggio: 1052 di 3906
Iscritto il: 30/12/2014, 11:13

Re: Problema di combinatoria - Test SGSS

Messaggioda axpgn » 29/03/2017, 18:32

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

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

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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 7887 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Problema di combinatoria - Test SGSS

Messaggioda orsoulx » 29/03/2017, 18:42

@Alex
è moooolto più semplice.... e il risultato numerico è un megahint
Ciao
Stephen Wolfram non mi è simpatico, anche perché il malefico Wolfram|Alpha non mi permette di credere che $ e^\pi=(640320^3+744)^(1/\sqrt(163)) $.
"Sono venticinque secoli che la filosofia inquadra i problemi, ma non scatta mai la foto.” - Edoardo Boncinelli, L'infinito in breve.
orsoulx
Cannot live without
Cannot live without
 
Messaggio: 1055 di 3906
Iscritto il: 30/12/2014, 11:13

Re: Problema di combinatoria - Test SGSS

Messaggioda axpgn » 29/03/2017, 19:01

Penso di aver capito ma non ho verificato ...

Testo nascosto, fai click qui per vederlo
$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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 7888 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Problema di combinatoria - Test SGSS

Messaggioda orsoulx » 29/03/2017, 20:42

@Alex :smt023
Testo nascosto, fai click qui per vederlo
Nel settimo quadratino deve esserci la cifra, unica ed esistente, che porta ad un multiplo di 4 la somma delle 15 già inserite.

Ciao
Stephen Wolfram non mi è simpatico, anche perché il malefico Wolfram|Alpha non mi permette di credere che $ e^\pi=(640320^3+744)^(1/\sqrt(163)) $.
"Sono venticinque secoli che la filosofia inquadra i problemi, ma non scatta mai la foto.” - Edoardo Boncinelli, L'infinito in breve.
orsoulx
Cannot live without
Cannot live without
 
Messaggio: 1056 di 3906
Iscritto il: 30/12/2014, 11:13

Prossimo

Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite