4.6: Ejercicios
( \newcommand{\kernel}{\mathrm{null}\,}\)
1. Supongamos que se le da una lista den enteros, cada uno de tamaño como máximo100n. Cuántas operaciones te llevaría realizar las siguientes tareas (al responder a estas preguntas, nos interesa principalmente si tomarálogn,√n,n,n2,n3,2n,… medidas. Es decir, ignorar las constantes multiplicativas. ):
a. Determinar si el número2n+7 está en la lista.
b. Determinar si hay dos números en la lista cuya suma es2n+7.
c. Determine si hay dos números en la lista cuyo producto es2n+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úmeroi para el cual todos los números de la lista están entrei yi+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 enterosx,y yz de la lista para quex+y=z.
h. Determinar si hay tres enterosx,y yz de la lista para quex2+y2=z2.
i. Determinar si hay tres enterosx,y yz de la lista para quexy=z.
j. Determinar si hay tres enterosx,y yz de la lista para quexy=z.
k. Determinar si hay dos enterosx yy de la lista para quexy sea un primo.
i. Determinar la progresión aritmética más larga de la lista (una secuencia (a1,a2,…,at) es una progresión aritmética cuando hay una constante ded≠0 manera queai+1=ai+d, para cada unai=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é enterosm, la lista contiene al menos el 10% de los enteros de{1,2,...,m}.
2. Si tienes que metern+1 palomas en n hoyos, tienes que meter dos palomas en el mismo hoyo. ¿Qué pasa si hay que metermn+1 palomas enn hoyos?
3. Considera el conjuntoX={1,2,3,4,5} y supongamos que tienes dos agujeros. También suponga que tiene 10 palomas: los subconjuntos de 2 elementos deX. ¿Puedes poner estas 10 palomas en los dos agujeros de una manera que no haya un subconjunto de 3 elementosS={a,b,c}⊂X para el que todas las palomasS vayan en el mismo hoyo? Entonces responde la misma pregunta siX={1,2,3,4,5,6} con15=C(6,2) palomas.
4. Vamosn=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 tiene2n−1 subconjuntos. Discuta cómo puedes compartir tu corazonada con tu amigo en un esfuerzo por ganar el premio.
5. DejarN denotar el conjunto de enteros positivos. Cuandof:N→N es una función, dejaE(f) ser la función definida porE(f)(n)=2f(n). ¿Qué esE5(n2)?