Divisibilidad y Venn

Hallar cuantos números del conjunto S={1,2,3,…,120) son divisibles
por:
a)Exactamente tres de 2,3,5,7
b)Exactamente dos de  2,3,5,7
c)Exactamente uno de  2,3,5,7
d)Ninguno de 2,3,5,7
e)¿Cuantos primos hay en S?

Principuio de inclusiones y exclusiones …
Sea D_i_j_… el número de ellos divisibles por i, j, … Entonces,

D_2 = [120/2] = 60
D_3 = [120/3] = 40
D_5 = [120/5] = 24
D_7 = [120/7] = 17
D_2_3 = D_6 = [120/6] = 20
D_2_5 = D_10 = [120/10] = 12
D_2_7 = D_14 ) = [120/14] = 8
D_3_5 = D_15 = [120/15] = 8
D_3_7 = D_21 = [120/21] = 5
D_5_7 = D_35 = [120/35] = 3
D_2_3_5 = D_30 = [120/30] = 4
D_2_3_7 = D_42 = [120/42] = 2
D_2_5_7 = D_70 = [120/70] = 1
D_3_5_7 = D_105 = [120/105] = 1
D_2_3_5_7 = D_210 = [120/210] = 0

> a)Exactamente tres de 2,3,5,74 + 2 + 1 + 1 – 4*0 = 8
 

> b)Exactamente dos de  2,3,5,720 + 12 + 8 + 8 + 5 + 3 – 3*8 =  32
 

> c)Exactamente uno de  2,3,5,760 + 40 + 24 + 17 – 2*32 – 3*8 = 53
 

> d)Ninguno de 2,3,5,7120 – 53 – 32 – 8 =  27
 

> e)¿Cuantos primos hay en S?

 

27 + #{2, 3, 5, 7} – #{1} = 30

—
Ignacio Larrosa Cañestro

 

Si llamamos :

S_0=120
S_1=D_2 +D_3+D_5+D_7 =141
S_2=D_2_3 +D_2_5+D_2_7+D_3_5+D_3_7+D_5_7 =56
S_3=D_2_3_5+D_2_3_7+D_2_5_7+D_3_5_7 =8
S_4=D_2_3_5_7 =0

El número de elementos de S que satisfacen exactamente m condiciones (en nuestro caso, múltiplos de 1 núnero,múltiplos de 2 números,múltiplos de 3 numeros,múltiplos de 4 números y múltiplos de 0 números) el Grimaldi en el capitulo de Exclusión Inclusión página 416 nos da la fórmula para ello:

E(m)=S_m – C(m+1,1)*S_(m+1) + C(m+2,2)*S_(m+2) – C(m+3,3)*S_(m+3) +… 

E(0)=120-C(1,1)*S_1+C(2,2)*S_2-C(3,3)*S_3-C(4,4)*S_4 =120-141+56-8+0=27     Ninguno de 2,3,5,7

E(1)=S_1-C(2,1)*S_2+C(3,2)*S_3-C(4,3)*S_4 = 141-2*56+3*8-12*0=53  Uno exactamente

E(2)=S_2-C(3,1)*S_3+C(4,2)*S_4=56-3*8+6*0=32  Dos exactamente

E(3)=S_3-C(4,1)*S_4=8   Tres exactamente

La fórmula que nos da el número de elementos de S que satisfacen al menos m de las condiciones es:

L_m=S_m- C(m,m-1)*S_(m+1)+C(m+1,m-1)*S_(m+2) – …

Leon-Sotelo

También podriamos recurrir al diagrama de Venn con cuatro conjuntos

 

http://en.wikipedia.org/wiki/Image:Edwards-Venn-four.png

León-Sotelo

¿Cuantos enteros positivos menores que 2007 son coprimos con 1001?
¿Cuantos tienen exactamente un divisor primo común con 1001?
¿Cuantos exactamente dos?
¿Cuantos exactamente tres?
¿Cuantos al menos uno?
¿Cuantos al menos dos? 

Como es archiconocido, 1001 = 7*11*13, y 2007 = 2*1001 + 5, no tiene
factores comunes con 1001. Hallemos los que tienen algún factor común con
1001. Llamando m(i) al número de multiplos de i menores que 2007, y
aplicando el principio de inclusiones y exclusiones, este número es:

M = m(7) + m(11) + m(13) – m(77) – m(91) – m(143) + m(1001)

    = [2007/7] + [2007/11] + [2007/13] – [2007/77] – [2007/91] – [2007/143]
+ [2007/1001]

    = 286 + 182 + 154 – 26 – 22 – 14 + 2 = 562

Por tanto, el número pedido es 2006 – 562 = 1444 (= 38^2)

> ¿Cuantos tienen exactamente un divisor primo común con 1001?[2007/7] + [2007/11] + [2007/13] – 2*[2007/77] – 2*[2007/91] – 2*[2007/143]
+ 3*[2007/1001]

   = 286 + 182 + 154 – 2*26 – 2*22 – 2*14 + 3*2 =504

Como 1001 está libre de cuadrados, esto coincide con #{n < 2007 | mcd(n,
1001) es primo}

> ¿Cuantos exactamente dos?[2007/77] + [2007/91] + [2007/143] – 2* [2007/1001]

  =  26 + 22 + 14 – 3*2 = 56

> ¿Cuantos exactamente tres?[2007/1001] = 2

> ¿Cuantos al menos uno?Ya queda dicho en la primera respuesta, 562, por otra parte  igual a 504 +
56 + 2.

> ¿Cuantos al menos dos?Pues 56 + 2 = 58.

Pareca que el tema está bastante trillado, ¿no? 

 http://www.artofproblemsolving.com/Forum/viewtopic.php?t=243336

 

 

~ por leonsotelo en diciembre 5, 2008.