2. Demuestre que el importe postal de 24 centavos o más se logra usando sólo timbres de 5 y 7 centavos.
3. Utilice la forma
Si S(n) es verdadera, entonces S(n + 1) es verdadera
del paso inductivo para probar la afirmación del ejemplo 1.8.1.
4. Utilice la forma
Si S(n) es verdadera, entonces S(n + 1) es verdadera del paso inductivo para probar la afirmación en el ejercicio 1.
5. Utilice la forma Si S(n) es verdadera, entonces S(n + 1) es verdadera del paso inductivo para probar la afirmación en el ejercicio 2.
Los ejercicios 6 y 7 se refieren a la secuencia c1, c2,... definida por las
ecuaciones
c1= 0,
cn = c n/2 + n2 para toda n > 1.
6. Calcule c2, c3, c4 y c5.
7. Pruebe que cn < 4n2 para toda n ≥ 1.
Los ejercicios 8 al 10 se refieren a la secuencia c1, c2, . . . definida porlas ecuaciones
c1 = 0, para toda n > 1.
8. Calcule c2, c3, c4 y c5.
9. Pruebe que cn
≤ 4(n – 1)2 para toda n ≥ 1.
10. Pruebe que (n+1)2/8 < Cn para toda n ≥ 2. Pista: Los pasos base son n = 2, 3. Además n/2 ≥ (n − 1)/2 para toda n. Get 1.8.10 exercise solution
11. Suponga que se tienen dos pilas de cartas cada una con n cartas.
Dos jugadores juegan el siguiente juego. Cada jugador, en su turno, elige una pila y quita cualquier número de cartas, pero al menos una, de la pila elegida. El jugador que quita la última carta gana
el juego. Muestre que el segundo jugador siempre puede ganar. Get 1.8.11 exercise solution
En los ejercicios 12 al 17, encuentre el cociente q y el residuo r como
en el teorema 1.8.5 cuando n se divide entre d.
12. n = 47, d = 9 Get 1.8.12 exercise solution
13. n = −47, d =9 Get 1.8.13 exercise solution
14. n = 7, d = 9 Get 1.8.14 exercise solution
15. n = −7, d = 9 Get 1.8.15 exercise solution
16. n = 0, d = 9 Get 1.8.16 exercise solution
17. n = 47, d = 47 Get 1.8.17 exercise solution
Los egipcios de la antigüedad expresaban una fracción como la suma de
fracciones cuyos numeradores eran 1. Por ejemplo, 5/6 se expresaba como
Decimos que la fracción p/q, donde p y q son enteros positivos, está en
forma egipcia si
donde n1, n2, . . . , nk son enteros positivos que satisfacen n1 < n2 < . . . < nk.
18. Demuestre que la representación (1.8.2) no tiene que ser única representando 5/6 de dos maneras diferentes. Get 1.8.18 exercise solution
19. Demuestre que la representación (1.8.2) nunca es única. Get 1.8.19 exercise solution
20. Siguiendo los pasos descritos, proporcione una prueba por inducción sobre p para demostrar que toda fracción p/q con 0 < p/q < 1 puede expresarse en forma egipcia.
a) Verifique el paso base (p = 1).
b) Suponga que 0 < p/q < 1 y que todas las fracciones i/q , con 1 ≤ i < p y q arbitrarios, se pueden expresar en la forma egipcia.
Seleccione el menor entero positivo n con 1/n ≤ p/q. Demuestre que
c) Demuestre que si p/q = 1/n, la prueba queda completa.
21. Use el método del ejercicio anterior para encontrar formas egipcias para 3/8, 5/7 y 3/19.
22. Demuestre que cualquier fracción p/q, donde p y q son enteros positivos, se puede escribir en la forma egipcia. (No se está suponiendo que p/q < 1).
23. Demuestre que cualquier tablero deficiente de n × n se puede enlosar con trominos si n es impar, n > 5 y 3 divide a n2 – 1. Sugerencia: Use las ideas mencionadas en la sugerencia del ejercicio 33, sección 1.7. Get 1.8.23 exercise solution
24. Demuestre que cualquier tablero deficiente de n × n se puede enlosar con trominos si n es par, n > 8 y 3 divide a n2 – 1. Sugerencia: Tome como base el hecho de que un tablero deficiente de 4 × 4 se puede enlosar con trominos; ejercicios 23 y 31, sección 1.7. Get 1.8.24 exercise solution
25. Proporcione una prueba alternativa de la existencia de q y r en el teorema 1.8.5 para el caso n ≥ 0; para ello demuestre primero que el conjunto X de todos los enteros k donde dk > n es un conjunto
no vacío de enteros no negativos, después demuestre que X tiene un elemento menor, y por último analice el elemento menor de X. Get 1.8.25 exercise solution
26. Proporcione una prueba alternativa de la existencia de q y r en el teorema 1.8.5 usando la forma de inducción matemática donde el paso inductivo es “si S(n) es verdadera, entonces S(n + 1) es verdadera”.
Sugerencia: Primero suponga que n > 0. Maneje el caso n = 0 por separado. Reduzca el caso n < 0 al caso n > 0. Get 1.8.26 exercise solution
27. Suponga la forma de inducción matemática donde el paso inductivo es “si S(n) es verdadera, entonces S(n + 1) es verdadera”.
Pruebe la propiedad del buen orden. Get 1.8.27 exercise solution
28. Suponga la propiedad del buen orden. Pruebe la forma fuerte de inducción matemática. Get 1.8.28 exercise solution
29. Demuestre que la forma fuerte de inducción matemática y la forma de inducción matemática donde el paso inductivo es “si S(n) es verdadera, entonces S(n + 1) es verdadera” son equivalentes. Es decir,suponga la forma fuerte de inducción matemática y pruebe la forma alternativa; después suponga la forma alternativa y pruebe la forma fuerte de inducción matemática.
