Problema 6 SNS 2015

[tommy1996q]

Provo a mettere la soluzione del sesto problema, premetto che i problemi di questo tipo non sono il mio forte, perciò se avete consigli, vedete errori, avete soluzioni alternative ecc. scrivete mi raccomando!

Problema 6
Non ricordo il testo, ma sostanzialmente chiedeva 3 cose:
1) in quanti modi diversi si può comporre un sudoku di 4 quadretti 2X2 dove si mettono i numeri (1,2,3,4). Le regole sono quelle classiche del sudoku: in ogni quadretto 2X2 ci possono essere solo numeri diversi, così come in ogni riga e in ogni colonna.
2) se fisso un numero in una casella, quante sono le soluzioni che hanno quel numero in quella casella?
3) e se invece fisso 2 numeri? Mostra che esiste sempre una soluzione e che non è unica

Ecco la soluzione che ho pensato:

1) Consideriamo che possiamo scegliere gli elementi di 2 quadratini 2X2 non adiacenti in 4!*4! modi. Tuttavia le righe (dove per riga si intende anche colonna, in generale una fila di 2 numeri che fa da lato ai 2 quadratini) dei 2 quadratini che hanno in comune una certa casella dei 2 quadratini rimasti devono sempre avere almeno un numero in comune. Infatti se ciò non fosse avremmo sempre delle caselle nei quadratini rimasti in cui nessun numero andrebbe bene. Allora le combinazioni non saranno 4!, ma meno.
Avendo completato un quadratino solamente, possiamo scegliere un elemento da porre nel secondo quadratino 2X2, non adiacente al primo, in 4 modi. Poi scegliamo un altro elemento, non adiacente alla casella del primo (ma nello stesso quadratino 2X2) in 3 modi. A questo punto rmangono 2 quadratini. Mettendo "a sistema" le condizioni prima dette, notiamo che solo uno dei due modi di porre i restanti 2 numeri nelle restanti caselle è giusto. A questo punto gli altri quadratini 2X2 sono a scelta obbligata, perché intersezioni di linee che hanno già 3 elementi diversi, per cui la scelta deve ricadere per forza sul quarto.

Allora il numero cercato è:
$S=4!*4*3=288$

2) Considero un elemento fisso, e parto a costruire il mio quadrato dal quadratino 2X2 che lo contiene. Gli altri elementi del quadratino 2X2 si possono scegliere in 3! modi e poi il ragionamento è lo stesso del punto 1. quindi la risposta dovrebbe essere:

$S(1)=3!*4*3=72$

3) per il punto 3 considero una soluzione generale e noto che la permutazione di elementi, lo scambio di due righe parallele di uno stesso quadrato e la rotazione del sudoku mantengono un sudoku che è una soluzione. Allora permuto e scambio e ruoto fino ad avere i 2 elementi nei posti scelti, e ottengo una soluzione. Un'altra esiste sempre perché basta permutare gli altri 2 elementi

ATTENZIONE: non era richiesto dal problema, ma io lo propongo lo stesso: chi mi sa dire quante sono le soluzioni fissati 2 numeri e perché?

[coleridge1]

Non ho ben capito quali sono le "mosse" che consideri (lo scambio tra due righe di un quadratino 2x2 non è valido), né come le conti, ma la tua risposta al primo punto mi sembra eccessiva.
Banalmente, il sudoku è determinato dai numeri che sono scritti in due quadratini 2x2 "opposti"; i modi per scrivere i numeri lì dentro sono solo $4!\cdot 4!$ (e non tutti funzionano!)
Inoltre, forse ho capito male il testo, ma se al secondo punto fissi un numero in una casella, allora rimani con esattamente un quarto di tutte le configurazioni possibili.

[coleridge1]

Per il terzo punto (e la domanda aggiuntiva) vengono fissati due numeri diversi nello stesso quadratino 2x2, oppure lo stesso numero in due quadratini diversi, o ancora due numeri diversi in due quadratini diversi?

[Pachisi]

Per il punto 1) dovrebbero essere $288$. Fissi il primo quadretto in alto a sinistra. Ora il quadretto a destra di quello può essere riempito in 4 modi, cosi come quello sotto il primo. L'ultimo ovviamente lo puoi riempire in 1 modo. Di quei 16 modi di riempire il secondo e il terzo quadretto 4 in ogni configurazione non funzionano (credo). Il primo quadretto lo puoi riempire in $4!$ modi, quindi $4! \cdot 12=288$.

[DeBeTeo]

Io per il primo punto ho provato a ragionare in questo modo:

Per quanto riguarda la prima riga abbiamo un 4! di possibilitá diverse
Per quanto riguarda la seconda riga si ha invece 2 varianti per ogni quadrato (4 in tutto)
Arrivati alle ultime due righe sappiamo che, completando un quadrato (in cui in ogni colonnina da 2x1 abbiamo 2 combinazioni diverse, quindi 4 in tutto), si completa automaticamente anche l'ultimo quadrato.

Il calcolo delle possibilitá diventa quindi 4! per 2^4, cioè 384

[Pachisi]

Di quelle configurazioni non tutte funzionano. Se provi, per esempio, iniziando con {1,2,3,4} te ne accorgi subito.

[DeBeTeo]

"Pachisi":Di quelle configurazioni non tutte funzionano. Se provi, per esempio, iniziando con {1,2,3,4} te ne accorgi subito.

Sicuro che non funzionano tutte? Ho provato come dici te ad iniziare con 1,2,3,4 ma fanziona lo stesso. Sarà un caso ma sto provando diverse combinazioni avendo fissata la prima riga e nonostante questo riesco sempre a completare il sudoku

[DeBeTeo]

E ti dico anche perchè secondo me nel ragionamento che ho fatto non ci dovrebbero essere configurazioni non funzionanti: ovvero perchè il mio ragionamento è stato portato avanti tenendo sempre conto delle regole del sudoku. Quindi, a meno che io non abbia sbagliato qualche regola, le possibilitá da me calcolate dovrebbero essere tutte corrette. Nel modo di procedere ho considerato inizialmente tutte le permutazioni di 4 numeri. In base alle regole del sudoku ho poi escluso quelle permutazioni che facevano comparire in un solo quadrato e/o in una sola colonna due numeri uguali tra loro.

[Pachisi]

Sulle 16 possibili configurazioni se inizi con 1,2,3,4, quattro non funzionano.

[DeBeTeo]

"Pachisi":
Sulle 16 possibili configurazioni se inizi con 1,2,3,4, quattro non funzionano.

Ok allora era un caso ahahah. Non avevo provato abbastanza

[DeBeTeo]

Ed effettivamente non avevo nemmeno considerato tutte le regole del sudoku. Ovvero che per completare l'ultimo quadrante devo prima far sì che non ci siano giá tre coppie di numeri uguali tra loro in ogni riga e in ogni colonna

[tommy1996q]

Allora, secondo me le combinazioni che ho trovato sono troppe per un sudoku così piccolo, lo dico "a occhio" diciamo, ma credo di aver contato più volte le stesse combinazioni.
Il problema è sapere quante....
Oltretutto alle operazioni che ho descritto mi è venuta in mente anche la simmetria assiale, quindi il numero finale sarebbe ancora maggiore...

Secondo me comunque conviene ragionare sul fatto che la somma lungo una riga e in un quadratino 2X2 è sempre 10, e da lì trovare tutte le possibilità

[tommy1996q]

Ho rifatto il problema in un modo diverso e secondo me più convincente, non avevo molto tempo quindi nn so se si capirà benissimo. La soluzione nuova è sotto la vecchia e nel caso la sostituirò

[Pachisi]

Per il punto 2) le soluzioni dovrebbero essere (come detto da coleridge) un quarto quelle del punto 1), quindi $72$.

[tommy1996q]

si hai ragione, infatti sono un quarto, io avevo fatto una divisione assurda perché ero in ritardo pauroso e nn ho visto l'errore madornale . Ora ho corretto, ma a me le configuarzaioni non tornano 288, come hai fatto a ottenere quel numero???

[coleridge1]

"tommy1996q":ATTENZIONE: non era richiesto dal problema, ma io lo propongo lo stesso: chi mi sa dire quante sono le soluzioni fissati 2 numeri e perché?

Provo a rispondere a questa domanda.
Il primo numero è già stato inserito, qundi abbiamo già diviso i casi possibili per $4$ e ne rimangono $72$.
Per il secondo, osserviamo che si possono ancora scambiare tra loro le due righe e/o le due colonne rimanenti, o i tre numeri non usati:

[*:2qr4ee4z]se è lo stesso numero


[*:2qr4ee4z]in una 2x2 contigua: $72:2=36$[/*:m:2qr4ee4z]
[*:2qr4ee4z]nella 2x2 opposta: $72:4=18$[/*:m:2qr4ee4z][/list:u:2qr4ee4z][/*:m:2qr4ee4z]
[*:2qr4ee4z]se è un numero diverso


[*:2qr4ee4z]nella stessa 2x2: $72:3=24$[/*:m:2qr4ee4z]
[*:2qr4ee4z]nella 2x2 opposta: $72:4=18$[/*:m:2qr4ee4z]
[*:2qr4ee4z]in una 2x2 contigua


[*:2qr4ee4z] sulla stessa riga/colonna: $72:3=24$[/*:m:2qr4ee4z]
[*:2qr4ee4z] sull'altra riga/colonna (vanno esclusi i casi con lo stesso numero): $(72-72:2):3=12$[/*:m:2qr4ee4z][/list:u:2qr4ee4z][/*:m:2qr4ee4z][/list:u:2qr4ee4z][/*:m:2qr4ee4z][/list:u:2qr4ee4z]

[coleridge1]

"tommy1996q":Alllora il primo di questi 2 quadretti potrà essere riempito in 4 modi, vaiando l'ordine degli elementi. Per il secondo notiamo che se una sua riga è uguale a una colonna del primo, allora anche la riga restante sarà uguale all'altra colonna, per cui le possibilità si riducono, alla fine, a 2, che praticamente consistono nelle stesse 2 righe scambiate di posto. Allora alla fine abbiamo:

$S=4!*4*2=192$

Ma in 2 di questi 4 casi non è possibile che una riga del secondo (terzo?) sia uguale a una colonna del primo (secondo?).

[tommy1996q]

Guarda, ho riveduto tutto con calma e senza fretta, e ho trovato che anche a me tornano 288 possibilità e poi nel punto 2 72. Ho corretto la dimostrazione, ma senza disegni non mi è facile spiegare, semmai provvederò a metterli. Oltretutto non credo sia molto rigorosa come cosa.... Comunque tu in un post precedente hai semplicemente detto che le soluzioni erano 288. Puoi spiegare come sei giunto a questo risultato? Perché alla fine le domande 2 e 3 sono abbastanza facili una volta risolta la prima, che è un po la chiave di volta del problema

[Pachisi]

Ti consiglio di fare un disegno.
La casella $a_{i,j}$ è quella nella $i-esima$ riga e $j-esima$ colonna.
Riempiamo il quadrato 2x2 in alto a sinistra con $a_{1,1}=1, a_{1,2}=2, a_{2,1}=3, a_{2,2}=4$. Ora, possiamo avere $a_{1,3}=3, a_{1,4}=4$ o viceversa. Analogamente, possiamo avere $a_{3,1}=2, a_{4,1}=4$ o viceversa. Notiamo che possiamo scambiare le ultime due righe e le ultime due colonne per avere una nuova soluzione. Quindi, possiamo considerare uno di questi casi. Sia $a_{1,3}=3, a_{1,4}=4$ e $a_{3,1}=2, a_{4,1}=4$. Consideriamo la posizione $a_{3,3}$. Chiaramente non possiamo mettere ne 2 ne 3. Notiamo che non possiamo mettere neanche 1. Infatti, se $a_{3,3}=1$, allora, si avrebbe $a_{4,2}=a_{2,4}=1$, quindi $a_{2,3}=2$ e $a_{3,2}=3$. Allora, $a_{3,4}=4$. Questo però è impossibile perché abbiamo già un 4 in quella colonna. Quindi, $a_{3,3}=4$. Questo porta 3 diverse soluzioni. Considerando che il primo quadrato 2x2 puo` essere riempito in $4!$ modi e che possiamo scambiare le ultime due righe e colonne in $2 \cdot 2$ modi, abbiamo un totale di $4! \cdot 2 \cdot 2 \cdot 3=288$ modi.

[coleridge1]

In alternativa potresti calcolare così:
Nella casella 2x2 opposta a quella già sistemata ci sono $4\cdot3$ modi di scrivere $a$ e $d$.
\begin{matrix}a&b\\c&d\\&&\cdot&\cdot\\&&\cdot&\cdot\end{matrix}
Ora c'è un solo modo per scrivere $b$ (non sulla colonna di $a$) e $c$ (non sulla riga di $a$).