16.1: Cuadrados Latinos y Sudokus
- Page ID
- 114345
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Se puede pensar en un cuadrado latino como un rompecabezas de Sudoku que puede ser de cualquier tamaño (cuadrado), y no tiene el requisito de que cada valor aparezca en cada uno de los subcuadrados más pequeños delineados.
Definición: Cuadrado Latino
Un cuadrado latino de orden\(n\) es una\(n \times n\) matriz cuyas entradas son elementos de un conjunto\(N\) de cardinalidad\(n\), con la propiedad de que cada elemento de\(N\) aparece exactamente una vez en cada fila y cada columna.
Ejemplo\(\PageIndex{1}\)
Aquí hay un cuadrado latino de orden\(4\):
\[ 1 \; \; 2 \; \; 3\; \; 4 \\ 4 \;\; 1 \; \; 2 \; \; 3 \\ 3 \; \; 4 \; \; 1\; \; 2 \\ 2 \; \; 3\; \; 4 \; \; 1 \]
Solución
Observe que en el ejemplo anterior, colocamos los números\(1\),\(2\),\(3\), y\(4\) en la primera fila, en ese orden. Para cada fila posterior, cambiamos los números un lugar a la derecha (envolviendo). Esta misma técnica (colocar los números de\(1\) a\(n\) través de la primera fila) trabajará para construir un cuadrado latino de orden\(n\).
Entonces podrías pensar (con razón) que los cuadrados latinos no son muy interesantes. Sin embargo, aun sabiendo que hay un cuadrado latino de todos los órdenes posibles y son fáciles de construir, quedan algunas preguntas relacionadas interesantes.
Algunas de estas preguntas están relacionadas con Sudokus. Si rellenamos algunas entradas de una plaza latina, ¿existen condiciones en estas entradas que garanticen que esto se pueda completar a una plaza latina completa? ¿Hay condiciones en las que podamos estar seguros de que una plaza latina parcial tiene una terminación única a una plaza latina completa?
Algunas de estas preguntas tienen respuestas fáciles que no son lo que realmente estamos buscando. Por ejemplo, si te damos todos menos una entrada de un cuadrado latino (o Sudoku), entonces si se puede completar en absoluto, la finalización será única. No obstante, se ha realizado un interesante trabajo matemático sobre estos problemas, tanto para los cuadrados latinos como para los Sudokus.
No se conocen ejemplos en los que un rompecabezas de Sudoku con\(16\) o menos cuadrados precargados, se pueda completar de manera única. Sin embargo, hay decenas de miles de formas (no isomórficas) de prellenar\(17\) entradas de un rompecabezas de Sudoku, que tienen una terminación única.
Mirar solo ejemplos “no isomórficos” es importante, porque hay muchas formas de crear cuadrados latinos (o rompecabezas de Sudoku) que son esencialmente los mismos. Las siguientes operaciones llevan un cuadrado latino a otro cuadrado latino que es estructuralmente esencialmente el mismo:
- Permutación de los símbolos utilizados en el conjunto\(N\). Por ejemplo, cambiando cada\(1\) a una\(2\) y cada\(2\) a una\(1\).
- Intercambiar dos filas cualesquiera.
- Intercambiar dos columnas cualesquiera.
- Hacer todas las filas en columnas, y todas las columnas en filas.
Ejercicio\(\PageIndex{1}\)
1) Demostrar que al intercambiar dos filas de un cuadrado latino, se obtiene un cuadrado latino.
2) Completar el siguiente cuadrado latino. ¿La finalización es única?
\( 1 \; \; \_ \; \; 4\; \; \_\; \\ \_ \; \; 1 \; \; \_\; \; \_\; \\ \_ \; \; \_ \; \; \_\; \; 3\; \\ \_ \; \; \_ \; \;\_\; \; \_\; \\ \)
3) Utilizar el método descrito al inicio de este capítulo para crear un cuadrado latino de orden\(5\). ¿Qué\(3\) de las operaciones enumeradas anteriormente que cambian un cuadrado latino a un cuadrado latino isomórfico, se requieren para llegar al siguiente resultado?
\( 5 \; \; 1 \; \; 4\; \; 2\; \; 3 \\ 1 \; \; 3 \; \; 5\; \; 4\; \; 2\\ 4 \; \; 5 \; \; 2\; \; 3\; \; 1\\ 2 \; \; 4 \; \; 3\; \; 1\; \; 5 \\ 3 \; \; 2 \; \; 1\; \; 5\; \; 4 \)
4) Mostrar que hay exactamente dos cuadrados latinos diferentes de orden\(3\) cuya primera fila es\(1\),\(2\),\(3\).
5) Mostrar que hay exactamente doce cuadrados latinos diferentes de orden\(3\) cuyas entradas son los números\(1\),\(2\),\(3\).
[Pista: Problema de uso\(4\).]
6) Hay cuatro cuadrados latinos diferentes de orden\(4\) cuya primera fila es\(1\),\(2\),\(3\),\(4\) y cuya primera columna es también\(1\),\(2\),\(3\),\(4\). Es decir, sólo hay cuatro formas de completar el siguiente cuadrado latino:
\( 1 \; \; 2 \; \; 3\; \; 4\; \\ 2 \; \; \_ \; \; \_\; \; \_\; \\ 3 \; \; \_ \; \; \_\; \; \_\; \\ 4 \; \; \_ \; \;\_\; \; \_\; \\ \)
Encuentra los cuatro.
[Pista: Cada una de las posibilidades para la segunda entrada de la segunda fila se puede completar de una o dos maneras.]