3.11: Ejercicios

1. Una base de datos utiliza identificadores de registro que son cadenas alfanuméricas en las que los 10 dígitos decimales y las 26 letras mayúsculas son símbolos válidos. Los criterios que definen un identificador de registro válido son recursivos. Un identificador de registro válido de longitud se\(n \geq 2\) puede construir de las siguientes maneras:

• comenzando con cualquier letra mayúscula que no sea\(D\) y seguida de cualquier identificador válido de registro de longitud\(n−1\);
• comenzando con\(1C, 2K\), o\(7J\) y seguido de cualquier identificador de registro válido de longitud\(n−2\);
• comenzando con\(D\) y seguido de cualquier cadena de dígitos\(n-1\) decimales;

Dejar\(r(n)\) denotar el número de identificadores de registro válidos de longitud\(n\). Tomamos\(r(0)=1\) y tomamos nota de eso\(r(1)=26\). Encuentra una recursión para\(r(n)\) cuándo\(n \geq 2\) y úsalo para calcular\(r(5)\).

2. Considera un\(1 \times n\) tablero de ajedrez. Los cuadrados del tablero de ajedrez se van a pintar de blanco y oro, pero no hay dos cuadrados consecutivos que se puedan pintar de blanco. Dejar\(p(n)\) denotar el número de formas de pintar el tablero de ajedrez sujeto a esta regla. Encuentra una fórmula recursiva para\(p(n)\) válido para\(n \geq 3\).

3. Dar una recursión para el número\(g(n)\) de cadenas ternarias de longitud\(n\) que no contienen 102 como subcadena.

4. Un\(2 \times n\) tablero de ajedrez debe ser alicatado usando dos tipos de azulejos. El primer azulejo es un azulejo\(1 \times 1\) cuadrado. La segunda baldosa se llama\(L\) -tile y se forma quitando el\(1 \times 1\) cuadrado superior derecho de una\(2 \times 2\) baldosa. Los\(L\) -tiles se pueden utilizar en cualquiera de las cuatro formas en que se pueden girar. (Es decir, el “cuadrado faltante” puede estar en cualquiera de las cuatro posiciones.) Dejar\(t(n)\) denotar el número de inclinaciones del\(2 \times n\) tablero de ajedrez utilizando\(1 \times 1\) azulejos y\(L\) -azulejos. Encuentre una fórmula recursiva para\(t(n)\) y úsela para determinar\(t(7)\).

5. Dejar\(S\) ser el conjunto de cadenas en el alfabeto\(\{0,1,2,3\}\) que no contienen 12 o 20 como subcadena. Dar una recursión para el número\(h(n)\) de cadenas en\(S\) de longitud\(n\).

Pista

Verifique su recursión computando manualmente\(h(1), h(2), h(3)\), y\(h(4)\).

6. Encuentra\(d=gcd(5544,910)\) así como enteros\(a\) y\(b\) tal que\(5544a + 910b = d\).

7. Encuentra\(gcd(827,249)\) así como enteros\(a\) y\(b\) tal que\(827a+249b=6\).

8. Dejar\(a,b,m\), y\(n\) ser enteros y supongamos que\(am+bn=36\). ¿De qué se puede decir\(gcd(m,n)\)?

9. (Un problema desafiante) Para cada fórmula, dé tanto una prueba usando el Principio de Inducción Matemática como una prueba combinatoria. Uno de los dos será más fácil mientras que el otro será más desafiante.

a)\(1^2+2^2+3^2+ \cdot \cdot \cdot + n^2 = \dfrac{n(n+1)(2n+1)}{6}\)

b)\(\dbinom{n}{0}2^0 + \dbinom{n}{1}2^1 + \dbinom{n}{2}2^2 + \cdot \cdot \cdot + \dbinom{n}{n}2^n = 3^n\)

10. Demostrar que para todos los enteros\(n \geq 4\),\(2^n < n!\).

11. Demostrar que para todos los enteros positivos\(n\),

\(\displaystyle \sum_{i=0}^n 2^i = 2^{n+1} - 1\).

12. Mostrar que para todos los enteros positivos\(n, 7^n- 4^n\) es divisible por 3.

13. Mostrar que para todos los enteros positivos\(n,9^n-5^n\) es divisible por 4.

14. Resulta que si\(a\) y\(b\) son enteros positivos con\(a > b+1\), entonces hay un entero positivo\(M > 1\) tal que\(a^n-b^n\) es divisible por\(M\) para todos los enteros positivos\(n\). Determinar\(M\) en términos de\(a\)\(b\) y y demostrar que es un divisor de\(a^n-b^n\) para todos los enteros positivos\(n\).

15. Utilice la inducción matemática para demostrar que para todos los enteros\(n \geq 1\),

\(n^3+(n+1)^3 + (n+2)^3\)

es divisible por 9.

16. Dar una prueba por inducción del Teorema Binomial (Teorema 2.30). ¿Cómo cree que se compara con el argumento combinatorio dado en el Capítulo 2?

17. Considera la recursividad dada por\(f(n)=2f(n−1)−f(n−2)+6\) for\(n \geq 2\) with\(f(0)=2\) y\(f(1)=4\). Usa la inducción matemática para demostrarlo\(f(n)=3n^2−n+2\) para todos los enteros\(n \geq 0\).

18. Considera la recursividad dada por\(f(n)=f(n−1)+f(n−2)\) for\(n \geq 3\) with\(f(1)=f(2)=1\). Mostrar que\(f(n)\) es divisible por 3 si y solo si\(n\) es divisible por 4.

19. Supongamos que\(x \in \mathbb{R}\) y\(x > −1\). Demostrar que para todos los enteros\(n \geq 0\),\((1+x)^n \geq 1 + nx\).

20. Demostrar que hay una constante positiva\(c\) para que cualquier algoritmo que ordene una secuencia de enteros\(n\) positivos debe, en el peor de los casos, dar\(cn \log n\) pasos.

Pista

Hay\(n!\) permutaciones de un conjunto de enteros\(n\) distintos. Cada operación reduce el número de posibilidades en una fracción multiplicativa que es como mucho\(1/2\). Entonces si hay\(t\) operaciones, entonces\(2^t \geq n!\). Ahora busque la aproximación de Stirling\(n!\) y continúe a partir de ahí.