Buscar problemas de inducción que no estén basados en fórmulas

Question

Estoy buscando problemas que utilicen la inducción en sus pruebas como éste: Dado un tablero de damas al que se le ha quitado una casilla, puedes cubrirlo con piezas en forma de L hechas con tres casillas. Este problema es muy diferente de la mayoría de los problemas de inducción que se basan en el álgebra. ¿Conoces algún otro? Busco problemas de tipo geométrico o algorítmico.

Answer 1

A continuación se presentan algunos problemas con algunas imágenes ilustrativas. Todos los problemas fueron tomados del excelente libro de Daniel J. Velleman Cómo demostrarlo: Un enfoque estructurado .

$\textbf{Problem 1:}$ Para todos $n\in \mathbb{N}$ , si $n\ge 3$ , entonces si $n$ los puntos distintos de un círculo se conectan en orden consecutivo con líneas rectas, entonces los ángulos interiores del polígono resultante suman $(n-2)180º$ .

Caso $n=4$ :

Paso inductivo:

$\textbf{Problem 2:}$ Dejemos que $n\in \mathbb{N}$ . Un triángulo equilátero se corta en $4^n$ triángulos equiláteros congruentes, y se elimina una esquina. Demuestra que el área restante puede ser cubierta por baldosas trapezoidales que tienen este aspecto: .

Caso $n=2$ :

$\textbf{Problem 3:}$ Dejemos que $n\in \mathbb{N}$ . Supongamos que $n$ Las cuerdas se dibujan en un círculo de tal manera que cada cuerda se cruza con las demás, pero no hay tres que se crucen en un punto. Demuestra que las cuerdas cortan el círculo en $\displaystyle \frac{n^2+n+2}{2}$ regiones.

Caso $n=4$ :

$\textbf{Problem 4:}$ Dejemos que $n\in \mathbb{N}$ y supongamos que $n$ Las cuerdas se dibujan en un círculo, cortando el círculo en una serie de regiones. Demuestra que las regiones pueden ser coloreadas con dos colores de tal manera que las regiones adyacentes (es decir, las regiones que comparten una arista) sean de diferente color.

Caso $n=4$ :

Answer 2

Puede que quieras mirar este pdf: Estructura de la prueba por inducción que proporciona la inducción "tradicional, basada en fórmulas" para ayudar a explicar la lógica de las pruebas inductivas, pero comienza con, e incluye algunos ejemplos dispersos de su aplicabilidad a los algoritmos de tipo recursivo y a los argumentos de conteo: problema del dominó, problema del cambio de monedas.

De hecho, la corrección del algoritmo recursivo para resolver el Problema de la Torre de Hanoi se reduce a una prueba por inducción (véase el análisis lógico de la solución recursiva). Las pruebas inductivas también se utilizan a menudo en la teoría de grafos.

Ver también este post que te enlaza a un post anterior en el que se pedía ejemplos de inducción matemática . Obtendrá una rica mezcla de tipos de problemas y verá la amplitud de su utilidad.

Answer 3

1. Estos Las pruebas de inducción son interesantes. Mira los ejemplos.

2. Demostrar que todo número entero mayor que 2 se puede escribir como producto de primos.(Inducción fuerte)

3. Demuestra que todo entero mayor que 12 puede hacerse como suma de 4 y 5s.(El original tiene que ver con monedas y sellos de correos)