4.6: Ejercicios

1. Supongamos que se le da una lista de$n$ enteros, cada uno de tamaño como máximo$100n$. Cuántas operaciones te llevaría realizar las siguientes tareas (al responder a estas preguntas, nos interesa principalmente si tomará$\log ⁡n, \sqrt{n}, n, n^2, n^3, 2^n, …$ medidas. Es decir, ignorar las constantes multiplicativas. ):

a. Determinar si el número$2n+7$ está en la lista.

b. Determinar si hay dos números en la lista cuya suma es$2n+7$.

c. Determine si hay dos números en la lista cuyo producto es$2n+7$ (¡Este es más sutil de lo que podría parecer! Puede ser de su ventaja ordenar los enteros en la lista).

d. Determinar si existe un número$i$ para el cual todos los números de la lista están entre$i$ y$i+2n+7$.

e. Determinar la secuencia más larga de números enteros consecutivos pertenecientes a la lista.

f. Determinar el número de primos en la lista.

g. Determinar si hay tres enteros$x, y$ y$z$ de la lista para que$x+y=z$.

h. Determinar si hay tres enteros$x, y$ y$z$ de la lista para que$x^2 + y^2 = z^2$.

i. Determinar si hay tres enteros$x, y$ y$z$ de la lista para que$xy = z$.

j. Determinar si hay tres enteros$x, y$ y$z$ de la lista para que$x^y = z$.

k. Determinar si hay dos enteros$x$ y$y$ de la lista para que$xy$ sea un primo.

i. Determinar la progresión aritmética más larga de la lista (una secuencia ($a_1,a_2,…,a_t$) es una progresión aritmética cuando hay una constante de$d \neq 0$ manera que$a_{i+1}=a_i+d$, para cada una$i=1,2,…,t−1$).

m. Determinar el número de sumas distintas que se pueden formar a partir de los miembros de la lista (arbitrariamente se permite que muchos enteros de la lista sean términos en la suma).

n. Determinar el número de productos distintos que se pueden formar a partir de los miembros de la lista (arbitrariamente se permite que muchos enteros de la lista sean factores en el producto).

o. Determinar para qué enteros$m$, la lista contiene al menos el 10% de los enteros de$\{1,2,...,m\}$.

2. Si tienes que meter$n+1$ palomas en n hoyos, tienes que meter dos palomas en el mismo hoyo. ¿Qué pasa si hay que meter$mn+1$ palomas en$n$ hoyos?

3. Considera el conjunto$X=\{1,2,3,4,5\}$ y supongamos que tienes dos agujeros. También suponga que tiene 10 palomas: los subconjuntos de 2 elementos de$X$. ¿Puedes poner estas 10 palomas en los dos agujeros de una manera que no haya un subconjunto de 3 elementos$S=\{a,b,c\} \subset X$ para el que todas las palomas$S$ vayan en el mismo hoyo? Entonces responde la misma pregunta si$X=\{1,2,3,4,5,6\}$ con$15=C(6,2)$ palomas.

4. Vamos$n=10,000$. Supongamos que un amigo te dice que tiene una familia secreta de subconjuntos de$\{1,2,…,n\}$, y si lo adivinas correctamente, te dará un millón de dólares. Crees que conoces la familia de subconjuntos que tiene en mente y contiene exactamente la mitad de los subconjuntos, es decir, la familia tiene$2^{n−1}$ subconjuntos. Discuta cómo puedes compartir tu corazonada con tu amigo en un esfuerzo por ganar el premio.

5. Dejar$N$ denotar el conjunto de enteros positivos. Cuando$f:N \rightarrow N$ es una función, deja$E(f)$ ser la función definida por$E(f)(n)=2^{f(n)}$. ¿Qué es$E^5(n^2)$?