6.7: Inducción en geometría, combinatoria y teoría de números

Última actualización
Guardar como PDF

Page ID: 108177

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Pasamos junto a una colección mixta de problemas diseñados para resaltar una gama de aplicaciones.

Problema 256 Vamos $f_{1} = 2$ , $f_{k + 1} = f_{k} (f_{k} + 1)$ . Demostrar por inducción que $f_{k}$ tiene al menos k factores primos distintos.

Problema 257

(a) Demostrar por inducción que n puntos en una línea recta dividen la línea en $n + 1$ partes.

(b) (i) Experimentando con valores pequeños de n, adivina una fórmula $R_{n}$ para el número máximo de regiones que se pueden crear en el plano mediante una matriz de n líneas rectas.

(ii) Demostrar por inducción que n líneas rectas en el plano dividen el plano en como máximo $R_{n}$ regiones.

(c) (i) Experimentando con valores pequeños de n, adivina una fórmula $S_{n}$ para el número máximo de regiones que se pueden crear en 3 dimensiones mediante una matriz de n planos.

(ii) Demostrar por inducción que n planos en 3 dimensiones dividen el espacio en como máximo $S_{n}$ regiones.

Problema 258 Dado un cuadrado, demostrar que, para cada $n \geq 6$ , el cuadrado inicial se puede cortar en n cuadrados (de posiblemente diferentes tamaños).

Problema 259 Un árbol es una gráfica conectada, o red, que consiste en vértices y aristas, pero sin ciclos (o circuitos). Demostrar que un árbol con n vértices tiene exactamente $n - 1$ bordes.

El siguiente problema se refiere a los poliedros esféricos. Un poliedro esférico es una superficie poliédrica en 3 dimensiones, que se puede inflar para formar una esfera (donde asumimos que las caras y bordes pueden estirarse según sea necesario). Por ejemplo, un cubo es un poliedro esférico; pero la superficie de un marco no lo es. Un poliedro esférico tiene

caras (polígonos planos bidimensionales, que se pueden estirar para tomar la forma de un disco),
aristas (segmentos de línea unidimensionales, donde se encuentran exactamente dos caras), y
vértices (puntos 0-dimensionales, donde se encuentran varias caras y aristas, de tal manera que forman un solo ciclo alrededor del vértice).

Cada cara debe tener claramente al menos 3 bordes; y debe haber al menos tres bordes y tres caras que se encuentran en cada vértice.

Si un poliedro esférico tiene V vértices, bordes E y caras F, entonces los números V, E, F satisfacen la fórmula de Euler

$V - E + F = 2.$

Por ejemplo, un cubo tiene $V = 8$ vértices, $E = 12$ bordes, y $F = 6$ rostros, y $8 - 12 + 6 = 2$ .

Problema 260

(a) (i) Describir un poliedro esférico con exactamente 6 aristas.

(ii) Describir un poliedro esférico con exactamente 8 bordes.

b) Demostrar que ningún poliedro esférico puede tener exactamente 7 aristas.

c) Demostrar que para cada $n \geq 8$ , existe un poliedro esférico con n bordes.

Problema 261 Un mapa es una colección (finita) de regiones en el plano, cada una con un límite, o borde, que es `polígonal' en el sentido de que consiste en una sola secuencia de vértices distintos y —posiblemente curvados— bordes, que separan el plano en dos partes, una de las cuales es la poligonal región misma. Un mapa puede ser coloreado correctamente si a cada región se le puede asignar un color para que cada par de regiones vecinas (compartiendo un borde) siempre reciba diferentes colores. Demuestre que las regiones de dicho mapa pueden colorearse correctamente con solo dos colores si y solo si un número par de bordes se encuentran en cada vértice.

Problema 262 (Códigos grises) Hay $2^{n}$ secuencias de longitud n que consisten en 0s y 1s. Demostrar que, para cada $n \geq 2$ , estas secuencias se pueden organizar en una lista cíclica de tal manera que dos secuencias vecinas cualesquiera (incluyendo la última y la primera) difieran exactamente en una posición de coordenadas.

Problema 263 (Árbol Calkin-Wilf) El árbol binario en el plano tiene un vértice distinguido como `raíz', y se construye inductivamente. La raíz se une a dos nuevos vértices; y cada nuevo vértice se une luego a otros dos vértices nuevos, con el proceso de construcción que continúa para siempre (Figura 11). Etiquete los vértices del árbol binario con fracciones positivas de la siguiente manera:

a la raíz se le da la etiqueta $\frac{1}{1}$
siempre que sepamos la etiqueta $\frac{i}{j}$ de un vértice 'padre', etiquetamos su `descendiente izquierdo' como $\frac{i}{i + j}$ , y su `descendiente derecho' $\frac{i + j}{j}$ .

a) Demostrar que todo racional positivo $\frac{r}{s}$ ocurre una vez y sólo una vez como etiqueta, y que ocurre en sus términos más bajos.

b) Demostrar que las etiquetas son simétricas izquierda-derecha en el sentido de que las etiquetas en las posiciones izquierda y derecha correspondientes son recíprocas entre sí.

Problema 264 Una colección de n intervalos en el eje x es tal que cada par de intervalos tiene un punto en común. Demostrar que todos los n intervalos deben tener entonces al menos un punto en común.