Esame di Stato 2014 – 5

di

Dei numeri 1, 2, 3, …, 6000, quanti non sono divisibili né per 2, né per 3, né per 5?

Soluzione 1

Utilizza la forza bruta

  1. Scrivi i numeri da 1 a 6000
  2. Elimina i multipli di 2
  3. Elimina i multipli di 3
  4. Elimina i multipli di 5
  5. Conta i numeri rimanenti.

Soluzione 2

Ricorda che

  • Se \displaystyle X\cap Y=\empty allora \displaystyle \sharp(X \cup Y)=\sharp(X)+\sharp(Y)
    altrimenti
    \displaystyle \sharp(X \cup Y)=\sharp(X)+\sharp(Y)-\sharp(X\cap Y)
  • Se \displaystyle Y \subseteq X allora \displaystyle \sharp(X \setminus Y)=\sharp(X)-\sharp(Y)
    altrimenti
    \displaystyle \sharp(X \setminus Y)=\sharp(X)-\sharp(X\cap Y)

Osserva l’immagine a destra e considera che

M2 ∪ M3 ∪ M5 = M2 ∪ M3 ∪ M5 \ M6 \ M10 \ M15 ∪ M30

e di conseguenza

#(M2 ∪ M3 ∪ M5) = #(M2 ∪ M3 ∪ M5 \ M6 \ M10 \ M15 ∪ M30) = #(M2) + #(M3) + #(M5) – #(M6) – #(M10) – #(M15) + #(M30)

È necessario calcolare la cardinalità di tutti gli insiemi nella tabella…

InsiemeElementiCardinalità
I1, 2, 3, 4, …, 6000#(I) = 6000
M22, 4, 6, 8, …, 6000#(M2) = 3000
M33, 6, 9, 12, …, 6000#(M3) = 2000
M55, 10, 15, 20, …, 6000#(M5) = 1200
M6 = M2 ∩ M36, 12, 18, 24, …, 6000#(M6) = 1000
M10 = M2 ∩ M510, 20, 30, 40, …, 6000#(M10) = 600
M15 = M3 ∩ M515, 30, 45, 60, …, 6000#(M15) = 400
M30 = M2 ∩ M3 ∩ M530, 60, 90, 120, …, 6000#(M30) = 200
M2 ∪ M3 ∪ M52, 3, 4, 5, …, 6000#(M2 ∪ M3 ∪ M5) = ?
I \ (M2 ∪ M3 ∪ M5)1, 7, 11, 13, …#(I \ (M2 ∪ M3 ∪ M5)) = ?

Allora

#(M2 ∪ M3 ∪ M5) = 3000 + 2000 + 1200 – 1000 – 600 – 400 + 200 = 4400

e quindi

#(I \ (M2 ∪ M3 ∪ M5)) = 6000 – 4400 = 1600