podzielność - ile jest liczb niepodzielnych przez 3,5,7

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Przemekw
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 31 sie 2006, o 23:49
Płeć: Mężczyzna
Lokalizacja: Łódź

podzielność - ile jest liczb niepodzielnych przez 3,5,7

Post autor: Przemekw »

Ile jest liczb całkowitych między 1 a 1000, które nie są podzielne przez 3, 5, 7?

pozdrawiam
PRzemek
Ostatnio zmieniony 9 wrz 2006, o 00:40 przez Przemekw, łącznie zmieniany 1 raz.
liu
Użytkownik
Użytkownik
Posty: 1330
Rejestracja: 10 paź 2004, o 13:30
Płeć: Mężczyzna
Lokalizacja: Suchedniów
Pomógł: 104 razy

podzielność - ile jest liczb niepodzielnych przez 3,5,7

Post autor: liu »

Hmm, niech

A - zbior liczb calkowitych miedzy 1 a 1000 podzielnych przez 3
B - zbior liczb calkowitych miedzy 1 a 1000 podzielnych przez 5
C - zbior liczb calkowitych miedzy 1 a 1000 podzielnych przez 7
X = {1,2,...,1000}.
Oznaczmy n(A) - liczba elementow zbioru A.
Latwo sprawdzic (to szczegolny przypadek wzoru wlaczen i wylaczen), ze

\(\displaystyle{ n(A \cup B \cup C) = n(A) + n(B) - n(A\cap B) + n(C) - n(A\cap C) - n(B\cap C) - n(A \cap B \cap C).}\)

Mamy policzyc ile jest liczb takich, ktorych nie dzieli ani 3, ani 5, ani 7, czyli innymi slowy moc zbioru \(\displaystyle{ (X-A)\cap (X-B) \cap (X-C) = X-(A \cup B \cup C)}\), czyli \(\displaystyle{ 1000 - n(A\cup B\cup C)}\).

No to liczymy:

Do zbioru A naleza liczby:
\(\displaystyle{ 3 = 1\cdot 3, 2\cdot 3, \ldots, 333 \cdot 3 = 999}\)
wiec \(\displaystyle{ n(A) = 333}\).

Do zbioru B naleza liczby:
\(\displaystyle{ 5 = 1\cdot 5, 2\cdot 5, \ldots, 200\cdot 5 = 1000}\)
wiec \(\displaystyle{ n(B) = 200}\).

Do zbioru C naleza liczby:
\(\displaystyle{ 7 = 1\cdot 7, 2\cdot 7, \ldots, 142\cdot 7 = 994}\)
wiec \(\displaystyle{ n(C) = 142}\).

Do zbioru \(\displaystyle{ A\cap B}\) naleza liczby podzielne przez 3 i przez 5, a wiec podzielne przez 15:
\(\displaystyle{ 15 = 1\cdot 15, 2\cdot 15, \ldots, 66\cdot 15 = 990}\)
\(\displaystyle{ n(A\cap B) = 66.}\)

Do zbioru \(\displaystyle{ A\cap C}\) naleza liczby podzielne przez 21:
\(\displaystyle{ 21 = 1\cdot 21, 2\cdot 21, \ldots, 47\cdot 21 = 987}\)
\(\displaystyle{ n(A\cap C) = 47.}\)

Do zbioru \(\displaystyle{ B \cap C}\) naleza liczby podzielne przez 5*7=35:
\(\displaystyle{ 35 = 1\cdot 35, 2\cdot 35, \ldots, 28\cdot 35 = 980}\)
\(\displaystyle{ n(B\cap C) = 28}\).

Do zbioru \(\displaystyle{ A\cap B \cap C}\) naleza liczby podzielne przez 105:
\(\displaystyle{ 105 = 1\cdot 105, 2\cdot 105, \ldots, 9\cdot 105 = 945}\)
\(\displaystyle{ n(A\cap B\cap C)=9}\).

Uff, ostatecznie:
\(\displaystyle{ n(A\cup B\cup C) = 333 + 200 - 66 + 142 - 47 - 28 - 9 = 525}\), skad szukana liczba to 1000-525 = 475.

O ile nie pomylilem sie nigdzie po drodze ;)
EDIT -> napisalo mi sie n(B) zamiast n(C), juz poprawilem.
Ostatnio zmieniony 9 wrz 2006, o 00:49 przez liu, łącznie zmieniany 1 raz.
Awatar użytkownika
Tristan
Użytkownik
Użytkownik
Posty: 2353
Rejestracja: 24 kwie 2005, o 14:28
Płeć: Mężczyzna
Podziękował: 27 razy
Pomógł: 557 razy

podzielność - ile jest liczb niepodzielnych przez 3,5,7

Post autor: Tristan »

Aby zobrazować sytuację, zastanówmy się ile jest takich liczb pomiędzy 1 a 30. 30:3 jest 10, 30:5 jest 6 oraz 30:7 jest 3, można więc wnioskować, że liczb niepodzielnych przez 30 jest 30-(10+6+3)=30-19=11. Jednak łatwo policzyć, że liczb tych jest w rzeczywistości 13. Gdzie zgubiły nam się dwie liczby? Otóż pomiędzy 1 a 30 występują dwie liczby podzielne przez 3 i 5 tj. 15 i 30, więc możemy policzyć je tylko raz, a myśmy zrobili to podwójnie.
Dlatego też liczb pomiędzy 1 a 1000 niepodzielnych przez 3,5 i 7 jest 1000-(333+200+142)+(66+47+28+9)=475.
Schadoow
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 19 lis 2013, o 20:08
Płeć: Mężczyzna
Lokalizacja: Wrocław

podzielność - ile jest liczb niepodzielnych przez 3,5,7

Post autor: Schadoow »

Wiem, że mega odkop ale wynik jest błędny.
Zamiast\(\displaystyle{ -(A\cup B\cup C)}\) powinno być \(\displaystyle{ +(A\cup B\cup C)}\)
Policzone na "pieszo" wynik 457 a nie 475
liu
Użytkownik
Użytkownik
Posty: 1330
Rejestracja: 10 paź 2004, o 13:30
Płeć: Mężczyzna
Lokalizacja: Suchedniów
Pomógł: 104 razy

podzielność - ile jest liczb niepodzielnych przez 3,5,7

Post autor: liu »

Tak, pomyliłem znak 10 lat temu. Dziękuję:)
Baleron2
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 25 maja 2015, o 19:18
Płeć: Mężczyzna
Lokalizacja: Pomorskie
Podziękował: 17 razy

podzielność - ile jest liczb niepodzielnych przez 3,5,7

Post autor: Baleron2 »

A może ktoś wytłumaczyć dlaczego powinno być \(\displaystyle{ +(A\cap B\cap C)}\)?
Dlaczego nie odejmujemy powtórzeń?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

podzielność - ile jest liczb niepodzielnych przez 3,5,7

Post autor: Premislav »

Ależ odejmujemy powtórzenia, tylko że odejmując
\(\displaystyle{ n(A \cap B), n(A \cap C)}\) oraz \(\displaystyle{ n( B\cap C)}\), niektóre z nich odjęliśmy dwa razy (konkretnie te, które są elementami zarówno \(\displaystyle{ A \cap B}\), jak i \(\displaystyle{ A \cap C}\), etc. a więc elementami \(\displaystyle{ A\cap B \cap C}\)), więc potem musimy dodać.
ODPOWIEDZ