Matemáticas universitarias — Grado 2 · Bachelor Year 2

1Conjuntos y estructuras

Este capítulo inicial afila los cimientos puestos en el volumen del primer año hasta convertirlos en herramientas de trabajo: el cálculo con conjuntos y cocientes, la comparación de conjuntos infinitos (numerabilidad, Cantor–Bernstein) y la teoría estructural de grupos y anillos —el teorema de Lagrange, el grupo simétrico con su signatura, los ideales y el teorema chino del resto—. Todo lo que aquí aparece se usa sin descanso en el resto del libro: la signatura construye el determinante (Capítulo 2), los anillos cociente gobiernan la aritmética y la numerabilidad sostiene tanto la topología como la probabilidad.

1.1 Conjuntos, aplicaciones, cocientes

Usamos con toda libertad el lenguaje de conjuntos, aplicaciones y relaciones de equivalencia y de orden establecido en el volumen del primer año. Dos mejoras merecen un enunciado propio.

Proposición 1.1 (Imágenes e imágenes recíprocas de familias)

Sea $f \colon E \to F$ y sean $(A_i)_{i \in I}$ , $(B_j)_{j \in J}$ familias de subconjuntos de $E$ y de $F$ , respectivamente. Entonces

f^{-1}\Bigl(\bigcup_j B_j\Bigr) = \bigcup_j f^{-1}(B_j), \qquad f^{-1}\Bigl(\bigcap_j B_j\Bigr) = \bigcap_j f^{-1}(B_j), \qquad f^{-1}(F \setminus B) = E \setminus f^{-1}(B),

f\Bigl(\bigcup_i A_i\Bigr) = \bigcup_i f(A_i), \qquad f\Bigl(\bigcap_i A_i\Bigr) \subseteq \bigcap_i f(A_i) \quad (\text{con igualdad si } f \text{ es inyectiva}).

Demostración. Cada identidad se obtiene desplegando las definiciones; por ejemplo, $x \in f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ para todo $j$ $\iff x \in f^{-1}(B_j)$ para todo $j$ . Las identidades sobre imágenes y el fallo de la igualdad en el caso de la intersección (con el remedio de la inyectividad) se demostraron en el volumen del primer año para dos conjuntos; los argumentos son idénticos para familias. ∎

Ejemplo 1.2 (Cuándo la inclusión de imágenes es estricta)

Tomemos $f \colon \R \to \R$ , $f(x) = x^2$ , con $A_1 = \intcc{-1}{0}$ y $A_2 = \intcc{0}{1}$ . Entonces

f(A_1 \cap A_2) = f(\{0\}) = \{0\}, \qquad f(A_1) \cap f(A_2) = \intcc{0}{1} \cap \intcc{0}{1} = \intcc{0}{1} :

la inclusión de la Proposición 1.1 es todo lo estricta que puede ser: las dos preimágenes $\pm x$ de un mismo valor viven en $A_i$ distintos. La inyectividad es justamente lo que prohíbe ese desdoblamiento, y por eso las imágenes recíprocas (que nunca funden puntos) cumplen las cuatro identidades sin condiciones, mientras que las imágenes pierden la de la intersección. Regla práctica para todo el libro: las imágenes recíprocas atraviesan las operaciones conjuntistas sin más; con las imágenes hay que ir con cuidado.

Definición 1.3 (Conjunto cociente)

Sea $\mathcal{R}$ una relación de equivalencia sobre $E$ . El conjunto cociente $E/\mathcal{R}$ es el conjunto de las clases de equivalencia; la sobreyección $\pi \colon E \to E/\mathcal{R}$ , $x \mapsto \mathrm{cl}(x)$ , es la proyección canónica.

Propiedad universal (factorización): si $f \colon E \to F$ es compatible con $\mathcal{R}$ (es decir, $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ ), existe una única aplicación $\overline f \colon E/\mathcal{R} \to F$ tal que $f = \overline f \circ \pi$ .

Demostración de la propiedad universal. Unicidad: la condición $f = \overline f \circ \pi$ se lee

\overline f\bigl(\mathrm{cl}(x)\bigr) = f(x) \qquad (x \in E),

y, como $\pi$ es sobreyectiva, todo elemento de $E/\mathcal{R}$ es de la forma $\mathrm{cl}(x)$ : los valores de $\overline f$ quedan todos forzados. Existencia: tomemos la fórmula anterior como definición de $\overline f$ ; es inequívoca precisamente por la compatibilidad —si $\mathrm{cl}(x) = \mathrm{cl}(y)$ , entonces $x \mathbin{\mathcal{R}} y$ , luego $f(x) = f(y)$ y los dos valores candidatos coinciden— y factoriza $f$ por construcción. Obsérvese el reparto de papeles: la sobreyectividad de $\pi$ da la unicidad, la compatibilidad da la existencia. ∎

Ejemplo 1.4

$\Z/n\Z$ es el cociente de $\Z$ por la congruencia módulo $n$ ; las comprobaciones de buena definición del volumen del primer año eran casos particulares de la propiedad universal. Los cocientes convierten las “construcciones compatibles sobre representantes” en aplicaciones legítimas; lo usaremos sin cesar más abajo.

1.2 Numerabilidad y cardinalidad

Definición 1.5 (Equipotencia, numerabilidad)

Dos conjuntos son equipotentes cuando existe una biyección entre ellos. Un conjunto es numerable cuando es equipotente a $\N$ (algunos autores incluyen los conjuntos finitos; nosotros decimos a lo sumo numerable para “finito o numerable”).

Proposición 1.6 (Propiedades de estabilidad)

Todo subconjunto infinito de $\N$ es numerable; un conjunto es a lo sumo numerable si y solo si se inyecta en $\N$ , si y solo si es vacío o imagen sobreyectiva de $\N$ .
$\N \times \N$ es numerable; un producto de dos conjuntos a lo sumo numerables es a lo sumo numerable.
Una unión a lo sumo numerable de conjuntos a lo sumo numerables es a lo sumo numerable.
$\Z$ y $\Q$ son numerables.

Demostración. (1) Enumeremos un $A \subseteq \N$ infinito por mínimos sucesivos: $a_0 = \min A$ , $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (conjunto no vacío, pues $A$ es infinito); la aplicación $k \mapsto a_k$ es estrictamente creciente, inyectiva y sobreyectiva sobre $A$ (cada $a \in A$ supera solo a un número finito de elementos de $A$ , luego se alcanza). Si $E$ se inyecta en $\N$ mediante $\varphi$ , entonces $E$ es equipotente a $\varphi(E) \subseteq \N$ : finito o numerable. Si $s \colon \N \to E$ es sobreyectiva, entonces $x \mapsto \min s^{-1}(\{x\})$ inyecta $E$ en $\N$ .

(2) La aplicación $(p, q) \mapsto 2^p(2q + 1) - 1$ es una biyección $\N^2 \to \N$ (todo entero positivo admite una única descomposición $2^p m$ con $m$ impar, por la factorización única). Productos: compóngase con inyecciones.

(3) Dados conjuntos $E_n$ con sobreyecciones $s_n \colon \N \to E_n$ (inofensivo cuando algún $E_n$ es finito: se repiten valores), la aplicación $(n, k) \mapsto s_n(k)$ es una sobreyección del conjunto numerable $\N^2$ sobre $\bigcup E_n$ .

(4) $\Z = \N \cup (-\N^*)$ : unión numerable. $\Q$ es imagen sobreyectiva de $\Z \times \N^*$ (la aplicación fracción), luego es a lo sumo numerable, y es infinito. ∎

Ejemplo 1.7 (Una función de emparejamiento, calculada)

La biyección $(p, q) \mapsto 2^p(2q + 1) - 1$ de la demostración merece verse en funcionamiento. Sus primeros valores:

\begin{array}{c|ccccc} & q = 0 & q = 1 & q = 2 & q = 3 & q = 4\\ \hline p = 0 & 0 & 2 & 4 & 6 & 8\\ p = 1 & 1 & 5 & 9 & 13 & 17\\ p = 2 & 3 & 11 & 19 & 27 & 35\\ p = 3 & 7 & 23 & 39 & 55 & 71 \end{array}

La fila $p$ reúne los enteros $n$ para los que $n + 1$ es divisible exactamente por $2^p$ : cada número natural aparece una sola vez. Descodificar es tan explícito como codificar: para $n = 43$ se factoriza $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ , luego $(p, q) = (2, 5)$ . La moraleja: las demostraciones de numerabilidad son a menudo algoritmos disfrazados; aquí, “sacar factor común los doses”.

Ejemplo 1.8 (Los números algebraicos son numerables)

Un número complejo es algebraico cuando anula algún polinomio no nulo con coeficientes racionales. El conjunto $\overline\Q$ de los números algebraicos es numerable: los polinomios de grado $\leq d$ sobre $\Q$ se inyectan en $\Q^{d+1}$ , producto finito de conjuntos numerables (Proposición 1.6 (2)); la unión sobre $d$ enumera los polinomios racionales no nulos como $P_0, P_1, P_2, \dots$ ; cada $P_k$ tiene un número finito de raíces; y

\overline\Q = \bigcup_{k \in \N}\ \{\text{raíces de } P_k\}

es una unión numerable de conjuntos finitos (Proposición 1.6 (3)), infinita porque contiene a $\Q$ . Junto con la no numerabilidad de $\R$ (Teorema 1.9 más abajo), esto demuestra —sin exhibir ni uno solo— que los números trascendentes existen y forman una mayoría no numerable: el argumento de conteo de Cantor de 1874, existencia por pura cardinalidad.

Teorema 1.9 (Cantor; no numerabilidad de $\R$ )

Para todo conjunto $E$ no existe ninguna sobreyección $E \to \mathcal{P}(E)$ .
$\R$ no es numerable.

Demostración. (1) se demostró en el volumen del primer año (el conjunto diagonal $D = \{x : x \notin f(x)\}$ ).

(2) Supongamos que $(x_n)_{n \in \N}$ enumera $\R$ . Construyamos segmentos encajados $I_0 \supseteq I_1 \supseteq \dots$ con $\abs{I_n} = 3^{-n}$ y $x_n \notin I_n$ : se divide el segmento actual en tres tercios cerrados; al menos uno de ellos evita $x_n$ (un punto pertenece a lo sumo a dos de los tres). El teorema de los segmentos encajados (extremos adyacentes) proporciona $\ell \in \bigcap_n I_n$ ; pero $\ell = x_N$ para algún $N$ , y $x_N \notin I_N$ : contradicción. ∎

Teorema 1.10 (Cantor–Bernstein)

Si $E$ se inyecta en $F$ y $F$ se inyecta en $E$ , entonces $E$ y $F$ son equipotentes.

Demostración. Sean $f \colon E \to F$ y $g \colon F \to E$ inyectivas. Para cada punto (de $E$ o de $F$ ), recorramos su cadena de antecesores de preimágenes sucesivas, $x \mapsto g^{-1}(x) \mapsto f^{-1}(g^{-1}(x)) \mapsto \dots$ : cada paso está definido mientras el punto actual esté en la imagen de la inyección correspondiente, y entonces es único por inyectividad. Hay tres destinos mutuamente excluyentes: la cadena se detiene en un punto de $E \setminus g(F)$ (origen en $E$ ), se detiene en un punto de $F \setminus f(E)$ (origen en $F$ ) o no se detiene nunca. Esto reparte $E = E_E \cup E_F \cup E_\infty$ y $F = F_E \cup F_F \cup F_\infty$ según el origen.

Obsérvese ahora que $f$ aplica $E_E$ sobre $F_E$ : la cadena de $f(x)$ es la de $x$ con un paso más al principio, luego los orígenes coinciden; y todo $y \in F_E$ tiene una cadena con al menos un paso (su origen está en $E$ ), así que $y = f(x)$ con $x \in E_E$ . El mismo argumento da biyecciones $f \colon E_\infty \to F_\infty$ y $g \colon F_F \to E_F$ . Pegando,

h(x) = \begin{cases} f(x) & \text{si } x \in E_E \cup E_\infty,\\ g^{-1}(x) & \text{si } x \in E_F, \end{cases}

es una biyección de $E$ sobre $F = F_E \cup F_\infty \cup F_F$ : es biyectiva en cada trozo y las tres piezas de llegada son disjuntas. ∎

Ejemplo 1.11

$\intoo{0}{1}$ y $\intcc{0}{1}$ son equipotentes: la identidad inyecta en un sentido y $x \mapsto \frac{x + 1}{3}$ en el otro; el teorema fabrica la biyección (forzosamente discontinua). Del mismo modo, $\R$ , $\intoo{0}{1}$ (mediante biyecciones de tipo $\tanh$ ) y $\mathcal{P}(\N)$ (desarrollos binarios, Ejercicio 1.3) son todos equipotentes: “el cardinal del continuo”.

Ejemplo 1.12 (El segmento y el cuadrado)

$\intcc{0}{1}$ y $\intcc{0}{1}^2$ son equipotentes: la dimensión es invisible para el cardinal. Una inyección es trivial: $x \mapsto (x, 0)$ . Para la otra, enviemos $(x, y)$ al número real cuyas cifras decimales intercalan las de $x$ y las de $y$ ,

(0.x_1x_2x_3\dots,\ 0.y_1y_2y_3\dots) \;\longmapsto\; 0.x_1y_1x_2y_2x_3y_3\dots,

eligiendo para cada coordenada el desarrollo que no termina en infinitos $9$ : con ese convenio las cifras de la imagen determinan las de $x$ y las de $y$ , de modo que la aplicación es inyectiva (no tiene por qué ser sobreyectiva —ninguna imagen tiene, por ejemplo, todas las cifras de posición impar iguales a $9$ a partir de un punto—, y eso no importa). Cantor–Bernstein (Teorema 1.10) ensambla una biyección auténtica. La continuidad, eso sí, es inalcanzable: una biyección continua entre ambos es imposible, y los capítulos métricos explican por qué (la conexidad distingue la recta del plano, Capítulo 4).

1.3 Grupos

Definición 1.13 (Subgrupo generado; orden)

Sea $G$ un grupo y $A \subseteq G$ . El subgrupo generado por $A$ , escrito $\langle A \rangle$ , es el menor subgrupo que contiene a $A$ ; en concreto, el conjunto de todos los productos finitos de elementos de $A$ y de sus inversos. Un grupo es cíclico cuando está generado por un solo elemento: $\langle a\rangle = \{a^k : k \in \Z\}$ . El orden de $a \in G$ es $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (posiblemente infinito); cuando es finito, es el menor $n \geq 1$ con $a^n = e$ , y $a^k = e \iff \operatorname{ord}(a) \mid k$ .

Demostración de la caracterización del orden. Si algún $a^m = e$ con $m \geq 1$ , sea $n \geq 1$ el menor con $a^n = e$ . Los elementos $e, a, \dots, a^{n-1}$ son distintos dos a dos ( $a^{i} = a^{j}$ con $0 \leq i < j < n$ da $a^{j-i} = e$ , en contra de la minimalidad), y toda potencia $a^k$ se reduce a uno de ellos mediante la división euclídea $k = nq + r$ : $\langle a\rangle$ tiene exactamente $n$ elementos, y $a^k = a^r = e \iff r = 0 \iff n \mid k$ . Si ninguna potencia es trivial, todas las $a^k$ ( $k \in \Z$ ) son distintas (mismo argumento de división) y el orden es infinito. ∎

Teorema 1.14 (Lagrange)

Sea $G$ un grupo finito y $H$ un subgrupo. Entonces $\abs H$ divide a $\abs G$ . En particular, el orden de todo elemento divide a $\abs G$ , y $a^{\abs G} = e$ para todo $a \in G$ .

Demostración. La relación $x \sim y \iff x^{-1}y \in H$ es de equivalencia (reflexiva: $e \in H$ ; simétrica: por inversos; transitiva: por productos). La clase de $x$ es la clase lateral izquierda $xH = \{xh : h \in H\}$ , y $h \mapsto xh$ es una biyección $H \to xH$ (de inversa $y \mapsto x^{-1}y$ ): todas las clases tienen $\abs H$ elementos. Las clases forman una partición de $G$ (el teorema general de partición del volumen del primer año), luego $\abs G = \abs H \times (\text{número de clases})$ . Para un elemento: aplíquese lo anterior a $H = \langle a\rangle$ ; entonces $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

Ejemplo 1.15 (Clases laterales en acción: $A_3$ dentro de $\mathfrak{S}_3$ )

Tomemos $G = \mathfrak{S}_3$ (de orden $6$ ) y $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . Las clases laterales izquierdas son

H = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}, \qquad (1\,2)H = \{(1\,2),\ (2\,3),\ (1\,3)\} :

dos clases de tres elementos que reparten $G$ , exactamente como exige el recuento $\abs G = \abs H \times (\text{número de clases})$ , y visiblemente la partición en permutaciones pares e impares. Nótese que $(1\,3)H = (1\,2)H$ aunque $(1\,3) \neq (1\,2)$ : las clases laterales son clases, no van etiquetadas por sus representantes, y $x^{-1}y \in H$ es la única comparación legítima. Esta imagen de dos clases es la general para la signatura: $A_n$ y su única clase acompañante parten $\mathfrak{S}_n$ por la mitad, y así es como el problema de fin de semana cuenta las posiciones alcanzables del rompecabezas.

Ejemplo 1.16

Dos dividendos inmediatos. Los grupos de orden primo son cíclicos: si $\abs G = p$ es primo y $a \neq e$ , entonces $\operatorname{ord}(a)$ divide a $p$ y no vale $1$ , luego vale $p$ : $\langle a\rangle = G$ . El retículo de subgrupos de $\Z/12\Z$ : por la Proposición 1.17 de más abajo hay exactamente un subgrupo por cada divisor de $12$ —de órdenes $1, 2, 3, 4, 6, 12$ , generados respectivamente por $\overline 0$ , $\overline 6$ , $\overline 4$ , $\overline 3$ , $\overline 2$ , $\overline 1$ —. La advertencia final: el recíproco del teorema de Lagrange es falso en general; $A_4$ tiene orden $12$ pero ningún subgrupo de orden $6$ , como demostramos en el problema de fin de semana de este capítulo (Problema 1.1, pregunta 14). Lagrange restringe los órdenes posibles; no los garantiza.

El retículo de subgrupos de ℤ/12ℤ: un subgrupo por cada divisor de 12 (), con una arista cuando uno contiene al otro con índice primo. Las inclusiones van en contra de la divisibilidad del generador: 4 ⊂eq 2 porque 4 es múltiplo de 2. — El retículo de subgrupos de $\Z/12\Z$ : un subgrupo por cada divisor de $12$ (Proposición 1.17), con una arista cuando uno contiene al otro con índice primo. Las inclusiones van *en contra* de la divisibilidad del generador: $\langle\overline 4\rangle \subseteq \langle\overline2\rangle$ porque $4$ es múltiplo de $2$ .

Proposición 1.17 (Grupos cíclicos)

Sea $G = \langle a \rangle$ cíclico de orden $n$ .

$G$ es isomorfo a $(\Z/n\Z, +)$ , mediante $\overline k \mapsto a^k$ .
Todo subgrupo de $G$ es cíclico; para cada divisor $d \mid n$ hay exactamente un subgrupo de orden $d$ , a saber $\langle a^{n/d}\rangle$ .
$a^k$ genera $G$ si y solo si $\gcd(k, n) = 1$ : $G$ tiene $\varphi(n)$ generadores (función de Euler).

Demostración. (1) La aplicación $k \mapsto a^k$ de $\Z$ sobre $G$ es compatible con la congruencia módulo $n$ ( $a^{k} = a^{k'} \iff n \mid k - k'$ , por la caracterización del orden); la propiedad universal (Definición 1.3) proporciona un morfismo biyectivo bien definido desde $\Z/n\Z$ .

(2) Sea $H \leq G$ no trivial y $m$ el menor entero $\geq 1$ con $a^m \in H$ . La división euclídea muestra que $H = \langle a^m\rangle$ (para $a^k \in H$ : de $k = mq + r$ se sigue $a^r \in H$ , luego $r = 0$ ), y $m \mid n$ (divídase $n$ entre $m$ : $a^{n \bmod m} \in H$ ). Entonces $\abs H = n/m$ ; tomando $m = n/d$ se realiza cada divisor $d$ . Unicidad: todo subgrupo de orden $d$ es, por lo anterior, de la forma $\langle a^m \rangle$ con $n/m = d$ ; así pues $m = n/d$ queda forzado y el subgrupo queda determinado.

(3) Afirmamos que $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . Escribamos $d = \gcd(k, n)$ . Para todo $m \geq 1$ , la caracterización del orden de la Definición 1.13 da la cadena de equivalencias

(a^k)^m = e \iff n \mid km \iff \frac{n}{d} \,\Big|\, \frac{k}{d}\,m \iff \frac{n}{d} \,\Big|\, m ,

donde el último paso es el lema de Gauss, ya que $\frac nd$ y $\frac kd$ son primos entre sí. El menor $m$ así es $\frac nd$ : $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ , que vale $n$ si y solo si $\gcd(k, n) = 1$ . Hay $\varphi(n)$ clases $k$ módulo $n$ en esas condiciones. ∎

1.4 El grupo simétrico

Definición 1.18

$\mathfrak{S}_n$ es el grupo de las permutaciones de $\intint{1}{n}$ (de orden $n!$ ). Un ciclo $(a_1\,a_2\,\cdots\,a_k)$ aplica $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ y deja fijo todo lo demás; $k$ es su longitud, y un ciclo de longitud $2$ es una transposición. Dos ciclos son disjuntos cuando lo son sus soportes (los puntos no fijos).

Teorema 1.19 (Descomposición en ciclos)

Toda permutación $\sigma \neq \mathrm{id}$ es producto de ciclos disjuntos dos a dos, de manera única salvo el orden de los factores. Los ciclos disjuntos conmutan, y $\operatorname{ord}(\sigma)$ es el mcm de las longitudes.

Demostración. Consideremos la relación de “órbita” sobre el soporte de $\sigma$ : $x \sim y$ si y solo si $y = \sigma^k(x)$ para algún $k \in \Z$ ; es una relación de equivalencia. Cada clase $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (finita, de modo que los iterados cierran el ciclo: la primera repetición ha de volver a $x$ por inyectividad) lleva asociado el ciclo $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ , y $\sigma$ es el producto de esos ciclos: sobre cada órbita solo actúa el ciclo correspondiente. Unicidad: toda factorización en ciclos disjuntos reproduce exactamente las órbitas (el ciclo que pasa por $x$ ha de ser $(x\ \sigma(x)\ \cdots)$ ). Los ciclos disjuntos conmutan porque mueven puntos disjuntos; el enunciado sobre el orden se sigue de que $\sigma^m = \mathrm{id}$ si y solo si lo es la potencia $m$ -ésima de cada ciclo (por disjunción), si y solo si cada longitud divide a $m$ . ∎

Ejemplo 1.20 (El tipo de ciclos como recuento)

¿Cuántas permutaciones de $\mathfrak{S}_9$ tienen el tipo de ciclos $(4, 3, 2)$ —un ciclo de longitud $4$ , uno de longitud $3$ y una transposición—? Se eligen los soportes y los órdenes cíclicos:

\frac{9!}{4\cdot 3\cdot 2} = \frac{362\,880}{24} = 15\,120 :

se alinean los nueve símbolos en fila ( $9!$ maneras), se agrupan los cuatro primeros, los tres siguientes y los dos últimos en ciclos y se divide por las rotaciones dentro de cada grupo ( $4$ , $3$ y $2$ respectivamente), que dan la misma permutación. (Aquí las longitudes de los ciclos son distintas, luego no hay que dividir más; con longitudes iguales habría que dividir además por las permutaciones de los grupos iguales.) Toda permutación de este tipo tiene orden $\operatorname{lcm}(4,3,2) = 12$ y signatura $(-1)^3(-1)^2(-1)^1 = +1$ (Teorema 1.19 y el teorema de la signatura de más abajo). Una partición de $9$ , una clase de conjugación, un recuento: la combinatoria de $\mathfrak{S}_n$ es la aritmética de las particiones.

Teorema 1.21 (Signatura)

Existe exactamente un morfismo de grupos $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (para $n \geq 2$ ) que vale $-1$ sobre las transposiciones: la signatura. Además, $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ , donde $I(\sigma)$ es el número de inversiones (pares $i < j$ con $\sigma(i) > \sigma(j)$ ); un ciclo de longitud $k$ tiene signatura $(-1)^{k-1}$ , y el grupo alternado $A_n = \ker\varepsilon$ tiene orden $\frac{n!}{2}$ .

Demostración. Existencia. Para $\sigma \in \mathfrak{S}_n$ pongamos

\varepsilon(\sigma) = \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i} .

Los valores absolutos de los factores se multiplican para dar $1$ (los pares no ordenados $\{\sigma(i), \sigma(j)\}$ recorren todos los pares), luego $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$ . Es morfismo: para $\sigma, \tau$ ,

\varepsilon(\sigma\tau) = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{j - i} = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{\tau(j) - \tau(i)} \cdot \prod_{i<j} \frac{\tau(j) - \tau(i)}{j - i} = \varepsilon(\sigma)\,\varepsilon(\tau),

donde el producto central vale $\varepsilon(\sigma)$ tras reindexar por los pares $\{\tau(i), \tau(j)\}$ (cada par no ordenado aparece una vez, y numerador y denominador cambian de signo a la vez). Una transposición $\tau = (a\,b)$ con $a < b$ tiene un número impar de inversiones; contémoslas exactamente: los pares invertidos $(i, j)$ , con $i < j$ y $\tau(i) > \tau(j)$ , son

(a, j) \ \text{con } a < j < b, \qquad (i, b) \ \text{con } a < i < b, \qquad (a, b) \ \text{mismo},

es decir $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ , un número impar. (Alternativamente: compruébese $(1\,2)$ directamente, con una sola inversión, y conjúguese —los conjugados tienen la misma signatura, pues $\varepsilon$ es un morfismo hacia un grupo abeliano—.) Por tanto $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

Unicidad. Las transposiciones generan $\mathfrak{S}_n$ : todo ciclo cumple

(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2),

y el Teorema 1.19 remata. Un morfismo hacia $\{\pm1\}$ queda determinado por sus valores sobre los generadores.

Consecuencias. La identidad anterior escribe un ciclo de longitud $k$ como producto de $k - 1$ transposiciones: signatura $(-1)^{k-1}$ . En cuanto a $A_n$ : el morfismo $\varepsilon$ es sobreyectivo (hay transposiciones para $n \geq 2$ ), y las dos “clases laterales” $A_n$ y $(1\,2)A_n$ son equipotentes y parten $\mathfrak{S}_n$ (argumento de Lagrange): $\abs{A_n} = \frac{n!}{2}$ . ∎

Ejemplo 1.22

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix} = (1\,3\,5)(2\,6)$ : orden $\operatorname{lcm}(3,2) = 6$ , signatura $(-1)^{2}\cdot(-1)^{1} = -1$ . La signatura es la comprobación de paridad más rápida sobre barajaduras, y el motor del determinante en el Capítulo 2.

Ejemplo 1.23 (Tres caminos hacia un mismo signo)

Sea $\sigma \in \mathfrak{S}_5$ la permutación que envía $1, 2, 3, 4, 5$ a $3, 5, 4, 1, 2$ . Por ciclos: $1 \mapsto 3 \mapsto 4 \mapsto 1$ y $2 \mapsto 5 \mapsto 2$ , luego $\sigma = (1\,3\,4)(2\,5)$ y $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$ . Por inversiones: en la lista de valores $3, 5, 4, 1, 2$ los pares desordenados son $(3,1)$ , $(3,2)$ , $(5,4)$ , $(5,1)$ , $(5,2)$ , $(4,1)$ , $(4,2)$ : siete, y $(-1)^7 = -1$ . Por transposiciones: $\sigma = (1\,4)(1\,3)(2\,5)$ , tres factores, $(-1)^3 = -1$ . Tres cálculos, una misma paridad: la unicidad del Teorema 1.21 garantiza que ningún sistema de recuento puede hacerlos discrepar, y eso es exactamente lo que convierte a $\varepsilon$ en un invariante utilizable (véase el problema de fin de semana).

Observación 1.24 (Adónde va la signatura a partir de aquí)

La signatura es la semilla de tres cosechas posteriores: construye el determinante y su regla del producto en el Capítulo 2; alimenta invariantes de paridad para rompecabezas combinatorios (el problema de fin de semana de este capítulo resuelve con ella el juego del quince); y los grupos alternados $A_n$ que define pasan a ocupar un lugar central en el volumen del tercer año, donde su simplicidad para $n \geq 5$ explica que las ecuaciones de grado $5$ no se resuelvan por radicales.

1.5 Anillos, ideales, cocientes

Definición 1.25 (Ideal)

Sea $A$ un anillo conmutativo. Un ideal $I \subseteq A$ es un subgrupo aditivo tal que $a x \in I$ para todos $a \in A$ , $x \in I$ . Los núcleos de morfismos de anillos son ideales; $I = A$ si y solo si $1 \in I$ , si y solo si $I$ contiene una unidad. El ideal generado por $x$ es $xA = \{xa\}$ (un ideal principal).

Teorema 1.26 (Ideales de $\Z$ y de $K[X]$ )

Todo ideal de $\Z$ es de la forma $n\Z$ para un único $n \in \N$ ; todo ideal de $K[X]$ ( $K$ un cuerpo) es de la forma $P\,K[X]$ para un único $P$ mónico (o nulo). En consecuencia, existen máximos comunes divisores en ambos anillos, con relaciones de Bézout: $x\Z + y\Z = \gcd(x,y)\Z$ , y análogamente para polinomios.

Demostración. Para $\Z$ esto era el teorema sobre subgrupos del volumen del primer año (un ideal es en particular un subgrupo, y $n\Z$ es un ideal). Para $K[X]$ : sea $I \neq \{0\}$ un ideal y $P \in I$ no nulo de grado mínimo, normalizado mónico. Para $F \in I$ , la división euclídea $F = PQ + R$ da $R = F - PQ \in I$ con $\deg R < \deg P$ : la minimalidad obliga a $R = 0$ , luego $I = P\,K[X]$ . Unicidad: dos generadores mónicos se dividen mutuamente. Los enunciados de Bézout expresan la igualdad del ideal $x\Z + y\Z$ (o de su análogo polinómico) con el ideal principal del mcd —la propia definición de mcd usada en el primer año, reconocida ahora como un enunciado sobre ideales—. ∎

Ejemplo 1.27 (Un mcd de polinomios, de dos maneras)

Calculemos $\gcd(X^3 - 1,\ X^2 - 1)$ en $\Q[X]$ . Por Euclides:

X^3 - 1 = X\,(X^2 - 1) + (X - 1), \qquad X^2 - 1 = (X + 1)(X - 1) + 0 ,

luego el mcd es $X - 1$ , y remontando la división se obtiene la relación de Bézout

X - 1 = 1\cdot(X^3 - 1) - X\cdot(X^2 - 1).

Por ideales: el ideal $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ es principal (Teorema 1.26); contiene a $X - 1$ (por la fórmula anterior) y está contenido en $(X - 1)\Q[X]$ (ambos generadores se anulan en $1$ , luego son múltiplos de $X - 1$ ): el generador mónico es $X - 1$ . La moraleja: el punto de vista de los ideales identifica el mcd sin dividir —las raíces comunes localizan el ideal y Euclides se limita a certificarlo—.

Definición 1.28 (El anillo cociente $\Z/n\Z$ , revisitado)

Para un ideal $I$ de $A$ , la relación $x \sim y \iff x - y \in I$ es una equivalencia compatible con $+$ y $\times$ ; el conjunto cociente $A/I$ hereda una estructura de anillo —el anillo cociente— que hace de $\pi \colon A \to A/I$ un morfismo de núcleo $I$ . Para $A = \Z$ e $I = n\Z$ esto es el $\Z/n\Z$ del volumen del primer año, ahora con su propiedad universal: todo morfismo que anula $I$ factoriza a través de $A/I$ .

Teorema 1.29 (Teorema chino del resto, forma anular)

Si $\gcd(m, n) = 1$ , la aplicación

\Z/mn\Z \longrightarrow \Z/m\Z \times \Z/n\Z, \qquad \overline{x} \longmapsto (x \bmod m,\; x \bmod n)

es un isomorfismo de anillos. En consecuencia, $\varphi(mn) = \varphi(m)\varphi(n)$ para $m, n$ primos entre sí, y

\varphi(n) = n \prod_{p \mid n} \Bigl(1 - \frac 1p\Bigr) \quad (p \text{ primo}).

Demostración. La aplicación es un morfismo de anillos bien definido (las compatibilidades son inmediatas). Inyectividad: si $x \equiv 0$ módulo $m$ y módulo $n$ con $\gcd(m,n) = 1$ , entonces $mn \mid x$ (Gauss). Sobreyectividad: ambos lados tienen $mn$ elementos, así que basta la inyectividad (cardinales finitos iguales); o explícitamente, a partir de una relación de Bézout $um + vn = 1$ , la clase de

x = b\,um + a\,vn

se aplica en $(a \bmod m,\ b \bmod n)$ , pues $vn = 1 - um \equiv 1 \pmod m$ hace que $x \equiv a \pmod m$ , y simétricamente módulo $n$ —la receta usada numéricamente en el Ejemplo 1.30—. Las unidades se corresponden con los pares de unidades (las unidades de un anillo producto son los pares de unidades), luego $\varphi(mn) = \varphi(m)\varphi(n)$ . Para una potencia de primo, $\varphi(p^k) = p^k - p^{k-1}$ (los no invertibles módulo $p^k$ son los múltiplos de $p$ ); la multiplicatividad ensambla la fórmula del producto. ∎

Ejemplo 1.30 (Inversión del isomorfismo chino)

Tomemos $m = 8$ , $n = 9$ . La inversa del isomorfismo se hace explícita mediante dos idempotentes: buscamos $u \equiv 1 \pmod 8$ , $u \equiv 0 \pmod 9$ y $v \equiv 0 \pmod 8$ , $v \equiv 1 \pmod 9$ . De $u = 9k \equiv 1 \pmod 8$ resulta $k \equiv 1$ , luego $u = 9$ ; de $v = 8k \equiv 1 \pmod 9$ resulta $-k \equiv 1$ , $k \equiv 8$ , luego $v = 64$ . Entonces la clase de $x = 9a + 64b$ módulo $72$ es la única solución de $x \equiv a \pmod 8$ , $x \equiv b \pmod 9$ : para $a = 3$ , $b = 5$ se obtiene $27 + 320 = 347 \equiv 59 \pmod{72}$ , exactamente el valor intermedio hallado por sustitución en el Ejercicio 1.8. La moraleja: $u$ y $v$ cumplen $u + v \equiv 1$ , $uv \equiv 0$ , $u^2 \equiv u$ , $v^2 \equiv v$ módulo $72$ ; son las imágenes de $(1, 0)$ y $(0, 1)$ , y toda descomposición china es, en el fondo, una descomposición de $1$ en idempotentes ortogonales.

Teorema 1.31 (Euler; Fermat revisitado)

Las unidades de $\Z/n\Z$ forman un grupo de orden $\varphi(n)$ ; por tanto, si $\gcd(a, n) = 1$ ,

a^{\varphi(n)} \equiv 1 \pmod n \qquad (\text{teorema de Euler}),

y el pequeño teorema de Fermat es el caso $n = p$ primo, ahora a una línea de Lagrange.

Demostración. Las clases invertibles son exactamente las de los enteros primos con $n$ (volumen del primer año): hay $\varphi(n)$ , y forman un grupo para la multiplicación. Por Lagrange (Teorema 1.14), todo elemento elevado al orden del grupo da el neutro. ∎

Ejemplo 1.32 (Un grupo de unidades sin generador)

El grupo $(\Z/15\Z)^*$ tiene $\varphi(15) = \varphi(3)\varphi(5) = 8$ elementos. ¿Es cíclico? Calculemos órdenes con el isomorfismo chino $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (una unidad módulo $15$ es un par de unidades): los factores tienen órdenes $2$ y $4$ , luego el orden de todo elemento divide a $\operatorname{lcm}(2, 4) = 4 < 8$ ; ninguno genera. En concreto:

2^4 = 16 \equiv 1, \qquad 4^2 = 16 \equiv 1, \qquad 7^4 \equiv 1, \qquad 11^2 = 121 \equiv 1, \qquad 14^2 \equiv 1 \pmod{15} :

órdenes $4, 2, 4, 2, 2$ y nunca $8$ . Compárese con el Ejercicio 1.10: $(\Z/p\Z)^*$ sí es cíclico para $p$ primo, porque allí el grupo de unidades vive dentro de un cuerpo. El teorema de Euler sigue valiendo con exponente $\varphi(15) = 8$ , pero el verdadero exponente universal aquí es $4$ : Euler da una cota superior, no siempre la óptima.

Definición 1.33 (Álgebra)

Una $K$ -álgebra es un $K$ -espacio vectorial $A$ dotado de una estructura de anillo cuya multiplicación es $K$ -bilineal. Ejemplos: $K[X]$ , $\mathcal{M}_n(K)$ , $\mathcal{L}(E)$ , los espacios de funciones $\mathcal{F}(X, K)$ , $\C$ como $\R$ -álgebra. Los morfismos de álgebras son los morfismos de anillos lineales; la evaluación $P \mapsto P(u)$ de $K[X]$ en $\mathcal{L}(E)$ (o en $\mathcal{M}_n(K)$ ) es el ejemplo central, y es el motor del Capítulo 3.

Ejemplo 1.34 (Un morfismo de evaluación y su núcleo)

Tomemos $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ y la evaluación $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$ , $P \mapsto P(A)$ . Como $A^2 = 0$ ,

P(A) = P(0)\,I + P'(0)\,A = \begin{pmatrix} P(0) & P'(0)\\ 0 & P(0)\end{pmatrix},

(solo sobreviven los términos constante y lineal de $P$ ). Por tanto $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$ : un ideal principal, exactamente como predice el Teorema 1.26, generado por el polinomio mónico $X^2$ de menor grado del núcleo —el polinomio mínimo de $A$ , protagonista del Capítulo 3—. La imagen es el álgebra conmutativa de dimensión dos $\{aI + bA\}$ : los morfismos de evaluación comprimen el $\R[X]$ de dimensión infinita sobre álgebras pequeñas y calculables.

Observación 1.35 (Perspectivas: tres melodías que conviene escuchar)

Tres ideas estructurales de este capítulo reaparecen a lo largo del volumen, cada vez con orquestación más densa. La factorización a través de un cociente (Definición 1.3): construye aquí $\Z/n\Z$ , define aplicaciones sobre los conjuntos de soluciones de sistemas lineales en el Capítulo 2 y subyace en silencio a todo argumento del tipo “está bien definido sobre las clases”. Los invariantes: la signatura es un morfismo hacia $\{\pm1\}$ que ningún movimiento legal puede esquivar; la misma lógica da la regla del producto del determinante (Capítulo 2), la invariancia de la traza por semejanza y las cantidades conservadas del Capítulo 16. El recuento contra una estructura: Lagrange cuenta mediante clases laterales, la dimensión cuenta mediante bases (Capítulo 2), la multiplicidad cuenta mediante grados de polinomios (Capítulo 3); siempre que una cota parezca milagrosa, alguna partición o graduación está haciendo el recuento.

Observación 1.36 (Errores frecuentes)

Cuatro clásicos. (i) Una aplicación definida sobre un cociente debe comprobarse bien definida: “ $\overline x \mapsto$ (fórmula en $x$ )” solo es legítimo si la fórmula es constante sobre las clases —la compatibilidad de la Definición 1.3, y no un mero formalismo—. (ii) La igualdad $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ es falsa en general, incluso para elementos que conmutan ( $a$ y $a^{-1}$ ); el Ejercicio 1.4 da el enunciado correcto para órdenes primos entre sí, y los ciclos disjuntos la versión correcta para permutaciones. (iii) La numerabilidad se conserva por uniones numerables y por productos finitos, pero no por productos numerables: $\{0,1\}^{\N}$ no es numerable (Ejercicio 1.3) aunque cada factor tenga dos elementos. (iv) Cantor–Bernstein solo necesita inyecciones en ambos sentidos, pero la biyección que construye suele ser discontinua y no explícita: no hay que esperar una fórmula (Ejemplo 1.11).

Observación 1.37 (Dónde se usa este capítulo)

Casi en todas partes. La signatura construye los determinantes (Capítulo 2); el morfismo de evaluación $P \mapsto P(u)$ y los ideales principales de $K[X]$ producen los polinomios mínimos y las descomposiciones en núcleos del Capítulo 3; la numerabilidad es el escenario sobre el que actúa el Capítulo 21 (probabilidad sobre espacios numerables) y la razón de que la topología no deje de producir conjuntos densos numerables (Capítulo 4). La construcción del cociente $A/I$ se redespliega en el volumen del tercer año para construir cuerpos $K[X]/(P)$ y, a partir de ellos, la teoría de Galois: la propiedad universal demostrada aquí se usa allí palabra por palabra.

1.6 Ejercicios

Ejercicio 1.1 ★

¿Cuáles de los siguientes conjuntos son numerables? El conjunto de los subconjuntos finitos de $\N$ ; el conjunto de todos los subconjuntos de $\N$ ; $\R \setminus \Q$ ; el conjunto de los polinomios con coeficientes racionales; el conjunto de las sucesiones de $0$ y de $1$ que son nulas a partir de un cierto índice.

Solución

Solución de Ejercicio 1.1.

Subconjuntos finitos de $\N$ : numerable —el conjunto de los subconjuntos de $\intint{0}{n}$ es finito, y los subconjuntos finitos forman la unión numerable sobre $n$ de estos (Proposición 1.6 (3))—; infinito, porque contiene todos los conjuntos unitarios.

Todos los subconjuntos de $\N$ : no numerable, por el teorema de Cantor (Teorema 1.9 (1) con $E = \N$ ).

$\R \setminus \Q$ : no numerable —en otro caso $\R = \Q \cup (\R\setminus\Q)$ sería unión de dos conjuntos numerables, en contradicción con el Teorema 1.9 (2)—.

Polinomios sobre $\Q$ : numerable —los polinomios de grado $\leq n$ se inyectan en $\Q^{n+1}$ (productos finitos de conjuntos numerables); tómese después la unión sobre $n$ —.

Sucesiones binarias nulas a partir de un índice: numerable —están en biyección con los subconjuntos finitos de $\N$ (el soporte)—.

Ejercicio 1.2 ★

En $\mathfrak{S}_7$ , sean $\sigma = (1\,4\,2\,6)(3\,5)$ y $\tau = (2\,3\,7)$ . Calcula $\sigma\tau$ y $\tau\sigma$ en forma de ciclos disjuntos, los órdenes y las signaturas de las cuatro permutaciones, y $\sigma^{2026}$ .

Solución

Solución de Ejercicio 1.2.

Se calcula elemento a elemento, aplicando primero el factor de la derecha. $\sigma\tau$ envía $1 \mapsto \sigma(1) = 4$ , $\;2 \mapsto \sigma(3) = 5$ , $\;3 \mapsto \sigma(7) = 7$ , $\;4 \mapsto \sigma(4) = 2$ , $\;5 \mapsto \sigma(5) = 3$ , $\;6 \mapsto \sigma(6) = 1$ , $\;7 \mapsto \sigma(2) = 6$ :

\sigma\tau = (1\,4\,2\,5\,3\,7\,6),

un ciclo de longitud $7$ . Análogamente, $\tau\sigma$ envía $1 \mapsto \tau(4) = 4$ , $\;2 \mapsto \tau(6) = 6$ , $\;3 \mapsto \tau(5) = 5$ , $\;4 \mapsto \tau(2) = 3$ , $\;5 \mapsto \tau(3) = 7$ , $\;6 \mapsto \tau(1) = 1$ , $\;7 \mapsto \tau(7) = 2$ :

\tau\sigma = (1\,4\,3\,5\,7\,2\,6),

también un ciclo de longitud $7$ (como cabía esperar: $\sigma\tau$ y $\tau\sigma$ son conjugadas y por tanto comparten su tipo de ciclos).

Órdenes y signaturas: $\sigma$ tiene tipo de ciclos $(4,2)$ : orden $\operatorname{lcm}(4,2) = 4$ , signatura $(-1)^3(-1)^1 = +1$ ; $\tau$ es un ciclo de longitud $3$ : orden $3$ , signatura $+1$ ; ambos productos son ciclos de longitud $7$ : orden $7$ , signatura $(-1)^6 = +1$ .

$\sigma^{2026}$ : como $2026 = 4 \times 506 + 2$ , se tiene $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (se eleva al cuadrado el ciclo de longitud $4$ ; la transposición desaparece al cuadrarla).

Ejercicio 1.3 ★

Construye inyecciones explícitas que muestren que $\mathcal{P}(\N)$ , $\intcc{0}{1}$ y el conjunto $\{0,1\}^{\N}$ de las sucesiones binarias son equipotentes dos a dos (desarrollos binarios en ambos sentidos; Cantor–Bernstein absorbe la molestia de la doble representación).

Solución

Solución de Ejercicio 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : una sucesión se aplica en su soporte; es una biyección (funciones indicadoras) y no hace falta ningún teorema.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : la aplicación en base $3$ dada por $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ es inyectiva (dos sucesiones distintas difieren por primera vez en un rango $N$ ; las colas no pueden compensar una separación de $2\cdot 3^{-N-1}$ , ya que $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} < 2\cdot3^{-N-1}$ ).

$\intcc{0}{1} \to \{0,1\}^{\N}$ : desarrollo binario, eligiendo (por ejemplo) el que no termina en infinitos $1$ : es inyectiva.

Por Cantor–Bernstein (Teorema 1.10) aplicado a las dos últimas inyecciones, $\intcc{0}{1}$ y $\{0,1\}^{\N}$ son equipotentes, y en consecuencia los tres conjuntos lo son.

Ejercicio 1.4 ★

Sea $G$ un grupo y $a, b \in G$ dos elementos que conmutan, de órdenes finitos $m$ y $n$ primos entre sí. Demuestra que $\operatorname{ord}(ab) = mn$ . Muestra con un ejemplo en $\mathfrak{S}_3$ que la conmutación es esencial.

Solución

Solución de Ejercicio 1.4.

Sea $c = ab = ba$ y $d = \operatorname{ord}(c)$ . En primer lugar, $c^{mn} = a^{mn} b^{mn} = e$ (la conmutación permite separar la potencia), luego $d \mid mn$ . Recíprocamente, $c^d = e$ da $a^d = b^{-d}$ ; este elemento pertenece a $\langle a\rangle \cap \langle b\rangle$ , subgrupo cuyo orden divide a la vez a $m$ y a $n$ (Lagrange en cada grupo cíclico) y que, por tanto, es trivial: $a^d = b^d = e$ , así que $m \mid d$ y $n \mid d$ , y por coprimalidad $mn \mid d$ . Luego $d = mn$ .

En $\mathfrak{S}_3$ : tómense $a = (1\,2)$ (de orden $2$ ) y $b = (1\,2\,3)$ (de orden $3$ ), de órdenes primos entre sí, que no conmutan: $ab = (2\,3)$ tiene orden $2 \neq 6$ —de hecho, $\mathfrak{S}_3$ no tiene ningún elemento de orden $6$ —. La conmutación es esencial.

Ejercicio 1.5 ★★

Sea $G$ un grupo finito de orden par. Demuestra que $G$ contiene un elemento de orden $2$ . (Emparéjese cada elemento con su inverso y cuéntense los que quedan emparejados consigo mismos.)

Solución

Solución de Ejercicio 1.5.

Emparejemos cada $x \in G$ con $x^{-1}$ . Los pares $\{x, x^{-1}\}$ con $x \neq x^{-1}$ tienen dos elementos y forman una partición de su unión; los elementos restantes son exactamente aquellos con $x = x^{-1}$ , es decir, $x^2 = e$ . Como $\abs G$ es par y los pares de dos elementos cubren un número par de elementos, el conjunto $\{x : x^2 = e\}$ tiene cardinal par; contiene a $e$ , luego contiene al menos otro elemento $x \neq e$ : un elemento de orden $2$ .

Ejercicio 1.6 ★★

Demuestra que $A_n$ ( $n \geq 3$ ) está generado por los ciclos de longitud $3$ . (Un producto de dos transposiciones es un ciclo de longitud $3$ o un producto de dos ciclos de longitud $3$ .)

Solución

Solución de Ejercicio 1.6.

Todo elemento de $A_n$ es producto de un número par de transposiciones (Teorema 1.21: descompóngase en transposiciones; el número es par porque la signatura vale $+1$ ). Basta con escribir cada producto de dos transposiciones mediante ciclos de longitud $3$ :

(a\,b)(a\,c) = (a\,c\,b), \qquad (a\,b)(c\,d) = (a\,c\,b)(a\,c\,d) \quad (a,b,c,d \text{ distintos}),

(compruébese evaluando), junto con $(a\,b)(a\,b) = \mathrm{id}$ . Así pues, los ciclos de longitud $3$ generan $A_n$ .

Ejercicio 1.7 ★★

Determina todos los morfismos de grupos: de $(\Q, +)$ en $(\Z, +)$ ; de $(\Z/n\Z, +)$ en $(\Z/m\Z, +)$ (cuéntalos: hay $\gcd(m,n)$ ); de $(\Q, +)$ en $(\Q_+^*, \times)$ .

Solución

Solución de Ejercicio 1.7.

$(\Q,+) \to (\Z,+)$ : solo el morfismo nulo. Para todo $x$ y todo $n \geq 1$ , $f(x) = n f\bigl(\frac xn\bigr)$ es divisible por $n$ en $\Z$ ; el único entero divisible por todo $n$ es $0$ , luego $f(x) = 0$ para todo $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : un morfismo queda determinado por $c = f(\overline 1)$ , que ha de cumplir $n c \equiv 0 \pmod m$ , es decir, $c$ es múltiplo de $\frac{m}{\gcd(m,n)}$ ; hay $\gcd(m,n)$ clases así, y cada elección define efectivamente un morfismo (factorícese $k \mapsto kc$ a través de $\Z/n\Z$ por la propiedad universal).

$(\Q, +) \to (\Q_+^*, \times)$ : solo el trivial. Si $f(x) = y$ , entonces para todo $n$ se tiene $y = f(n \cdot \frac xn) = f(\frac xn)^n$ , una potencia $n$ -ésima en $\Q_+^*$ . Pero un racional $y \neq 1$ no puede ser potencia $n$ -ésima para todo $n$ : algún primo aparece en $y$ con exponente $v$ no nulo, y $n \nmid v$ para $n > \abs v$ (los exponentes de las potencias $n$ -ésimas son múltiplos de $n$ , por la factorización única). Por tanto $f \equiv 1$ .

Ejercicio 1.8 ★★

Usando el teorema chino del resto, calcula $\varphi(360)$ , halla todos los $x$ con $x \equiv 3 \pmod 8$ , $x \equiv 5 \pmod 9$ y $x \equiv 2 \pmod 5$ , y calcula las dos últimas cifras de $3^{2026}$ (Euler módulo $100$ ; atención: trabaja módulo $4$ y módulo $25$ ).

Solución

Solución de Ejercicio 1.8.

$360 = 2^3 \cdot 3^2 \cdot 5$ : $\varphi(360) = 360\bigl(1 - \tfrac12\bigr)\bigl(1 - \tfrac13\bigr)\bigl(1 - \tfrac15\bigr) = 360 \cdot \tfrac12 \cdot \tfrac23 \cdot \tfrac45 = 96$ .

Sistema: los módulos $8, 9, 5$ son primos entre sí dos a dos y su producto es $360$ . De $x \equiv 3 \pmod 8$ y $x \equiv 5 \pmod 9$ : $x = 3 + 8k$ con $3 + 8k \equiv 5 \pmod 9$ , es decir, $-k \equiv 2$ , $k \equiv -2 \equiv 7 \pmod 9$ : $x \equiv 3 + 56 = 59 \pmod{72}$ . Después, $59 + 72\ell \equiv 2 \pmod 5$ : $4 + 2\ell \equiv 2$ , $2\ell \equiv 3 \equiv 8$ , $\ell \equiv 4 \pmod 5$ : $x \equiv 59 + 288 = 347 \pmod{360}$ .

Dos últimas cifras de $3^{2026}$ : módulo $4$ , $3^{2026} = 9^{1013} \equiv 1$ . Módulo $25$ : $\varphi(25) = 20$ y $2026 = 20\cdot101 + 6$ , luego $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$ . Resolvamos $x \equiv 1 \pmod 4$ , $x \equiv 4 \pmod{25}$ : de $x = 4 + 25k \equiv 1 \pmod 4$ resulta $k \equiv 1 \pmod 4$ , luego $x \equiv 29 \pmod{100}$ . Las dos últimas cifras son $29$ .

Ejercicio 1.9 ★★★

Demuestra que todo dominio de integridad finito es un cuerpo. Deduce que $\Z/n\Z$ es un cuerpo si y solo si $n$ es primo (de nuevo).

Solución

Solución de Ejercicio 1.9.

Sea $A$ un dominio de integridad finito y $a \in A$ , $a \neq 0$ . La aplicación $x \mapsto ax$ es inyectiva ( $ax = ay \implies a(x - y) = 0 \implies x = y$ , pues no hay divisores de cero); y una aplicación inyectiva de un conjunto finito en sí mismo es sobreyectiva (volumen del primer año, la equivalencia del principio del palomar). Luego $1 = ab$ para algún $b$ : todo elemento no nulo es invertible y $A$ es un cuerpo.

$\Z/n\Z$ : si $n$ es primo, es un dominio de integridad ( $n \mid ab \implies n \mid a$ o $n \mid b$ , lema de Euclides), finito y por tanto un cuerpo; si $n = rs$ es compuesto, $\overline r\,\overline s = \overline 0$ exhibe divisores de cero.

Ejercicio 1.10 ★★★

(Un clásico) Sea $K$ un cuerpo y $G$ un subgrupo finito de $(K^*, \times)$ . Demuestra que $G$ es cíclico. Indicación: sea $m$ el orden máximo entre los elementos de $G$ ; prueba que el orden de todo elemento divide a $m$ (aplicando el Ejercicio 1.4 a partes coprimas adecuadas), de modo que todo $G$ satisface $x^m = 1$ ; cuenta después las raíces de $X^m - 1$ . En particular, $(\Z/p\Z)^*$ es cíclico.

Solución

Solución de Ejercicio 1.10.

Sea $m = \max\{\operatorname{ord}(x) : x \in G\}$ , alcanzado en $a$ .

Afirmación: el orden de todo $x \in G$ divide a $m$ . Supongamos que algún $x$ tiene orden $q$ con $q \nmid m$ : entonces alguna potencia de primo $p^k$ divide a $q$ pero no a $m$ . Escribamos $m = p^j m'$ con $p \nmid m'$ y $j < k$ . El elemento $a^{p^j}$ tiene orden $m'$ ; el elemento $x^{q/p^k}$ tiene orden $p^k$ ; estos órdenes son primos entre sí y los dos elementos conmutan ( $G \subseteq K^*$ es abeliano), de modo que por el Ejercicio 1.4 su producto tiene orden $p^k m' > p^j m' = m$ , en contra de la maximalidad.

Así pues, todo $x \in G$ cumple $x^m = 1$ : el polinomio $X^m - 1$ tiene al menos $\abs G$ raíces en el cuerpo $K$ , luego $\abs G \leq m$ (un polinomio no nulo de grado $m$ tiene a lo sumo $m$ raíces, volumen del primer año). Pero $m = \operatorname{ord}(a) \leq \abs G$ por Lagrange. Por tanto $m = \abs G$ y $\langle a \rangle$ , de cardinal $m = \abs G$ , es todo $G$ : cíclico.

Para $K = \Z/p\Z$ : $(\Z/p\Z)^*$ es un subgrupo finito de $K^*$ , luego cíclico (de orden $p - 1$ ).

Ejercicio 1.11 ★★★

Demuestra que el grupo $(\Q, +)$ no es cíclico y, peor aún, que ni siquiera es finitamente generado. Demuestra en cambio que todo subgrupo finitamente generado de $(\Q, +)$ es cíclico.

Solución

Solución de Ejercicio 1.11.

No es cíclico: el subgrupo $\langle \frac pq\rangle$ está formado por los múltiplos enteros de $\frac pq$ , todos ellos con denominador divisor de $q$ (en forma irreducible); por tanto no alcanza $\frac{1}{2q}$ . Ningún generador único puede alcanzar los denominadores arbitrariamente grandes de $\Q$ .

No es finitamente generado: el subgrupo generado por $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ está formado por racionales cuyos denominadores dividen a $Q = q_1 \cdots q_k$ (las combinaciones enteras tienen denominador divisor de $Q$ ): no alcanza $\frac{1}{2Q}$ .

Los subgrupos finitamente generados son cíclicos: con $Q$ como antes, el subgrupo $H = \langle \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}\rangle$ está contenido en $\frac{1}{Q}\Z$ . La aplicación $x \mapsto Qx$ es un isomorfismo de $\frac1Q\Z$ sobre $\Z$ que lleva $H$ a un subgrupo de $\Z$ , que es $n\Z$ para algún $n$ (volumen del primer año): luego $H = \frac{n}{Q}\Z$ es cíclico, generado por $\frac nQ$ .

Ejercicio 1.12 ★★

(Criterio de Dedekind) Demuestra que todo conjunto infinito contiene un subconjunto numerable y deduce que un conjunto $E$ es infinito si y solo si es equipotente a un subconjunto propio de sí mismo. (Para la implicación directa, desplaza un subconjunto numerable un paso; para la recíproca, recuerda el principio del palomar.)

Solución

Solución de Ejercicio 1.12.

Un subconjunto numerable. Sea $E$ infinito. Construyamos $a_0, a_1, a_2, \dots$ por inducción: $E$ no es vacío, elijamos $a_0 \in E$ ; si $a_0, \dots, a_n$ ya están elegidos, $E \setminus \{a_0, \dots, a_n\}$ no es vacío ( $E$ no es finito) y elegimos allí $a_{n+1}$ . Los $a_n$ son distintos dos a dos por construcción, luego $A = \{a_n : n \in \N\}$ es un subconjunto numerable de $E$ .

Infinito $\implies$ equipotente a un subconjunto propio. Definamos $f \colon E \to E \setminus \{a_0\}$ por $f(a_n) = a_{n+1}$ y $f(x) = x$ para $x \notin A$ . Es inyectiva (los dos trozos lo son y tienen imágenes disjuntas) y sobreyectiva sobre $E \setminus \{a_0\}$ : se alcanza cada $a_{n+1}$ y cada $x \notin A$ . Luego $E$ es equipotente al subconjunto propio $E \setminus \{a_0\}$ .

Recíproco. Si $E$ es finito y $g \colon E \to F$ es una biyección sobre $F \subseteq E$ con $F \neq E$ , entonces $g$ es una inyección de $E$ en sí mismo que no es sobreyectiva, en contradicción con el principio del palomar (volumen del primer año: una aplicación inyectiva de un conjunto finito en sí mismo es biyectiva). Por tanto, un conjunto equipotente a un subconjunto propio es infinito.

1.7 Problema: el juego del quince

El juego del quince es una bandeja de $4 \times 4$ con quince fichas deslizantes numeradas del $1$ al $15$ y una casilla vacía; un movimiento desliza a la casilla vacía una de las fichas contiguas a ella. En la década de 1890 Sam Loyd popularizó el juego ofreciendo 1000 dólares a quien lograra intercambiar las fichas $14$ y $15$ devolviendo todas las demás a su sitio. Nadie cobró nunca, y este problema de fin de semana demuestra las dos mitades de la razón: la signatura del Teorema 1.21 prohíbe el intercambio de Loyd y —la mitad más difícil, la constructiva— todo lo que la signatura permite es de verdad realizable. El enunciado completo es el teorema de Johnson–Story (1879).

La configuración resuelta y la configuración 14–15 de Sam Loyd. La pregunta de los 1000 dólares: ¿pueden unos deslizamientos legales convertir la bandeja de la derecha en la de la izquierda? — La configuración resuelta y la configuración $14$ – $15$ de Sam Loyd. La pregunta de los 1000 dólares: ¿pueden unos deslizamientos legales convertir la bandeja de la derecha en la de la izquierda?

Problema 1.1

Problema de fin de semana — el teorema de resolubilidad de Johnson–Story

Numeremos las casillas del $1$ al $16$ en orden de lectura (de izquierda a derecha y de arriba abajo), de modo que la casilla $k$ ocupe la fila $i$ y la columna $j$ con $k = 4(i - 1) + j$ . La casilla $16$ (abajo a la derecha) es la casa de la casilla vacía; trataremos la casilla vacía como una decimosexta ficha, escrita $b$ e identificada con el número $16$ . Una configuración es una biyección $\sigma \colon \intint1{16} \to \intint1{16}$ , casilla $\mapsto$ contenido; la configuración resuelta es $\sigma = \mathrm{id}$ . En todo el problema, $\varepsilon$ es la signatura del Teorema 1.21 y dos casillas son contiguas cuando comparten un lado de la bandeja.

Parte I — Configuraciones, movimientos, signaturas.

Justifica que las configuraciones son exactamente los elementos de $\mathfrak{S}_{16}$ , de modo que hay $16! = 20\,922\,789\,888\,000$ , y que el número de movimientos legales desde una configuración dada es $2$ , $3$ o $4$ , según que la casilla vacía esté en una esquina, en un borde o en el interior.
Sea $\sigma$ una configuración, $p = \sigma^{-1}(16)$ la casilla del hueco y $c$ una casilla contigua a $p$ . Prueba que deslizar la ficha de $c$ hasta $p$ produce la configuración $\sigma' = \sigma \circ \tau$ con $\tau = (p\ c)$ , y deduce que todo movimiento cambia el signo de la signatura: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
Colorea la bandeja como un tablero de ajedrez: $\chi(k) = (-1)^{i+j}$ para la casilla $k$ situada en la fila $i$ y la columna $j$ . Prueba que todo movimiento cambia el signo de $\chi(\text{casilla del hueco})$ y deduce que una sucesión de movimientos que devuelve el hueco a su casilla de partida tiene longitud par.
Prueba que

$I(\sigma) = \varepsilon(\sigma)\, \chi\bigl(\sigma^{-1}(16)\bigr)$

es invariante por todo movimiento legal, y calcula $I(\mathrm{id})$ .

Parte II — El premio de Loyd: el invariante en acción.

La configuración $\sigma_L$ de Loyd coincide con la resuelta salvo que las casillas $14$ y $15$ contienen las fichas $15$ y $14$ . Calcula $I(\sigma_L)$ y concluye que ninguna sucesión de movimientos une $\sigma_L$ con la configuración resuelta: los 1000 dólares de Loyd nunca corrieron peligro.
Prueba que exactamente la mitad de las configuraciones cumplen $I = +1$ : $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (Para una casilla vacía fija, emparéjense las configuraciones componiendo con una transposición fija de otras dos casillas.)
Prueba que todo movimiento se deshace mediante un movimiento legal, que “ $\sigma'$ es alcanzable desde $\sigma$ mediante movimientos legales” es una relación de equivalencia, y que la clase $R$ de la configuración resuelta cumple $R \subseteq \{I = +1\}$ . Concluye que hay al menos dos clases.
Supongamos que el hueco está en casa: $\sigma(16) = 16$ . Prueba que $I(\sigma) = \varepsilon(\rho)$ , donde $\rho \in \mathfrak{S}_{15}$ es la restricción de $\sigma$ a las casillas $1, \dots, 15$ , y que toda configuración puede llevarse mediante movimientos legales a otra con el hueco en casa. Concluye: para demostrar que $R = \{I = +1\}$ basta con realizar toda permutación par de las quince casillas distintas de la casa mediante una sucesión de movimientos que empiece y termine con el hueco en casa.

Parte III — Recorridos del hueco y grupo de programas. Un programa es una sucesión finita de movimientos legales, iniciada en una configuración con el hueco en casa, cuya configuración final tiene también el hueco en casa. Su efecto es la permutación $\pi$ de las casillas definida por: el contenido de la casilla $x$ acaba en la casilla $\pi(x)$ .

Prueba que un programa ejecutado desde $\sigma$ termina en $\sigma \circ \pi^{-1}$ ; que ejecutar dos programas seguidos compone sus efectos; y que el conjunto $H$ de todos los efectos es un subgrupo de $\mathfrak{S}_{15}$ (permutaciones de las casillas $1, \dots, 15$ ) contenido en el grupo alternado $A_{15}$ .
(El recorrido elemental) Con el hueco en casa, hazlo circular por el bloque $2 \times 2$ inferior derecho: casillas $16 \to 12 \to 11 \to 15 \to 16$ . Prueba que el efecto es el ciclo $(11\ 12\ 15)$ y que el recorrido inverso da $(11\ 15\ 12)$ . Ambos pertenecen a $H$ .
(El gran recorrido) Comprueba que

$16 \to 15 \to 14 \to 13 \to 9 \to 5 \to 1 \to 2 \to 3 \to 4 \to 8 \to 7 \to 6 \to 10 \to 11 \to 12 \to 16$

es un camino cerrado que pasa por las dieciséis casillas (con pasos entre casillas contiguas únicamente), y que su efecto es el ciclo de longitud $15$

$\zeta = (15\ 12\ 11\ 10\ 6\ 7\ 8\ 4\ 3\ 2\ 1\ 5\ 9\ 13\ 14) .$

Escribiendo $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , …, $x_{14} = 14$ para su orden cíclico, comprueba que el recorrido elemental inverso de la pregunta 10 es exactamente $(x_0\ x_1\ x_2)$ .
Demuestra la fórmula de conjugación en cualquier $\mathfrak{S}_n$ : para una permutación $g$ y un ciclo de longitud $3$ ,

$g\,(a\ b\ c)\,g^{-1} = \bigl(g(a)\ g(b)\ g(c)\bigr),$

y observa que $H$ , por ser un grupo, es estable por conjugación por sus propios elementos.
Deduce que $H$ contiene los quince ciclos de longitud $3$ consecutivos del gran recorrido:

$s_t = (x_t\ x_{t+1}\ x_{t+2}) \qquad (t \in \Z/15\Z, \text{ índices módulo } 15).$

Parte IV — Generación del grupo alternado.

(Lema A) Sean $s$ y $t$ dos ciclos de longitud $3$ cuyos soportes comparten exactamente dos puntos, digamos $\{a, b, c\}$ y $\{b, c, d\}$ . Prueba que, tras sustituir $s$ o $t$ por su inverso si hace falta (lo cual no cambia el subgrupo generado), el producto $st$ es una doble transposición; prueba que $A_4$ no contiene ningún subgrupo de orden $6$ (un subgrupo de índice $2$ contiene todos los cuadrados; cuenta los ciclos de longitud $3$ que son cuadrados); y concluye que $\langle s, t\rangle$ es todo el grupo alternado de las cuatro letras $\{a, b, c, d\}$ .
(Lema B) Sea $X$ un conjunto de $k \geq 4$ letras, $w \notin X$ , y sea $G$ un subgrupo de algún $\mathfrak{S}_n$ que contiene todas las permutaciones pares de $X$ y un ciclo de longitud $3$ de la forma $(u\ v\ w)$ con $u, v \in X$ . Prueba que para todos $a, b \in X$ distintos existe una permutación par $g$ de $X$ con $g(u) = a$ , $g(v) = b$ , y deduce que $(a\ b\ w) \in G$ .
Deduce que el grupo $G$ del lema B contiene todas las permutaciones pares de $X \cup \{w\}$ (usa el Ejercicio 1.6: los ciclos de longitud $3$ generan). Después, encadenando los lemas A y B a lo largo de los ciclos consecutivos $s_0, s_1, \dots, s_{12}$ de la pregunta 13, demuestra que $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
Concluye que $H = A_{15}$ : toda reordenación par de las quince fichas es realizable mediante un programa, y $H$ tiene $15!/2 = 653\,837\,184\,000$ elementos.
(El teorema de Johnson–Story, 1879) Ensambla las preguntas 6, 7, 8 y 17: las configuraciones alcanzables desde la resuelta son exactamente las $16!/2 = 10\,461\,394\,944\,000$ configuraciones con $I = +1$ ; y la alcanzabilidad tiene exactamente dos clases, la de la configuración resuelta y la de la $\sigma_L$ de Loyd. (Para el segundo punto, reetiqueta las fichas $14$ y $15$ : prueba que $\sigma \mapsto (14\ 15) \circ \sigma$ transforma sucesiones de movimientos en sucesiones de movimientos e intercambia $\{I = +1\}$ con $\{I = -1\}$ .)

Parte V — Criterios, variantes y la vista desde arriba.

(El criterio práctico) Lee las quince fichas en el orden de lectura de sus casillas, saltándote el hueco, y sea $N$ el número de inversiones de esa lista; sea $r$ la fila del hueco contada desde abajo. Prueba que $I(\sigma) = (-1)^{N + r + 1}$ , de modo que $\sigma$ es resoluble si y solo si $N + r$ es impar.
(Acciones de grupo) Una acción de un grupo $G$ sobre un conjunto $X$ es una aplicación $G \times X \to X$ , $(g, x) \mapsto g \cdot x$ , con $e \cdot x = x$ y $g \cdot (h \cdot x) = (gh) \cdot x$ ; la órbita de $x$ es $G \cdot x$ , y la acción es libre cuando $g \cdot x = x$ obliga a $g = e$ . Prueba que $h \cdot \sigma = \sigma \circ h^{-1}$ define una acción libre de $H$ sobre el conjunto de configuraciones con el hueco en casa, que sus órbitas son exactamente las clases de alcanzabilidad mutua mediante programas, y recupera del recuento de órbitas que esas configuraciones se reparten en exactamente $15!\,/\,\abs H = 2$ clases.
(La obstrucción $3 \times 3$ ) Prueba que el tablero de $3 \times 3$ no admite ningún camino cerrado que visite cada casilla exactamente una vez: la estrategia del gran recorrido de la parte III falla para el juego del ocho. (Colorea las nueve casillas como un tablero de ajedrez.)
(La reparación) En el tablero de $3 \times 3$ con casillas del $1$ al $9$ en orden de lectura y casa $9$ : calcula los efectos del recorrido por el perímetro $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (un ciclo $\zeta'$ de longitud $7$ que deja fijo el centro $5$ ) y del recorrido de esquina $9 \to 6 \to 5 \to 8 \to 9$ (un ciclo de longitud $3$ que pasa por el centro). Conjugando el segundo por las potencias de $\zeta'$ y encadenando los lemas A y B, demuestra que el grupo de programas del juego del ocho es todo $A_8$ , y por tanto que exactamente $9!/2 = 181\,440$ de las $9! = 362\,880$ configuraciones son resolubles.
(Un tablero pobre) Sea ahora el tablero un único ciclo de $n \geq 4$ casillas con $n - 1$ fichas. Prueba que el orden cíclico de las fichas es invariante, que cada clase de alcanzabilidad tiene exactamente $n(n - 1)$ configuraciones (las clases son las órbitas de un grupo cíclico de orden $\operatorname{lcm}(n, n-1) = n(n-1)$ ), y que hay $(n - 2)!$ clases —para $n \geq 5$ , muchas más que $2$ —: en un tablero estrecho el invariante de paridad casi no captura nada y manda la geometría.
Dos veredictos mediante el criterio de la pregunta 19: la bandeja completamente invertida (fichas $15, 14, \dots, 1$ en las casillas $1$ a $15$ , hueco en casa) y la bandeja con el hueco en la casilla $1$ seguido de las fichas $15, 14, \dots, 1$ en las casillas $2$ a $16$ . ¿Cuál de las dos es resoluble?
(Síntesis) La demostración tiene dos pilares independientes: un invariante ( $I$ , construido a partir del morfismo signatura) que muestra que a lo sumo la mitad de las configuraciones son alcanzables, y un teorema de generación explícita ( $H = A_{15}$ ) que muestra que al menos la mitad lo son. Di, en una frase cada uno, dónde intervinieron: la propiedad de morfismo de $\varepsilon$ ; el teorema de Lagrange; la generación de $A_n$ por los ciclos de longitud $3$ ; la conjugación. Enuncia el metaprincipio en una línea.

Solución

Solución de Problema 1.1.

1. Una configuración asigna a cada una de las $16$ casillas uno de los $16$ contenidos (las fichas $1$ – $15$ o el hueco $b = 16$ ), cada uno exactamente una vez: precisamente una biyección $\intint1{16} \to \intint1{16}$ , es decir, un elemento de $\mathfrak{S}_{16}$ ; hay $16! = 20\,922\,789\,888\,000$ . Un movimiento legal desliza una ficha contigua al hueco, así que el número de movimientos es el número de vecinos de la casilla del hueco: $2$ para las cuatro casillas de esquina, $3$ para las ocho casillas de borde y $4$ para las cuatro casillas interiores.

2. Tras el deslizamiento, la casilla $p$ contiene el antiguo contenido de $c$ y la casilla $c$ contiene el hueco; las demás casillas quedan intactas: $\sigma'(p) = \sigma(c)$ , $\sigma'(c) = \sigma(p) = 16$ y $\sigma' = \sigma$ en el resto. Eso es exactamente $\sigma' = \sigma \circ (p\ c)$ . Como $\varepsilon$ es un morfismo y $\varepsilon\bigl((p\ c)\bigr) = -1$ , resulta $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. Dos casillas contiguas difieren en un paso en exactamente una de las dos coordenadas, luego $i + j$ cambia de paridad: $\chi$ toma valores opuestos en casillas contiguas. Un movimiento traslada el hueco de $p$ a la casilla contigua $c$ y cambia el signo de $\chi(\text{casilla del hueco})$ . A lo largo de un recorrido cerrado del hueco, $\chi$ cambia de signo una vez por movimiento y vuelve a su valor inicial: el número de movimientos es par.

4. Por las preguntas 2 y 3, un movimiento cambia el signo de los dos factores de $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ ; su producto no varía. Para la configuración resuelta: $\varepsilon(\mathrm{id}) = +1$ y el hueco está en la casilla $16$ , fila $4$ , columna $4$ , luego $\chi(16) = (-1)^{8} = +1$ y $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ es la transposición $(14\ 15)$ de casillas: $\varepsilon(\sigma_L) = -1$ ; su hueco está en casa, $\chi(16) = +1$ , luego $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . Como $I$ se conserva en todo movimiento, ninguna sucesión de movimientos une $\sigma_L$ con $\mathrm{id}$ . El premio estaba estructuralmente a salvo.

6. Fijemos una casilla $p$ y otras dos casillas $c \neq d$ , ambas distintas de $p$ , y pongamos $\tau_0 = (c\ d)$ . Sobre el conjunto de configuraciones con el hueco en $p$ , la aplicación $\sigma \mapsto \sigma \circ \tau_0$ es una involución (conserva $\sigma(p) = 16$ , pues $\tau_0$ deja fijo $p$ ) y cambia el signo de $\varepsilon$ , luego el de $I$ : empareja biyectivamente las configuraciones con $I = +1$ con las de $I = -1$ . Así, cada una de las $16$ posiciones del hueco aporta $15!/2$ configuraciones con $I = +1$ , y

\abs{\{I = +1\}} = 16 \cdot \frac{15!}{2} = \frac{16!}{2}.

7. El movimiento que desliza la ficha de $c$ hasta $p$ se deshace deslizando esa misma ficha (ahora en $p$ ) de vuelta a $c$ : componer dos veces con $(p\ c)$ da la identidad. De ahí: reflexividad (sucesión vacía), simetría (recórrase la sucesión al revés, deshaciendo cada movimiento) y transitividad (concaténense): es una relación de equivalencia. Todo $\sigma \in R$ cumple $I(\sigma) = I(\mathrm{id}) = +1$ por la pregunta 4, luego $R \subseteq \{I = +1\}$ ; y $\sigma_L \notin R$ proporciona una segunda clase.

8. Si $\sigma(16) = 16$ , entonces $\sigma$ permuta las casillas $1, \dots, 15$ ; llamemos $\rho$ a esa restricción. Añadir un punto fijo no cambia ni el tipo de ciclos ni la signatura (descompóngase $\rho$ en transposiciones; el mismo producto sirve en $\mathfrak{S}_{16}$ ), luego $\varepsilon(\sigma) = \varepsilon(\rho)$ , y $\chi(16) = +1$ da $I(\sigma) = \varepsilon(\rho)$ . Toda configuración puede llevarse a otra con el hueco en casa: la cuadrícula es conexa, así que se pasea el hueco por un camino de casillas contiguas hasta la casilla $16$ (cada paso es un movimiento legal). Supongamos ahora que todo $\rho \in \mathfrak{S}_{15}$ par se realiza mediante un programa. Dada $\sigma$ con $I(\sigma) = +1$ : llévese el hueco a casa para obtener $\widetilde\sigma$ (equivalente a $\sigma$ ), con $I(\widetilde\sigma) = +1$ , es decir, con restricción $\rho$ par; el programa que realiza $\rho$ lleva $\widetilde\sigma$ a $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (véase la pregunta 9). Por transitividad $\sigma \in R$ , de donde $\{I = +1\} \subseteq R$ y la igualdad.

9. Un solo movimiento: el contenido de $c$ acaba en $p$ y el hueco en $c$ : el efecto es $\pi = (p\ c)$ , y en efecto $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . Inducción: si una sucesión tiene efecto $\pi_1$ y lleva $\sigma$ a $\sigma \circ \pi_1^{-1}$ , prolongarla con un movimiento de efecto $\pi_2 = (p'\ c')$ da $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ , y los contenidos se mueven según $\pi_2 \circ \pi_1$ (primero $\pi_1$ , después $\pi_2$ ). Así pues, los efectos se componen, y un programa ejecutado desde $\sigma$ termina en $\sigma \circ \pi^{-1}$ . Subgrupo: el programa vacío tiene efecto $\mathrm{id}$ ; la concatenación da los productos; invertir un programa (pregunta 7) da los inversos. El efecto de un programa deja fija la casilla $16$ (el hueco empieza y acaba en casa), luego $H \leq \mathfrak{S}_{15}$ . Paridad: un programa de $k$ movimientos tiene $k$ par (pregunta 3), y $\varepsilon(\sigma \circ \pi^{-1}) = (-1)^k\varepsilon(\sigma)$ obliga a $\varepsilon(\pi) = +1$ : $H \subseteq A_{15}$ .

10. Sigamos los cuatro deslizamientos desde el hueco en $16$ : el movimiento $16 \to 12$ lleva el contenido de $12$ a $16$ ; el movimiento $12 \to 11$ lleva el contenido de $11$ a $12$ ; el movimiento $11 \to 15$ lleva el contenido de $15$ a $11$ ; el movimiento $15 \to 16$ lleva el contenido aparcado en $16$ (originalmente en $12$ ) a $15$ . En total: $11 \mapsto 12$ , $12 \mapsto 15$ , $15 \mapsto 11$ , hueco en casa; el efecto es $(11\ 12\ 15)$ . El recorrido inverso lo deshace: efecto $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . Ambos son efectos de programas y por tanto pertenecen a $H$ .

11. Contigüidad de casillas consecutivas: en cada par listado las casillas difieren en $1$ dentro de la misma fila ( $16{-}15$ , $15{-}14$ , $14{-}13$ ; $1{-}2$ , $2{-}3$ , $3{-}4$ ; $8{-}7$ , $7{-}6$ ; $10{-}11$ , $11{-}12$ ) o en $4$ dentro de una columna ( $13{-}9$ , $9{-}5$ , $5{-}1$ ; $4{-}8$ ; $6{-}10$ ; $12{-}16$ ): un recorrido cerrado por las $16$ casillas, de longitud $16$ . Efecto: como en la pregunta 10, escribiendo las casillas visitadas $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ , el contenido de $c_i$ pasa a $c_{i-1}$ para $i = 2, \dots, 15$ , y el contenido de $c_1$ , aparcado en $16$ tras el primer movimiento, es llevado a $c_{15}$ por el último. Así, el efecto envía $15 \mapsto 12$ , y $14 \mapsto 15$ , $13 \mapsto 14$ , $9 \mapsto 13$ , $5 \mapsto 9$ , $1 \mapsto 5$ , $2 \mapsto 1$ , $3 \mapsto 2$ , $4 \mapsto 3$ , $8 \mapsto 4$ , $7 \mapsto 8$ , $6 \mapsto 7$ , $10 \mapsto 6$ , $11 \mapsto 10$ , $12 \mapsto 11$ : exactamente el ciclo $\zeta$ de longitud $15$ . Su orden cíclico empieza por $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , y $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ envía $15 \mapsto 12 \mapsto 11 \mapsto 15$ , que es precisamente $(11\ 15\ 12)$ , el recorrido elemental inverso.

12. Sea $\gamma = (a\ b\ c)$ y $x \in \intint1n$ . Si $x = g(a)$ : $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ; análogamente $g(b) \mapsto g(c)$ y $g(c) \mapsto g(a)$ . Si $x \notin \{g(a), g(b), g(c)\}$ , entonces $g^{-1}(x) \notin \{a,b,c\}$ queda fijo por $\gamma$ , luego $x$ queda fijo. Por tanto $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . Y para $g, h \in H$ se tiene $ghg^{-1} \in H$ por los axiomas de subgrupo.

13. $\zeta \in H$ (pregunta 11) y $s_0 = (x_0\ x_1\ x_2) \in H$ (preguntas 10–11). Como $\zeta(x_i) = x_{i+1}$ (índices módulo $15$ ), la pregunta 12 da

\zeta^{t}\,s_0\,\zeta^{-t} = \bigl(\zeta^t(x_0)\ \zeta^t(x_1)\ \zeta^t(x_2)\bigr) = (x_t\ x_{t+1}\ x_{t+2}) = s_t \in H \qquad (t = 0, 1, \dots, 14).

14. Salvo inversión, supongamos $s = (a\ b\ c)$ y $t = (b\ c\ d)$ (un ciclo de longitud $3$ sobre $\{a,b,c\}$ es $(a\ b\ c)$ o su inverso; lo mismo sobre $\{b,c,d\}$ , y sustituir un generador por su inverso deja $\langle s, t\rangle$ intacto). Entonces, aplicando primero $t$ ,

st \colon a \mapsto b,\quad b \mapsto a,\quad c \mapsto d,\quad d \mapsto c, \qquad\text{es decir,}\quad st = (a\ b)(c\ d),

una doble transposición. El subgrupo $G = \langle s, t\rangle$ está formado por permutaciones pares de las cuatro letras, luego $G \leq A_4$ y $\abs G \mid 12$ ; contiene un elemento de orden $3$ y otro de orden $2$ , así que $6 \mid \abs G$ (Lagrange, Teorema 1.14, aplicado a los dos subgrupos cíclicos). Si $A_4$ tuviera un subgrupo $K$ de orden $6$ , tendría índice $2$ , y entonces $g^2 \in K$ para todo $g \in A_4$ : para $g \in K$ es evidente; para $g \notin K$ las únicas clases son $K$ y $gK$ , luego la clase $g^2K$ es $K$ o $gK$ , y $g^2K = gK$ obligaría a $g \in K$ . Así pues, todo cuadrado está en $K$ . Pero todo ciclo $\gamma$ de longitud $3$ es un cuadrado, $\gamma = (\gamma^2)^2$ , y $A_4$ contiene ocho de ellos: $8 > 6$ , contradicción. Luego $\abs G = 12$ : $G = A_4$ .

15. Extendamos $u \mapsto a$ , $v \mapsto b$ a una biyección $g_0$ de $X$ (envíense las $k - 2$ letras restantes biyectivamente sobre el complementario de $\{a, b\}$ ). Si $g_0$ es impar, tomemos dos letras distintas $s_1, t_1 \in X \setminus \{u, v\}$ (posible, pues $k \geq 4$ ) y sustituyamos $g_0$ por $g_0 \circ (s_1\ t_1)$ , que es par y sigue enviando $u \mapsto a$ , $v \mapsto b$ . Extendamos por la identidad fuera de $X$ : se obtiene una permutación par $g \in G$ (es una permutación par de $X$ ). Entonces la pregunta 12 da

g\,(u\ v\ w)\,g^{-1} = (g(u)\ g(v)\ g(w)) = (a\ b\ w) \in G,

usando $g(w) = w$ .

16. Todo ciclo de longitud $3$ de $X \cup \{w\}$ está en $G$ : los soportados en $X$ son permutaciones pares de $X$ ; uno de soporte $\{a, b, w\}$ es $(a\ b\ w)$ o $(b\ a\ w)$ , y la pregunta 15 proporciona ambos. Por el Ejercicio 1.6, los ciclos de longitud $3$ del conjunto de $k+1$ elementos $X \cup \{w\}$ generan su grupo alternado, luego $G$ contiene todas las permutaciones pares de $X \cup \{w\}$ . Encadenamiento: sea $G = \langle s_0, \dots, s_{12}\rangle$ . El lema A aplicado a $s_0 = (x_0\ x_1\ x_2)$ y $s_1 = (x_1\ x_2\ x_3)$ (los soportes comparten $\{x_1, x_2\}$ ) da todas las permutaciones pares de $X_4 = \{x_0, x_1, x_2, x_3\}$ . Si $G$ contiene todas las permutaciones pares de $X_m = \{x_0, \dots, x_{m-1}\}$ ( $4 \leq m \leq 14$ ), entonces $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ tiene $u = x_{m-2}, v = x_{m-1} \in X_m$ y letra nueva $w = x_m$ : el lema B y la primera parte dan todas las permutaciones pares de $X_{m+1}$ . Por inducción hasta $m = 14$ : $G \supseteq A_{15}$ (permutaciones pares de las quince casillas), y $G \subseteq A_{15}$ porque cada $s_t$ es par; luego $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .

17. Preguntas 13 y 16: $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ; pregunta 9: $H \subseteq A_{15}$ . Por tanto $H = A_{15}$ , de orden $15!/2 = 653\,837\,184\,000$ : toda reordenación par de las quince fichas es el efecto de un programa.

18. La pregunta 8 redujo $R = \{I = +1\}$ a realizar todo $\rho \in \mathfrak{S}_{15}$ par mediante un programa, cosa hecha en la pregunta 17. Con la pregunta 6, $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . Dos clases: hagamos actuar $t_0 = (14\ 15)$ sobre los contenidos: $\varphi(\sigma) = t_0 \circ \sigma$ . Un movimiento legal desde $\sigma$ es un movimiento legal desde $\varphi(\sigma)$ (la casilla del hueco no cambia: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ , y la casilla movida es la misma), y $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : $\varphi$ transforma sucesiones de movimientos en sucesiones de movimientos, de forma biyectiva (es una involución). Y cambia el signo de $I$ : $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ , con la misma casilla de hueco. Por tanto $\varphi$ aplica biyectivamente la clase $R = \{I = +1\}$ de $\mathrm{id}$ sobre la clase de $\varphi(\mathrm{id}) = \sigma_L$ , que es en consecuencia todo $\{I = -1\}$ : exactamente dos clases. Este es el teorema de Johnson–Story.

19. Indexemos las casillas en orden de lectura y sea $k = 4(i - 1) + j$ la casilla del hueco. Contemos las inversiones de $\sigma$ (pares de casillas $x < y$ con $\sigma(x) > \sigma(y)$ ): los pares de dos casillas con ficha aportan $N$ ; en los pares en que interviene el hueco, todas las casillas posteriores al hueco contienen fichas $< 16$ y están invertidas ( $16 - k$ pares), mientras que las anteriores nunca lo están. Luego $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . Como $k = 4(i-1) + j \equiv j \pmod 2$ ,

I(\sigma) = (-1)^{N + j}\,(-1)^{i + j} = (-1)^{N + i} = (-1)^{N + r + 1}

usando $i = 5 - r$ . Por la pregunta 18, $\sigma$ es resoluble si y solo si $I(\sigma) = +1$ , si y solo si $N + r$ es impar. Comprobación: en la resuelta, $N = 0$ , $r = 1$ : impar, resoluble; en la de Loyd, $N = 1$ , $r = 1$ : par, no resoluble.

20. Acción: $e \cdot \sigma = \sigma \circ \mathrm{id} = \sigma$ y $g \cdot (h \cdot \sigma) = \sigma \circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot \sigma$ ; además, $\sigma \circ h^{-1}$ vuelve a ser una configuración con el hueco en casa ( $h$ deja fija la casilla $16$ ). Libre: $\sigma \circ h^{-1} = \sigma$ da $h^{-1} = \mathrm{id}$ (compóngase con $\sigma^{-1}$ ). Órbitas $=$ clases de programas: la pregunta 9 dice que las configuraciones alcanzables desde $\sigma$ mediante programas son exactamente las $\sigma \circ \pi^{-1}$ , $\pi \in H$ : la órbita $H \cdot \sigma$ . Recuento: al ser libre, $h \mapsto h \cdot \sigma$ es inyectiva, de modo que toda órbita tiene $\abs H = 15!/2$ elementos; las $15!$ configuraciones con el hueco en casa se reparten pues en $15!\,/\,(15!/2) = 2$ órbitas, el reflejo con el hueco en casa de las dos clases de Johnson–Story.

21. La cuadrícula $3 \times 3$ es bipartita para la coloración de tablero de ajedrez: cada paso de un recorrido cambia de color, así que todo recorrido cerrado tiene longitud par. Un recorrido cerrado que visitara cada una de las $9$ casillas exactamente una vez tendría longitud $9$ , impar: imposible. La construcción del gran recorrido de la parte III no está, por tanto, disponible en el juego del ocho.

22. Recorrido por el perímetro $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (todos los pasos entre casillas contiguas; longitud $8$ , par): con la contabilidad de la pregunta 11 y $c_1 = 8, c_2 = 7, c_3 = 4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$ , el efecto es

\zeta' = (8\ 6\ 3\ 2\ 1\ 4\ 7),

un ciclo de longitud $7$ que deja fijo el centro $5$ (el contenido de $7$ pasa a $8$ , el de $4$ a $7$ , el de $1$ a $4$ , el de $2$ a $1$ , el de $3$ a $2$ , el de $6$ a $3$ y el de $8$ a $6$ ). Recorrido de esquina $9 \to 6 \to 5 \to 8 \to 9$ : efecto $(6\ 8\ 5)$ (el contenido de $5$ pasa a $6$ , el de $8$ a $5$ y el de $6$ —aparcado en $9$ — a $8$ ). Pongamos $y_t = \zeta'^{\,t}(8)$ : $y_0 = 8, y_1 = 6, y_2 = 3, y_3 = 2, y_4 = 1, y_5 = 4, y_6 = 7$ . Por conjugación (pregunta 12),

\zeta'^{\,t}\,(6\ 8\ 5)\,\zeta'^{-t} = (y_{t+1}\ y_t\ 5) =: T_t \in H_{3\times3},

ya que $\zeta'$ deja fijo $5$ . Los soportes de $T_0 = (y_1\ y_0\ 5)$ y $T_1 = (y_2\ y_1\ 5)$ comparten exactamente $\{y_1, 5\}$ : el lema A da todas las permutaciones pares de $\{y_0, y_1, y_2, 5\}$ . Después $T_2 = (y_3\ y_2\ 5)$ incorpora $y_3$ por el lema B (sus letras $y_2, 5$ están en el conjunto actual, $k = 4$ ), y $T_3, T_4, T_5$ incorporan sucesivamente $y_4, y_5, y_6$ : todas las permutaciones pares de las ocho casillas distintas de la casa están en el grupo de programas, que además está formado por permutaciones pares (el argumento de la pregunta 9 no depende del tablero). Luego $H_{3\times3} = A_8$ , y el razonamiento de las preguntas 6, 8 y 18 —también independiente del tablero— muestra que las configuraciones alcanzables son exactamente las de $I = +1$ : la mitad de $9!$ , es decir, $181\,440$ .

23. Etiquetemos las casillas $0, \dots, n-1$ a lo largo del ciclo. Un movimiento intercambia el hueco con uno de sus dos vecinos. Leamos las fichas en orden cíclico a partir de la casilla siguiente al hueco: se obtiene una palabra $w$ que lista las $n - 1$ fichas. Mover el hueco un paso hacia delante sustituye $(p, w)$ por $(p + 1, \rho w)$ , donde $p$ es la casilla del hueco y $\rho$ rota cíclicamente la palabra un lugar; el movimiento hacia atrás es el inverso. El orden cíclico de las fichas (la palabra salvo rotación) es, por tanto, invariante. La clase alcanzable de $(p, w)$ es la órbita de la aplicación $g \colon (p, w) \mapsto (p+1, \rho w)$ , elemento de orden $\operatorname{lcm}(n, n-1) = n(n-1)$ en el producto de los dos grupos cíclicos (traslaciones de $\Z/n\Z$ y rotaciones de las $n-1$ posiciones de la palabra), siendo el mcm igual a $n(n-1)$ porque $\gcd(n, n-1) = 1$ : cada clase tiene exactamente $n(n-1)$ configuraciones, todas con el mismo collar. Clases: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$ . Para $n \geq 5$ , $(n-2)! > 2$ : el invariante de paridad (dos clases a lo sumo) es ciego a casi toda la obstrucción; la riqueza del tablero de $4 \times 4$ —donde la paridad es la única obstrucción— es un hecho genuinamente geométrico, no formal.

24. Ambas bandejas tienen las fichas en orden completamente invertido, luego $N = \binom{15}{2} = 105$ en los dos casos (todo par de fichas está invertido). Hueco en casa: $r = 1$ , $N + r = 106$ par: no resoluble. Hueco en la casilla $1$ : el hueco está en la fila superior, $r = 4$ , $N + r = 109$ impar: resoluble. Dos bandejas que solo difieren en dónde está el hueco caen a lados opuestos del muro.

25. Propiedad de morfismo: convierte “un movimiento $=$ una transposición” en “un movimiento $=$ un cambio de signo” (preguntas 2 y 4), lo que hace $I$ calculable movimiento a movimiento. Lagrange: obligó a $6 \mid \abs{\langle s, t\rangle}$ en el lema A y midió las clases laterales en la exclusión del orden $6$ (pregunta 14). Generación por ciclos de longitud $3$ : convirtió “ $H$ contiene suficientes ciclos de longitud $3$ ” en “ $H$ contiene todo $A_{15}$ ” (pregunta 16). Conjugación: fabricó los quince ciclos consecutivos de longitud $3$ a partir de un único recorrido $2 \times 2$ transportado por el gran recorrido (preguntas 12–13), y los ciclos $(a\ b\ w)$ del lema B. Metaprincipio: un invariante demuestra la imposibilidad, una construcción explícita demuestra la posibilidad, y un problema queda completamente resuelto exactamente cuando las dos cotas se encuentran; aquí, en la mitad.

Términos definidos en este capítulo

Ver los 395 términos del glosario