---
title: "Conjuntos y estructuras"
book: "Matemáticas universitarias — Grado 2"
subject: math
language: es
chapter: 1
exercises: 12
source: https://one-course.com/books/math/4/es/chapter/1-conjuntos-y-estructuras
---

# Capítulo 1 — Conjuntos 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](#def-b2-structures-countable), Cantor–Bernstein) y la teoría estructural de grupos y anillos —el teorema de Lagrange, el grupo simétrico con su signatura, los [ideales](#def-b2-structures-ideal) 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](https://one-course.com/books/math/4/es/chapter/2-algebra-lineal#ch-b2-linalg)), los [anillos cociente](#def-b2-structures-quotientring) gobiernan la aritmética y la [numerabilidad](#def-b2-structures-countable) 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](#def-b2-structures-generated) 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](#prop-b2-structures-images) 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).**

1. Todo subconjunto infinito de $\N$ es [numerable](#def-b2-structures-countable) ; un conjunto es a lo sumo [numerable](#def-b2-structures-countable) si y solo si se inyecta en $\N$ , si y solo si es vacío o imagen sobreyectiva de $\N$ .
2. $\N \times \N$ es [numerable](#def-b2-structures-countable) ; un producto de dos conjuntos a lo sumo [numerables](#def-b2-structures-countable) es a lo sumo [numerable](#def-b2-structures-countable) .
3. Una unión a lo sumo [numerable](#def-b2-structures-countable) de conjuntos a lo sumo [numerables](#def-b2-structures-countable) es a lo sumo [numerable](#def-b2-structures-countable) .
4. $\Z$ y $\Q$ son [numerables](#def-b2-structures-countable) .

**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](#def-b2-structures-countable) a $\varphi(E) \subseteq \N$: finito o [numerable](#def-b2-structures-countable). 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](#def-b2-structures-countable) $\N^2$ sobre $\bigcup E_n$.

(4) $\Z = \N \cup (-\N^*)$: unión [numerable](#def-b2-structures-countable). $\Q$ es imagen sobreyectiva de $\Z \times \N^*$ (la aplicación fracción), luego es a lo sumo [numerable](#def-b2-structures-countable), 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](#def-b2-structures-countable) 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](#def-b2-structures-countable): los polinomios de grado $\leq d$ sobre $\Q$ se inyectan en $\Q^{d+1}$, producto finito de [conjuntos numerables](#def-b2-structures-countable) ([Proposición 1.6](#prop-b2-structures-countablestable) (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](#def-b2-structures-countable) de conjuntos finitos ([Proposición 1.6](#prop-b2-structures-countablestable) (3)), infinita porque contiene a $\Q$. Junto con la no [numerabilidad](#def-b2-structures-countable) de $\R$ ([Teorema 1.9](#thm-b2-structures-cantor) más abajo), esto demuestra —sin exhibir ni uno solo— que los números trascendentes existen y forman una mayoría no [numerable](#def-b2-structures-countable): el argumento de conteo de Cantor de 1874, existencia por pura cardinalidad.

**Teorema 1.9 (Cantor; no numerabilidad de R\RR).**

1. Para todo conjunto $E$ no existe ninguna sobreyección $E \to  \mathcal{P}(E)$ .
2. $\R$ *no* es [numerable](#def-b2-structures-countable) .

**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](#def-b2-structures-countable).

**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](#def-b2-structures-countable): 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](#exo-b2-structures-3)) son todos [equipotentes](#def-b2-structures-countable): “el cardinal del continuo”.

**Ejemplo 1.12 (El segmento y el cuadrado).**

$\intcc{0}{1}$ y $\intcc{0}{1}^2$ son [equipotentes](#def-b2-structures-countable): 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](#thm-b2-structures-cantorbernstein)) 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](https://one-course.com/books/math/4/es/chapter/4-topologia-de-los-espacios-metricos#ch-b2-metric)).

## 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](#def-b2-structures-generated) 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](#def-b2-structures-generated) 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: A3A_3A3​ dentro de S3\mathfrak{S}_3S3​).**

Tomemos $G = \mathfrak{S}_3$ (de [orden](#def-b2-structures-generated) $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](#def-b2-structures-generated) primo son [cíclicos](#def-b2-structures-generated):* 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](#prop-b2-structures-cyclic) de más abajo hay exactamente un subgrupo por cada divisor de $12$ —de órdenes $1, 2,
3, 4, 6, 12$, [generados](#def-b2-structures-generated) 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](#def-b2-structures-generated) $12$ pero ningún subgrupo de [orden](#def-b2-structures-generated) $6$, como demostramos en el problema de fin de semana de este capítulo ([Problema 1.1](#pb-b2-structures-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.](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-59863a61e897.svg)

*El retículo de subgrupos de $\Z/12\Z$: un subgrupo por cada divisor de $12$ ([Proposición 1.17](#prop-b2-structures-cyclic)), 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](#def-b2-structures-generated) de [orden](#def-b2-structures-generated) $n$.

1. $G$ es isomorfo a $(\Z/n\Z, +)$ , mediante $\overline k \mapsto  a^k$ .
2. Todo subgrupo de $G$ es [cíclico](#def-b2-structures-generated) ; para cada divisor $d \mid n$ hay exactamente un subgrupo de [orden](#def-b2-structures-generated) $d$ , a saber $\langle  a^{n/d}\rangle$ .
3. $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](#def-b2-structures-generated)); la propiedad universal ([Definición 1.3](#def-b2-structures-quotient)) 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](#def-b2-structures-generated) $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](#def-b2-structures-generated) de la [Definición 1.13](#def-b2-structures-generated) 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](#def-b2-structures-generated) $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](#def-b2-structures-sn) disjuntos dos a dos, de manera única salvo el orden de los factores. Los [ciclos](#def-b2-structures-sn) 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](#def-b2-structures-sn): la primera repetición ha de volver a $x$ por inyectividad) lleva asociado el [ciclo](#def-b2-structures-sn) $(x\ \sigma(x)\ \cdots\
\sigma^{k-1}(x))$, y $\sigma$ es el producto de esos [ciclos](#def-b2-structures-sn): sobre cada órbita solo actúa el [ciclo](#def-b2-structures-sn) correspondiente. Unicidad: toda factorización en [ciclos](#def-b2-structures-sn) disjuntos reproduce exactamente las órbitas (el [ciclo](#def-b2-structures-sn) que pasa por $x$ ha de ser $(x\
\sigma(x)\ \cdots)$). Los [ciclos](#def-b2-structures-sn) disjuntos conmutan porque mueven puntos disjuntos; el enunciado sobre el [orden](#def-b2-structures-generated) se sigue de que $\sigma^m = \mathrm{id}$ si y solo si lo es la potencia $m$-ésima de cada [ciclo](#def-b2-structures-sn) (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](#def-b2-structures-sn) $(4, 3, 2)$ —un [ciclo](#def-b2-structures-sn) de longitud $4$, uno de longitud $3$ y una transposición—? Se eligen los soportes y los órdenes [cíclicos](#def-b2-structures-generated):

$$
\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](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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](#def-b2-structures-generated) $\operatorname{lcm}(4,3,2) =
12$ y signatura $(-1)^3(-1)^2(-1)^1 = +1$ ([Teorema 1.19](#thm-b2-structures-cycles) 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](#def-b2-structures-sn): 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](#def-b2-structures-sn) de longitud $k$ tiene signatura $(-1)^{k-1}$, y el *grupo alternado* $A_n = \ker\varepsilon$ tiene [orden](#def-b2-structures-generated) $\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](#def-b2-structures-sn) $\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](#def-b2-structures-sn) generan $\mathfrak{S}_n$: todo [ciclo](#def-b2-structures-sn) 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](#thm-b2-structures-cycles) remata. Un morfismo hacia $\{\pm1\}$ queda determinado por sus valores sobre los generadores.

*Consecuencias.* La identidad anterior escribe un [ciclo](#def-b2-structures-sn) de longitud $k$ como producto de $k - 1$ [transposiciones](#def-b2-structures-sn): signatura $(-1)^{k-1}$. En cuanto a $A_n$: el morfismo $\varepsilon$ es sobreyectivo (hay [transposiciones](#def-b2-structures-sn) para $n \geq 2$), y las dos “clases laterales” $A_n$ y $(1\,2)A_n$ son [equipotentes](#def-b2-structures-countable) 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](#def-b2-structures-generated) $\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](https://one-course.com/books/math/4/es/chapter/2-algebra-lineal#ch-b2-linalg).

**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](#def-b2-structures-sn):* $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](#def-b2-structures-sn):* $\sigma = (1\,4)(1\,3)(2\,5)$, tres factores, $(-1)^3 = -1$. Tres cálculos, una misma paridad: la unicidad del [Teorema 1.21](#thm-b2-structures-signature) 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](https://one-course.com/books/math/4/es/chapter/2-algebra-lineal#ch-b2-linalg); 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](#def-b2-structures-generated)* por $x$ es $xA = \{xa\}$ (un ideal *principal*).

**Teorema 1.26 (Ideales de Z\ZZ y de K[X]K[X]K[X]).**

Todo [ideal](#def-b2-structures-ideal) de $\Z$ es de la forma $n\Z$ para un único $n \in \N$; todo [ideal](#def-b2-structures-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](#def-b2-structures-ideal) es en particular un subgrupo, y $n\Z$ es un [ideal](#def-b2-structures-ideal)). Para $K[X]$: sea $I \neq \{0\}$ un [ideal](#def-b2-structures-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](#def-b2-structures-ideal) $x\Z + y\Z$ (o de su análogo polinómico) con el [ideal](#def-b2-structures-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](#def-b2-structures-ideal):* el [ideal](#def-b2-structures-ideal) $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ es principal ([Teorema 1.26](#thm-b2-structures-principal)); 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](#def-b2-structures-ideal) identifica el mcd *sin dividir* —las raíces comunes localizan el [ideal](#def-b2-structures-ideal) y Euclides se limita a certificarlo—.

**Definición 1.28 (El anillo cociente Z/nZ\Z/n\ZZ/nZ, revisitado).**

Para un [ideal](#def-b2-structures-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](#def-b2-structures-quotient) $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](#ex-b2-structures-crtinverse)—. 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](#exo-b2-structures-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](#def-b2-structures-generated) $\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](#thm-b2-structures-lagrange)), todo elemento elevado al [orden](#def-b2-structures-generated) 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](#def-b2-structures-generated)? 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](#def-b2-structures-generated) 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](#exo-b2-structures-10): $(\Z/p\Z)^*$ *sí* es [cíclico](#def-b2-structures-generated) 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](https://one-course.com/books/math/4/es/chapter/3-reduccion-de-endomorfismos#ch-b2-reduction).

**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](#def-b2-structures-ideal) principal, exactamente como predice el [Teorema 1.26](#thm-b2-structures-principal), [generado](#def-b2-structures-generated) por el polinomio mónico $X^2$ de menor grado del núcleo —el *polinomio mínimo* de $A$, protagonista del [Capítulo 3](https://one-course.com/books/math/4/es/chapter/3-reduccion-de-endomorfismos#ch-b2-reduction)—. La imagen es el [álgebra](#def-b2-structures-algebra) conmutativa de dimensión dos $\{aI + bA\}$: los morfismos de evaluación comprimen el $\R[X]$ de dimensión infinita sobre [álgebras](#def-b2-structures-algebra) 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](#def-b2-structures-quotient)): construye aquí $\Z/n\Z$, define aplicaciones sobre los conjuntos de soluciones de sistemas lineales en el [Capítulo 2](https://one-course.com/books/math/4/es/chapter/2-algebra-lineal#ch-b2-linalg) 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](https://one-course.com/books/math/4/es/chapter/2-algebra-lineal#ch-b2-linalg)), la invariancia de la traza por semejanza y las cantidades conservadas del [Capítulo 16](https://one-course.com/books/math/4/es/chapter/16-ecuaciones-diferenciales#ch-b2-diffeq). *El recuento contra una estructura*: Lagrange cuenta mediante clases laterales, la dimensión cuenta mediante bases ([Capítulo 2](https://one-course.com/books/math/4/es/chapter/2-algebra-lineal#ch-b2-linalg)), la multiplicidad cuenta mediante grados de polinomios ([Capítulo 3](https://one-course.com/books/math/4/es/chapter/3-reduccion-de-endomorfismos#ch-b2-reduction)); 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](#def-b2-structures-quotient), 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](#exo-b2-structures-4) da el enunciado correcto para órdenes primos entre sí, y los [ciclos](#def-b2-structures-sn) disjuntos la versión correcta para permutaciones. (iii) La [numerabilidad](#def-b2-structures-countable) se conserva por *uniones* [numerables](#def-b2-structures-countable) y por *productos* finitos, pero no por productos [numerables](#def-b2-structures-countable): $\{0,1\}^{\N}$ no es [numerable](#def-b2-structures-countable) ([Ejercicio 1.3](#exo-b2-structures-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](#ex-b2-structures-cbexample)).

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

Casi en todas partes. La signatura construye los determinantes ([Capítulo 2](https://one-course.com/books/math/4/es/chapter/2-algebra-lineal#ch-b2-linalg)); el morfismo de evaluación $P \mapsto P(u)$ y los [ideales](#def-b2-structures-ideal) principales de $K[X]$ producen los polinomios mínimos y las descomposiciones en núcleos del [Capítulo 3](https://one-course.com/books/math/4/es/chapter/3-reduccion-de-endomorfismos#ch-b2-reduction); la [numerabilidad](#def-b2-structures-countable) es el escenario sobre el que actúa el [Capítulo 21](https://one-course.com/books/math/4/es/chapter/21-probabilidad-sobre-espacios-numerables#ch-b2-proba) (probabilidad sobre espacios [numerables](#def-b2-structures-countable)) y la razón de que la topología no deje de producir conjuntos densos [numerables](#def-b2-structures-countable) ([Capítulo 4](https://one-course.com/books/math/4/es/chapter/4-topologia-de-los-espacios-metricos#ch-b2-metric)). 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](#def-b2-structures-countable)? 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 de Ejercicio 1.1.**

*Subconjuntos finitos de $\N$:* [numerable](#def-b2-structures-countable) —el conjunto de los subconjuntos de $\intint{0}{n}$ es finito, y los subconjuntos finitos forman la unión [numerable](#def-b2-structures-countable) sobre $n$ de estos ([Proposición 1.6](#prop-b2-structures-countablestable) (3))—; infinito, porque contiene todos los conjuntos unitarios.

*Todos los subconjuntos de $\N$:* no [numerable](#def-b2-structures-countable), por el teorema de Cantor ([Teorema 1.9](#thm-b2-structures-cantor) (1) con $E = \N$).

*$\R \setminus \Q$:* no [numerable](#def-b2-structures-countable) —en otro caso $\R = \Q \cup
(\R\setminus\Q)$ sería unión de dos [conjuntos numerables](#def-b2-structures-countable), en contradicción con el [Teorema 1.9](#thm-b2-structures-cantor) (2)—.

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

*Sucesiones binarias nulas a partir de un índice:* [numerable](#def-b2-structures-countable) —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](#def-b2-structures-sn) disjuntos, los órdenes y las signaturas de las cuatro permutaciones, y $\sigma^{2026}$.

**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](#def-b2-structures-sn) 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](#def-b2-structures-sn) de longitud $7$ (como cabía esperar: $\sigma\tau$ y $\tau\sigma$ son conjugadas y por tanto comparten su tipo de [ciclos](#def-b2-structures-sn)).

Órdenes y signaturas: $\sigma$ tiene tipo de [ciclos](#def-b2-structures-sn) $(4,2)$: [orden](#def-b2-structures-generated) $\operatorname{lcm}(4,2) = 4$, signatura $(-1)^3(-1)^1 = +1$; $\tau$ es un [ciclo](#def-b2-structures-sn) de longitud $3$: [orden](#def-b2-structures-generated) $3$, signatura $+1$; ambos productos son [ciclos](#def-b2-structures-sn) de longitud $7$: [orden](#def-b2-structures-generated) $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](#def-b2-structures-sn) de longitud $4$; la [transposición](#def-b2-structures-sn) 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](#def-b2-structures-countable) dos a dos *(desarrollos binarios en ambos sentidos; Cantor–Bernstein absorbe la molestia de la doble representació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](#thm-b2-structures-cantorbernstein)) aplicado a las dos últimas inyecciones, $\intcc{0}{1}$ y $\{0,1\}^{\N}$ son [equipotentes](#def-b2-structures-countable), 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 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](#def-b2-structures-generated) divide a la vez a $m$ y a $n$ (Lagrange en cada [grupo cíclico](#def-b2-structures-generated)) 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](#def-b2-structures-generated) $2$) y $b =
(1\,2\,3)$ (de [orden](#def-b2-structures-generated) $3$), de órdenes primos entre sí, que no conmutan: $ab = (2\,3)$ tiene [orden](#def-b2-structures-generated) $2 \neq 6$ —de hecho, $\mathfrak{S}_3$ no tiene ningún elemento de [orden](#def-b2-structures-generated) $6$—. La conmutación es esencial.

**Ejercicio 1.5 ★★.**

Sea $G$ un grupo finito de [orden](#def-b2-structures-generated) par. Demuestra que $G$ contiene un elemento de [orden](#def-b2-structures-generated) $2$. *(Emparéjese cada elemento con su inverso y cuéntense los que quedan emparejados consigo mismos.)*

**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](#def-b2-structures-generated) $2$.

**Ejercicio 1.6 ★★.**

Demuestra que $A_n$ ($n \geq 3$) está [generado](#def-b2-structures-generated) por los [ciclos](#def-b2-structures-sn) de longitud $3$. *(Un producto de dos [transposiciones](#def-b2-structures-sn) es un [ciclo](#def-b2-structures-sn) de longitud $3$ o un producto de dos [ciclos](#def-b2-structures-sn) de longitud $3$.)*

**Solución de Ejercicio 1.6.**

Todo elemento de $A_n$ es producto de un número par de [transposiciones](#def-b2-structures-sn) ([Teorema 1.21](#thm-b2-structures-signature): descompóngase en [transposiciones](#def-b2-structures-sn); el número es par porque la signatura vale $+1$). Basta con escribir cada producto de dos [transposiciones](#def-b2-structures-sn) mediante [ciclos](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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 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 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 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](#def-b2-structures-generated). *Indicación: sea $m$ el [orden](#def-b2-structures-generated) máximo entre los elementos de $G$; prueba que el [orden](#def-b2-structures-generated) de todo elemento divide a $m$ (aplicando el [Ejercicio 1.4](#exo-b2-structures-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](#def-b2-structures-generated).

**Solución de Ejercicio 1.10.**

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

*Afirmación: el [orden](#def-b2-structures-generated) de todo $x \in G$ divide a $m$.* Supongamos que algún $x$ tiene [orden](#def-b2-structures-generated) $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](#def-b2-structures-generated) $m'$; el elemento $x^{q/p^k}$ tiene [orden](#def-b2-structures-generated) $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](#exo-b2-structures-4) su producto tiene [orden](#def-b2-structures-generated) $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](#def-b2-structures-generated).

Para $K = \Z/p\Z$: $(\Z/p\Z)^*$ es un subgrupo finito de $K^*$, luego [cíclico](#def-b2-structures-generated) (de [orden](#def-b2-structures-generated) $p - 1$).

**Ejercicio 1.11 ★★★.**

Demuestra que el grupo $(\Q, +)$ no es [cíclico](#def-b2-structures-generated) y, peor aún, que ni siquiera es finitamente [generado](#def-b2-structures-generated). Demuestra en cambio que todo subgrupo finitamente [generado](#def-b2-structures-generated) de $(\Q, +)$ es [cíclico](#def-b2-structures-generated).

**Solución de Ejercicio 1.11.**

*No es [cíclico](#def-b2-structures-generated):* 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](#def-b2-structures-generated):* el subgrupo [generado](#def-b2-structures-generated) 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](#def-b2-structures-generated) son [cíclicos](#def-b2-structures-generated):* 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](#def-b2-structures-generated), [generado](#def-b2-structures-generated) por $\frac nQ$.

**Ejercicio 1.12 ★★.**

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

**Solución de Ejercicio 1.12.**

*Un subconjunto [numerable](#def-b2-structures-countable).* 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](#def-b2-structures-countable) de $E$.

*Infinito $\implies$ [equipotente](#def-b2-structures-countable) 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](#def-b2-structures-countable) 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](#def-b2-structures-countable) 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](#thm-b2-structures-signature) 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?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-f5599a3944b8.svg)

![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?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-848b52687905.svg)

*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](#thm-b2-structures-signature) y dos casillas son *contiguas* cuando comparten un lado de la bandeja.

**Parte I — Configuraciones, movimientos, signaturas.**

1. 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.
2. 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)$ .
3. 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.
4. 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.**

5. 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.
6. 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](#def-b2-structures-sn) fija de otras dos casillas.)*
7. 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.
8. 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)$.

9. 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}$ .
10. (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](#def-b2-structures-sn) $(11\ 12\ 15)$ y que el recorrido inverso da $(11\ 15\ 12)$ . Ambos pertenecen a $H$ .
11. (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](#def-b2-structures-sn) 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](#def-b2-structures-generated) [cíclico](#def-b2-structures-generated), comprueba que el recorrido elemental inverso de la pregunta 10 es exactamente $(x_0\ x_1\ x_2)$.
12. Demuestra la fórmula de conjugación en cualquier $\mathfrak{S}_n$: para una permutación $g$ y un [ciclo](#def-b2-structures-sn) 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.
13. Deduce que $H$ contiene los quince [ciclos](#def-b2-structures-sn) 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.**

14. (Lema A) Sean $s$ y $t$ dos [ciclos](#def-b2-structures-sn) 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](#def-b2-structures-generated) ), el producto $st$ es una doble [transposición](#def-b2-structures-sn) ; prueba que $A_4$ no contiene ningún subgrupo de [orden](#def-b2-structures-generated) $6$ *(un subgrupo de índice $2$ contiene todos los cuadrados; cuenta los [ciclos](#def-b2-structures-sn) 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\}$ .
15. (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](#def-b2-structures-sn) 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$ .
16. Deduce que el grupo $G$ del lema B contiene todas las permutaciones pares de $X \cup \{w\}$ *(usa el [Ejercicio 1.6](#exo-b2-structures-6): los [ciclos](#def-b2-structures-sn) de longitud $3$ generan)* . Después, encadenando los lemas A y B a lo largo de los [ciclos](#def-b2-structures-sn) consecutivos $s_0, s_1, \dots, s_{12}$ de la pregunta 13, demuestra que $\langle s_0, \dots,  s_{12}\rangle = A_{15}$ .
17. 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.
18. (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.**

19. (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.
20. (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.
21. (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.)*
22. (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](#def-b2-structures-sn) $\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](#def-b2-structures-sn) 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.
23. (Un tablero pobre) Sea ahora el tablero un único [ciclo](#def-b2-structures-sn) de $n \geq 4$ casillas con $n - 1$ fichas. Prueba que el [orden](#def-b2-structures-generated) [cíclico](#def-b2-structures-generated) 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](#def-b2-structures-generated) de [orden](#def-b2-structures-generated) $\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.
24. 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?
25. (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](#def-b2-structures-sn) de longitud $3$ ; la conjugación. Enuncia el metaprincipio en una línea.

**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](#def-b2-structures-sn) $(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](#def-b2-structures-sn) ni la signatura (descompóngase $\rho$ en [transposiciones](#def-b2-structures-sn); 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](#def-b2-structures-sn) $\zeta$ de longitud $15$. Su [orden](#def-b2-structures-generated) [cíclico](#def-b2-structures-generated) 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](#def-b2-structures-sn) 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](#def-b2-structures-sn). 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](#def-b2-structures-generated) $3$ y otro de [orden](#def-b2-structures-generated) $2$, así que $6 \mid \abs G$ (Lagrange, [Teorema 1.14](#thm-b2-structures-lagrange), aplicado a los dos subgrupos [cíclicos](#def-b2-structures-generated)). Si $A_4$ tuviera un subgrupo $K$ de [orden](#def-b2-structures-generated) $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](#def-b2-structures-sn) $\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](#def-b2-structures-sn) 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](#exo-b2-structures-6), los [ciclos](#def-b2-structures-sn) 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](#def-b2-structures-generated) $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](#def-b2-structures-sn) 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](#def-b2-structures-sn). Un movimiento intercambia el hueco con uno de sus dos vecinos. Leamos las fichas en [orden](#def-b2-structures-generated) [cíclico](#def-b2-structures-generated) 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](#def-b2-structures-generated) *[cíclico](#def-b2-structures-generated)* 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](#def-b2-structures-generated) $\operatorname{lcm}(n, n-1) = n(n-1)$ en el producto de los dos [grupos cíclicos](#def-b2-structures-generated) (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](#def-b2-structures-generated) 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](#def-b2-structures-sn)” 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](#def-b2-structures-generated) $6$ (pregunta 14). *Generación por [ciclos](#def-b2-structures-sn) de longitud $3$:* convirtió “$H$ contiene suficientes [ciclos](#def-b2-structures-sn) de longitud $3$” en “$H$ contiene todo $A_{15}$” (pregunta 16). *Conjugación:* fabricó los quince [ciclos](#def-b2-structures-sn) consecutivos de longitud $3$ a partir de un único recorrido $2 \times 2$ transportado por el gran recorrido (preguntas 12–13), y los [ciclos](#def-b2-structures-sn) $(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.