Tag: Zbiory

Narzędzia

Obiekty

Zbiory

Słowa kluczowe

Kategoria

Kombinatoryka

Zadanie ZM-1350
o zadaniu...

Publikacja w Delcie: maj 2012

Publikacja elektroniczna: 28-04-2012
Egzamin składa się z $\text{[math]}$ pytań ( $\text{[math]}$ ). Pewna liczba studentów przystąpiła do tego egzaminu. Wiadomo, że dla każdych dwóch studentów było przynajmniej jedno pytanie, na które obaj znali odpowiedź, ale dla żadnej pary studentów nie było tak, że obaj znali odpowiedzi na dokładnie te same pytania. Udowodnić, że do egzaminu przystąpiło co najwyżej $\text{[math]}$ studentów.

Rozwiązanie

Podzbiory $\text{[math]}$ zbioru $\text{[math]}$ łączymy w nieuporządkowane pary postaci $\text{[math]}$ Takich par jest $\text{[math]}$ Wobec założenia z treści zadania każdego studenta możemy utożsamiać jednoznacznie ze zbiorem pytań, na które zna odpowiedź. Gdyby studentów było więcej niż $\text{[math]}$ to znalazłoby się dwóch, którym odpowiadałyby zbiory $\text{[math]}$ i $\text{[math]}$ To jednak przeczyłoby założeniu, że na egzaminie było pytanie, na które obaj znali odpowiedź.
Narzędzia

Obiekty

Zbiory

Słowa kluczowe

Kategoria

Teoria Mnogości

Klub 44M - zadania II 2011»Zadanie 607
o zadaniu...

Zadanie pochodzi z artykułu Klub 44M - zadania II 2011

Publikacja w Delcie: luty 2011

Publikacja elektroniczna: 1 lutego 2011

Artykuł źródłowy w wersji do druku [application/pdf]: (206 KB)
Niech $X$ będzie zbiorem $n$ -elementowym ( $|n > 3$ ). Wyznaczyć największą liczbę $m$ , dla której w zbiorze $X |$ istnieje $m$ podzbiorów, z których żaden nie zawiera się w innym oraz żaden nie jest równoliczny z innym.

Rozwiązanie

Niech $|ℱ$ będzie rodziną $m$ podzbiorów zbioru $X |$ , spełniającą zadane warunki. Jeżeli do $ℱ$ należy zbiór pusty lub zbiór pełny (cały zbiór $|X$ ), to już żaden inny zbiór nie może do $ℱ$ należeć. W tym przypadku $|m .$

Jeżeli do $|ℱ$ należy pewien zbiór jednoelementowy $J$ oraz pewien zbiór $|(n− 1)$ -elementowy $|M$ , to muszą się one dopełniać (bo inaczej $|J⊂ M$ ) oraz żaden inny zbiór nie może do $|ℱ$ należeć (bo albo zawiera $|J$ , albo jest zawarty w $M$ ). W tym przypadku $m .$

Przyjmijmy dalej, że żadna z tych sytuacji nie ma miejsca. Wszystkie zbiory w $ℱ$ mają z założenia różne liczności. Wykluczone zostały liczności $|0,n$ oraz albo $1,$ albo $n −1$ . Pozostaje $|n− 2$ możliwych liczności. Zatem $|m .$

Pokażemy teraz, że dla każdego $n ⩾ 4$ istnieje w zbiorze $={1,...,n} |X$ rodzina $n − 2$ podzbiorów $ℱ = {A1,$ o wymaganych własnościach. Najpierw przykłady dla $n = 4$ , $|n = 5$ :

$pict$

Dalej indukcja ze skokiem o 2. Niech $|{A1,$ będzie "dobrą" rodziną podzbiorów zbioru $|{1,...,n}$ , ponumerowanych tak, że $| Ak$ dla $|k = 1,...,n− 2$ . Bierzemy zbiór $={1,...,n+2} X$ i określamy:
$Bk = Ak$

Widać, że $| Bk = k$ dla $|k = 1,...,n$ i że żaden ze zbiorów $Bk$ nie jest podzbiorem innego. Tak więc $| {B1,...,Bn}$ jest rodziną podzbiorów $| X$ , o jaką chodzi.

Dostajemy odpowiedź: dla każdej liczby $n ⩾ 4$ maksymalna liczność rodziny $|ℱ$ wynosi $|n −2$ .
Narzędzia

Obiekty

Liczby pierwsze , Zbiory

Słowa kluczowe

Kategoria

Teoria liczb

Zadanie ZM-1296
o zadaniu...

Publikacja w Delcie: Rocznik 2010 archiwum

Publikacja elektroniczna: 20-12-2010
Niech $\text{[math]}$ będzie liczbą pierwszą postaci $\text{[math]}$ . Dowieść, że zbioru złożonego z $\text{[math]}$ kolejnych liczb całkowitych nie da się podzielić na dwa podzbiory w taki sposób, aby iloczyn liczb w jednym podzbiorze był równy iloczynowi liczb w drugim podzbiorze.

Rozwiązanie

Jeśli wśród $\text{[math]}$ kolejnych liczb całkowitych jest liczba podzielna przez $\text{[math]}$ , to iloczyn liczb w jednym podzbiorze jest podzielny przez $\text{[math]}$ , a iloczyn w drugim nie jest podzielny przez $\text{[math]}$ . Możemy więc przyjąć, że wśród $\text{[math]}$ kolejnych liczb całkowitych nie ma liczby podzielnej przez $\text{[math]}$
Oznaczmy przez $\text{[math]}$ iloczyn liczb w jednym podzbiorze, a przez $\text{[math]}$ iloczyn liczb w drugim i przyjmijmy, że $\text{[math]}$ . Wówczas, na mocy twierdzenia Wilsona,
$display-math$
Ponieważ liczba $\text{[math]}$ jest nieparzysta, więc
$display-math$
Z drugiej strony, na mocy małego twierdzenia Fermata wiemy, że $\text{[math]}$ . Otrzymaliśmy sprzeczność, która dowodzi, że $\text{[math]}$
Narzędzia

Obiekty

Liczby naturalne , Zbiory

Słowa kluczowe

Kategoria

Teoria liczb

Zadanie ZM-K44-598
o zadaniu...

Publikacja w Delcie: marzec 2010

Publikacja elektroniczna: 6 lipca 2010
Niech $\text{[math]}$ , gdzie $\text{[math]}$ jest ustaloną liczbą naturalną.
(a)
Ile jest w zbiorze $\text{[math]}$ podzbiorów niezawierających pary liczb, których różnica dzieli się przez $\text{[math]}$ ?
(b)
Ile jest w zbiorze $\text{[math]}$ podzbiorów niezawierających pary liczb, których różnica jest równa $\text{[math]}$ ?

Zadanie zaproponował pan Paweł Kubit z Krakowa.
Narzędzia

Obiekty

Zbiory

Słowa kluczowe

Kategoria

Teoria Mnogości

Zadanie ZM-K44-581
o zadaniu...

Publikacja w Delcie: maj 2009

Publikacja elektroniczna: 18 czerwca 2010
Dany jest $\text{[math]}$ -elementowy zbiór $\text{[math]}$ $\text{[math]}$ oraz $\text{[math]}$ jego podzbiorów. Wykazać, że wśród tych podzbiorów istnieją takie cztery, których część wspólna jest zbiorem pustym lub jednoelementowym.