Troviamo uno scopo per il Sudoku

[Marco]

Via, il Sudoku è un male necessario. Pazientate e a settembre migrerà nei paesi caldi. Nel frattempo vi chiedo:

---------------------------------------------

Il Sudoku originario si gioca su una scacchiera 9x9, suddivisa in 3x3 blocchi 3x3 ognuno. Ora, siccome noi poveri matematici siamo un po' brodi, diciamo che giochiamo un minisudoku, su una scacchiera 4x4, suddivisa in 2x2 blocchi 2x2.

Ebbene, quanti sono i minisudoku?

[ricordo le regole: su ogni riga, colonna e blocco ogni simbolo compare una ed una sola volta]

Ciao. M.

[enomis_costa88]

come mio solito non capisco mai i problemi..
per esempio in questo non ho capito se i numeri in gioco sono 4 o 9(nel senso se posso usare tutti e 9 i numeri nello stesso sudoku..)

se i numeri usati sono 4(non conosciuti):
il secondo quadrato(pensando come nel piano cartesiano..primo a partire da sinistra in alto) lo posso scegliere in 9*8*7*6 modi diversi( 9 per la prima casa 8 per la seconda...)
il quarto quadrato lo posso scegliere in 4! modi meno i modi non compatibili con il primo.
Quanti sono i modi irregolari?
ipotizziamo a,b la prima riga del primo(secondo nel piano..) quadrato. saranno irregolari tutti i modi che hanno a,b e sue permutazioni nella stessa colonna nel 4°(perchè assegnerebbero ad a,b le stesse coordinate nel primo).
quindi sono 8 irregolari:(in ordine a partire dal primo a sinistra fino all'ultimo in basso a destra andando da sin a des)ca,db;da,cb;db,ca;cb,da;e altri 4 simmetrici(invertendo le colonne..)
sono poi irregolari anche (ipotizzando a,c la prima colonna del primo (secondo..)quadrato)tutti quelli che hanno a,c e sue permutazioni nella stessa riga ovvero altri 8 di cui 4 però già contati(queste ultime sono irregolari perchè assegnano ad a,b le stesse coordinate nel 3° ma non ci possono essere 2 cifre nello stesso posto)..
totale disposizioni irregolari: 2*8-4=12.
Dimostro ora che gli ultimi 2 quadrati sono già decisi dal 2° e dal 4°(se compatibili).
rispetto al 1°: il 4° quadrato blocca la colonna; il 2° la riga e quindi con 2+2-1(principio inclusione esclusione l'intersezione tra riga e colonna in un quadrato 2*2 è 1) caselle bloccate ne rimane una sola disponibile.
analogamente rispetto al 3° quadrato(invertendo i compiti)..
per cui a meno che abbia preso un granchio usando 4 cifre solamente le possibili situazioni sono:
9*8*7*6*(4!-12)
modificato ma non ne sono ancora sicuro..

[Marco]

Allora, i numeri usati devono per forza essere quattro, altrimenti non è vero che li usi tutti una e una sola volta. Poi pensavo ai numeri da 1 a 4 (altrimenti credo che ti complichi la vita...). E comunque a me viene un risultato diverso (il che, si badi, non implica che il tuo sia sbagliato...).

[Boll]

A me escono 2^7*3

Se Marco conferma provo a dimostrare.

[enomis_costa88]

riprovo

se i numeri usati sono 4(da uno a 4):
il secondo quadrato(pensando come nel piano cartesiano..primo a partire da sinistra in alto) lo posso scegliere in 4! modi diversi
il quarto quadrato lo posso scegliere in 4! modi meno i modi non compatibili con il primo.
Quanti sono i modi irregolari?
ipotizziamo a,b la prima riga del primo(secondo nel piano..) quadrato. saranno irregolari tutti i modi che hanno a,b e sue permutazioni nella stessa colonna nel 4°(perchè assegnerebbero ad a,b le stesse coordinate nel primo).
quindi sono 8 irregolari:(in ordine a partire dal primo a sinistra fino all'ultimo in basso a destra andando da sin a des)ca,db;da,cb;db,ca;cb,da;e altri 4 simmetrici(invertendo le colonne..)
sono poi irregolari anche (ipotizzando a,c la prima colonna del primo (secondo..)quadrato)tutti quelli che hanno a,c e sue permutazioni nella stessa riga ovvero altri 8 di cui (4basta elencarseli tutti..) però già contati..
totale disposizioni irregolari: 2*8-4=12.
Dimostro ora che gli ultimi 2 quadrati sono già decisi dal 2° e dal 4°(se compatibili).
rispetto al 1°: il 4° quadrato blocca la colonna; il 2° la riga e quindi con 2+2-1(principio inclusione esclusione l'intersezione tra riga e colonna in un quadrato 2*2 è 1) caselle bloccate ne rimane una sola disponibile.
analogamente rispetto al 3° quadrato(invertendo i compiti)..
risultato: 4!(4!-12)

inoltre questo risultato è diverso da quello di Boll(se avessi avuro 8 disp irregolari)..bo avrò sbagliato ancora

edit: corretto un dodici..ma è ancora diverso..

[Marco]

Se Marco conferma provo a dimostrare.

Oddio, 'spetta, che cerco gli occhiali.....

Prova a dimostrare che è meglio. Confermo. M.

[Igor]

Non me ne voglia Boll se mando la mia soluzione...

Ammettiamo che la prima riga sia 1-2-3-4

Per la seconda riga, le possibili combinazioni sono 4:

3-4-1-2
3-4-2-1
4-3-1-2
4-3-2-1

Prendiamo ora una qualsiasi di queste seconde righe, ad esempio la prima.

Abbiamo lo schema

1-2-3-4
3-4-1-2

Per la terza riga le possibili combinazioni sono 4

2-3-4-1
2-1-4-3
4-1-2-3
4-3-2-1

Il ragionamento è uguale se prendiamo una qualunque delle seconde righe.

L'ultima riga è determinata univocamente dalle tre precedenti.

Dunque, fissata la prima riga, i mini-sudoku possibili sono $ 4*4=16 $.

Poichè la prima riga può essere scelta in $ 4! $ modi diversi, i mini-sudoku sono in tutto $ 4!*16=384 $,che è lo stesso risultato di Boll,anche se scritto in una forma diversa,il che mi fa pensare che lui abbia trovato una dimostrazione diversa dalla mia, e probabilmente anche più immediata.

[phi]

EDIT: Noooooo! battuta sul tempo, sob. Ma ormai l'ho scritta, la posto... vabbè. Scusa Igor.

Beh, penso che Boll non si offenderà (o forse mi sbaglio ) se provo io a postare una soluzione, visto che (sigh) è tanto che non posto un bel nulla.
Credo che la tua "strategia", enomis, non convenga molto. Io partirei riempiendo la prima colonna; ovviamente abbiamo 4! possibilità. Adesso riempiamo la seconda colonna; abbiamo 2 (2!) possibilità per i primi 2 quadretti, altre 2 per gli ultimi, in modo da riempire correttamente i due "blocchi" 2x2 (ehm, scusate la quantità esorbitante di 2... ). Notiamo che non abbiamo fatto nessuna mossa "sbagliata"; infatti la seconda colonna è perfetta (i primi 2 quadrati conterranno i numeri dei secondi 2 della prima colonna, e viceversa); e anche sulle righe, per ora, non abbiamo doppioni. Adesso riempiamo i due quadretti rimanenti della prima riga. Abbiamo 2 possibilità (i numeri che dobbiamo metterci sono obbligati, l'ordine no); prima riga a posto. Rimanenti quadretti della seconda riga: sappiamo già che dobbiamo metterci (in pratica, il contenuto dei primi due quadretti della prima riga), ma l'ordine non conta; quindi altre 2 possibilità. Ok, manca un solo blocco. Ma da adesso in poi è tutto obbligato: avremmo teoricamente 4 possibilità per completare le colonne, ma siamo condizionati dal dover completare anche le righe, e quindi dobbiamo accontentarci di una sola configurazione corretta (che esiste: uhm, questo devo puntualizzarlo meglio?) Insomma, ricapitolando il tutto, il risultato è esattamente quello di boll: 4*3*2*2*2*2*2=3*2^7
Boll avrebbe probabilmente scritto una soluzione più chiara, però dai, mi devo allenare un po' anch'io! (E aumentare il numero vergognosamente basso dei miei post... )

[enomis_costa88]

ma allora che errore ho fatto per favore aiutatemi a cercarlo!
ripropongo un piccolo schema.. delle possibilità di scelta per i quattro quadrati

4!********|risulta da se
risulta da se|4!-le combinazioni impossibili..

le combinazioni impossibili mi risultano essere 12..visto che il mio risultato è < 384 ed è 288 penso d'avere contato 4 combinazioni irregolari di più del dovuto.
se abcd(disposto come sotto)

ab
cd

è il secondo(primo in'alto a sinistra..nel secondo quadrante del piano cartesiano) quadrato allora mi risultano irregolari:
acbd,bcad,adbc,bdac,cadb,cbda,dacb,dbca perchè costringerebbero a e b a stare nella stessa casella nel quadrato nel primo quadrante.
e anche cabd,acdb,bdca,dbac; perchè costringerebbero a e c a stare nella stessa casella nel quadrato del terzo quadrante.

ma evidentemente 4 di esse non lo sono..il resto mi pare giusto!?!

[enomis_costa88]

@igor e phi(e Boll e ci butto dentro anche Marco per avere dato l'ok )..non ho ben capito(che grande novità..)

tutti voi avete convenuto che con
1
2
3
4
esiste la possibilità 3421 in seconda colonna..
13
24
32
41
e ora dovrei trovare 4 possibilità per la terza..
13 con 24 disponibile
24 con 13 disponibile
32 con 41 disponibile
41 con 23 disponibile

noto subito che 2143 e 4321 vanno bene sia nella terza sia nella quarta colonna.
ora se cerco un'altra combinazione in terza colonna che inizi con 2 ottengo che devo avere 23 nelle prime due file (se fosse 21 sarebbe obbligata la situazione di prima..) e o 4o1 nella terza fila ma la cosa più interessante è la quarta fila(un 23 disponibile..) e la faccio notare a voi!
analogamente se cerco una terza colonna che inizi con 4 e non sia quella di prima devo avere 41 nelle prime due file e vediamo un po' in terza fila..un 4 o un 1??

se ho sparato una vaccata paurosa non assalitemi troppo..grazie e buona serata!

[Igor]

Acc! Hai ragione Enomis!. Delle 4 seconde righe, 2 permettono quattro combinazioni possibili per la terza, mentre le altre 2 ne permettono solo due.
Quindi, fissata la prima riga, abbiamo $ 12 $ possibili sudoku.
In totale, dunque, i minisudoku sono:

$ 4!*12=288 $, come tu avevi già giustamente affermato.

[phi]

(che esiste: uhm, questo devo puntualizzarlo meglio?)

Ehm, forse sì, dovevo controllare meglio.
Ok, scusa enomis.

EDIT: com'è che Igor arriva sempre un minuto prima di me???

[Boll]

Ora è notte fonda, e non mi rimetterò a pensare ad un problema a cui pensai 6-7 minuti (odio la combinatoria) e che quindi, inevitabilmente, evidentemente, sbagliai. Il mio abbaglio, se il mio cervello funziona ancora, è esattamente quello di phi, Igor e credo Marco, cioè shiftare il tutto senza controllare configurazioni impossibili.

[Marco]

E comunque a me viene un risultato diverso (il che, si badi, non implica che il tuo sia sbagliato...).

[enomis_costa88]

[OT] Ok provo a tirare le somme di questo esercizio:

1) ho capito che il sudoku potrebbe anche avere uno scopo (che era il titolo e l'obiettivo dell'esercizio..) e d'ora in poi eviterò di continuare a dire a mio papà (che di matematica capisce 0) che è un'inutile perdita di tempo

2) ho capito che Marco (per il quale ho molta stima) è un essere umano in quanto sbaglia anch'egli..e arrossisce anch'egli!

3)

scusa enomis.

ovviamente le scuse sono accettate..(ma scusa di che?? è un gioco..e bisogna divertirsi! se uno chiedesse scusa tutte le volte che sbaglia non si finirebbe più!)

e sono accettati anche gli accidenti di Igor (mi spiace perchè è la seconda volta che ti rubo la sol..scusami..e no ora mi metto pure io a sproloquiare!)

Buona serata Simone