Home/ Intrebari/Q 93240
Urmator
In Process

AniDeȘcoală.ro Latest Intrebari

Felixx
veteran (III)
Pe: 2022-02-13T17:33:23+02:00 In: In:

Matrice

O minigrila Sudoku este o matrice 4 x 4 de numere intregi cu proprietatea ca in fiecare linie ,fiecare coloana si fiecare bloc 2 x 2 ,numerele de la 1 la 4 apar exact o data.Cate minigrile Sudoku distincte se pot construi ?
\begin{bmatrix} 1 & 2 &3 &4 \\ 3& 4 &2 &1 \\ 2& 1 &4 &3 \\ 4& 3 & 1 &2 \end{bmatrix}

a)280 b)288 c)282 d)285 e)284 f)290

Similare

9 raspunsuri

  1. robi

    Răspunsul este 288, dar fiind destul de complicată problema, aș vrea să știu care e sursa. De asemenea, v-ați referit greșit la „fiecare bloc 2×2”. Condiția se impune doar blocurilor 2×2 din colțuri.

  2. Felixx
    veteran (III)

    Intr-adevar blocurile sunt cele din colturi. Pe figura erau delimitate de linii rosii.
    Mutumesc pentru raspuns . Asa am obtinut si eu. Voiam o verificare. Problema este dintr-o culegere de admitere la UPT. Cum am judecat-o eu :
    Nu m-am jucat niciodata Sudoku 🙂 . Am plecat de la ideea ca in acest joc se pleaca de la situatia din figura.
    Am observat mai intai ca prin permutari circulare obtin o asemenea matrice celei din figura.Deci cu blocul 2×2 din stanga sus obtinem prin permutari circulare 4 asemenea matrice.Daca schimbam locul elementelor din blocul stanga sus intre ele obtinem 4! variante. Si cum pentru fiecare varianta avem 4 matrice : Total 24 variante x 4 matrice = 96 variante .
    Deci plecand de la pozitia cu blocul din stanga sus , putem pozitiona celelalte 3 blocuri in locul lui si vom obtine pentru fiecare acelasi nr. de variante.
    Total : 3 x 96 variante = 288 de variante.
    As fi curios daca am gandit corect si cum ati gasit dvs. rezultatul.
    Multumesc.

  4. robi

    Felixx post_id=116692 time=1644788250 user_id=21270 wrote: Am plecat de la ideea ca in acest joc se pleaca de la situatia din figura.
    Am observat mai intai ca prin permutari circulare obtin o asemenea matrice celei din figura.Deci cu blocul 2×2 din stanga sus obtinem prin permutari circulare 4 asemenea matrice.

    Nu am înțeles nimic din ce ați scris aici.

  5. Felixx
    veteran (III)

    Prin permutari circulare : 1→2→3→4→1 plecand de la blocul 2×2 din stanga sus obtinem o asemenea matrice , adica :
    \begin{bmatrix} 2 & 3 &4 &1 \\ 4 &1 & 3 &2 \\ 3& 2 & 1 &4 \\ 1 & 4 & 2 & 3 \end{bmatrix}
    si asa mai departe.

  6. robi

    Felixx post_id=116694 time=1644790113 user_id=21270 wrote:
    Prin permutari circulare : 1→2→3→4→1 plecand de la blocul 2×2 din stanga sus obtinem o asemenea matrice , adica :
    \begin{bmatrix} 2 & 3 &4 &1 \\ 4 &1 & 3 &2 \\ 3& 2 & 1 &4 \\ 1 & 4 & 2 & 3 \end{bmatrix}
    si asa mai departe.


    Prin permutari circulare : 1→2→3→4→1 plecand de la blocul 2×2 din stanga sus obtinem:
    \begin{bmatrix} 2&3\\4&1 \end{bmatrix}\rightarrow \begin{bmatrix} 3&4\\1&2 \end{bmatrix}\rightarrow \begin{bmatrix} 4&1\\2&3 \end{bmatrix}\rightarrow \ldots

  8. Felixx
    veteran (III)

    Permutari circulare pe toata matricea de plecare.La a 4-a permutare ajungem de unde am plecat , cu blocul 2×2 stanga sus.

  9. robi

    Felixx post_id=116696 time=1644856327 user_id=21270 wrote:
    Permutari circulare pe toata matricea de plecare.La a 4-a permutare ajungem de unde am plecat , cu blocul 2×2 stanga sus.


    Deci permutăm circular blocurile, nu numerele 1,2,3,4, așa cum ați scris.
    Ce e neclar: cum alegem matricea de start? De ce la sfârșit înmulțim cu 3 (și nu cu 4), nu toate blocurile 2×2 pot fi folosite?
    Care e argumentul că în felul ăsta (pe care, de fapt, tot nu l-am înțeles) obținem toate minigrilele, fără repetiție?

    Iată soluția mea. Mai întâi definesc zona principală a matricei ca fiind zona cu steluțe de mai jos.
    \begin{tabular}{|c|c|c|c|} \hline * & * & * & * \\ \hline * & * & &\\ \hline *&&&\\ \hline *&&&\\ \hline \end{tabular}

    Afirmația este următoarea: zona principală poate fi completată în 4!\cdot4=96 de moduri, iar restul matricei în 3.
    Prima parte a afirmației e destul de evidentă, așa că mă voi ocupa de partea a 2-a.
    Să presupunem că am completat zona principală și să ne concentrăm pe cele două elemente care se află pe diagonala blocului 2×2 stânga sus.
    \begin{tabular}{|c|c|c|c|} \hline x & & * & * \\ \hline & y & &\\ \hline *&&&\\ \hline *&&&\\ \hline \end{tabular}
    Desigur, pe prima linie și pe prima coloană trebuie să mai apară un y, în exteriorul primului bloc 2×2. Să alegem, de exemplu:
    \begin{tabular}{|c|c|c|c|} \hline x & & *& y \\ \hline & y & &\\ \hline y&&&\\ \hline * &&&\\ \hline \end{tabular}

    Atunci, în blocul 2×2 din dreapta jos există exact o căsuță pe a cărei linie și coloană nu există niciun y. Desigur, trebuie pus acolo y. Pentru x, în acest ultim bloc 2×2 mai sunt 3 posibilități de așezare (marcate cu steluțe mai jos).
    \begin{tabular}{|c|c|c|c|} \hline x & & & y \\ \hline & y & &\\ \hline y&&*&*\\ \hline &&y&*\\ \hline \end{tabular}
    Odată aleasă poziția lui x, completarea se face în mod unic (după ce am completat zona principală). De exemplu
    \begin{tabular}{|c|c|c|c|} \hline x & a& b & y \\ \hline b& y & &\\ \hline y&&&x\\ \hline a&&y&\\ \hline \end{tabular}\rightarrow \begin{tabular}{|c|c|c|c|} \hline x & a& b & y \\ \hline b& y & x&a\\ \hline y&b&a&x\\ \hline a&x&y&b\\ \hline \end{tabular}

  10. ghioknt
    profesor

    Eu propun și următoarea abordare, care pleacă de la întrebarea: în cazul în care această problemă îmi apare la examen, cam cât timp am la dispoziție pentru a găsi răspunsul (nu rezolvarea)?
    Ai sugerat că blocul de 4, B_{11} poate fi completat în 4!=24 de variante. Asta înseamnă că mulțimea tuturor matricelor se partiționează în 24 de clase disjuncte două câte două, fiecare clasă conținând toate matricele care au o anumită variantă a lui B_{11}. Nu e greu de observat, iar la ananghie doar presupui, că toate clasele au același cardinal, deci răspunsul trebuie să fie un număr divizibil cu 24. Dacă propunătorul nu a fost hain, o să găsești un singur asemenea răspuns.

  12. robi

    Păi abordarea asta a propunătorului problemei mi s-a părut cam evidentă din start, citind „soluția”. E relativ clar că numărul căutat se divide cu 24. Mă descurc apoi și cu 4. Problema e de unde scot divizorul 3?

Raspunde

Raspunde