Rozwiązania zadań z (jednej z grup) egzaminu z Podstaw
Matematyki z 21 czerwca 2007.
1. Które z podanych niżej zdań są warunkami dostatecznymi,
a które wystarczającymi do prawdziwości zdania ∃
x
∈
− x
2
≥ a 1
a) a ≤ 0
b) a −1
c) a 0
d) a ≤ −1
e)
| a |
≥ 1
Odpowiedź:
Konieczne są a, c, d, e
Dostateczne są: b, d.
Jak to rozwiązać? Wystarczy się zastanowić, co to znaczy
„konieczny” i "dostateczny" („wystarczający”). Jeżeli z alfa
wynika beta, to alfa jest wystarczający dla beta. Bo przecież
wystarczy, żeby zaszło alfa, żeby beta też się zdarzyło. Z tego, że
deszcz pada, wynika, że ulice sa mokre. A więc wystarczy, żeby
trochę popadało i już jest mokro. Przeciwnie, beta jest konieczny
dla alfa. Na przykład, z tego, że pada deszcz, wynika, ze ulice są
mokre. Jeżeli zobaczymy, suchą ulicę, to znaczy, że deszcz nie
pada. Ulice muszą być moker po deszczu.
Nstępnie, trzeba oswoić podany warunek z kwantyfikatorem.
Co znaczy podany warunek: istnieje iks o tej własności, że liczba
przeciwna do jego kwadratu spełnia coś tam? Otóż przecież
„liczbą przeciwną do kwadratu” może być każda liczba ujemna (i
zero) i odwrotnie, każda liczba ujemna (także i zero) jest liczbą
przeciwną do pewnego kwadratu. Na przykład -2008 jest liczbą
przeciwną do kwadratu liczby 2008 . A zatem zdanie
zamieszczone znaczy ni mniej ni więcej tylko: a 1 jest liczbą
ujemną (bądź zerem). Co wystarcza, by a 1 ≤ 0? Oczywiście jest
to to samo, co a ≤ −1. Zatem ten warunek jest i konieczny i
dostateczny. Warunek a) jest oczywiście za słaby, bo −
1
2
≤ 0, ale
nie jest ≤ −1. Podobnie z c) . Warunek b) wystarcza, ale nie jest
konieczny. Wreszcie, jeżeli liczba jest mniejsza od −1, to jej
moduł (wartość bezwzględna) jest większy od 1, ale nie na
odwrót.
2. Funkcja f : → jest dana wzorem
f
x
1
dla x 3
1
− x
2
gdy -3 ≤ x 3
3
dla x ≥ 3
.
a) Wyznaczyć obraz przedziału otwartego (1; 6). Odpowiedź:
(-8;0) 3 ;
b) wyznaczyć przeciwobraz przedziału domkniętego −3; 2 .
Odp. [-2; 2] .
c) wyznaczyć zbiór wartości funkcji f . Odpowiedź:
−8; 1 3
-5
-4
-3
-2
-1
1
2
3
4
5
-8
-6
-4
-2
2
x
y
3. Niech A 1, 2, 3, 4, 5, 6. W iloczynie kartezjańskim A A
wprowadzamy relację R wzorem a, b R c, d
max
a, b maxc, d.
a) Wyznaczyć klasę abstrakcji (klasę równoważności) pary
(3,4).
b) Ile elementów ma zbiór ilorazowy A A /R ?
c) Ile elementów ma najliczniejsza klasa równoważności?
Jak można opisać tę relację, przyswoić ją sobie? Dwie pary
uznajemy za równoważne, jeżeli większe elementy tych par są
takie same. Przyjmijmy, że liczby to numery butów męża i żony -
no, numeracja damska jest inna, więc może się zdarzyć, że mąż
ma jedynkę a żona szóstkę, a w ogóle to przecież tylko dla
wyobrażenia sobie. Jest zatem sześć klas równoważności , zbiór
ilorazowy ma siedem elementów - odpowiadających numerom
butów.
Jakie małżeństwa są równoważne Kowalskim, gdzie żona ma
trójkę, a mąż czwórkę? Są to: Jankowscy (żona jedynkę, mąż
czwórkę), Nowakowie (żona 2, mąż 4), Stefańscy (ż 3, m 4),
Wiśniewscy (4,4), Zielińscy (żona czwórkę, mąż trójkę),
Pietrzakowie (4,2) i Ząbkowscy (żona czwórkę, mąż jedyneczkę).
A więc w klasie równoważności (3,4) jest łącznie 7 par: (1,4),
(2,4), (3,4), (4,4), (4,3), (4,2), (4,1). Najliczniejsza klasa to
oczywiście (1,6), (2,6), (3,6), (4,6), (5,6), (6,6), (6,5), (6,4), (6,3),
(6,2), (6,1).
4. Zbiór P1, . . . 100, czyli rodzinę wszystkich podzbiorów
zbioru liczb naturalnych 1, 2, 3, ..., 99,100 porządkujemy
indukcyjnie.
a) podać najbliższy zbiór dwuelementowy, który występuje po
{1,7,13}.
b) ile podzbiorów o trzech elementach znajduje się przed
{1,3,10,12}?
Rozwiązanie. Zanalizujmy jeszcze raz porządek indukcyjny.
Zamiast {a,b,c} będę pisać abc, żeby było prościej:
, 1, 2, 12, 3, 13, 23, 123, 4, 14, 24, 124, 34, 134, 234, 1234,
5
,
15, 25, 125, 35, 135, 235, 1235, 45, 145, 245, 1245, 345, 1345, 2345, 12345
6
,
16, 26, 126, 36, 136, 236, 1236, 46, 146, 246, 1246, 346, 1346, 2346, 12346
56
,
156, 256, 1256, 356, 1356, 2356, 12356, 456, 1456, 2456, 12456, 3456, 13456
W zrozumieniu, w czym rzecz, naprawdę pomaga takie
ćwiczenie: piszemy (np. w edytorze Word) kilka początkowych
wyrazów, np. , 1, 2, 12, następnie dopisujemy do wszystkich
trójkę na końcu. Kopiujemy otrzymanych osiem zbiorów i
wpisujemy każdemu czwórkę na końcu, i tak dalej.
Otrzymujemy szesnaście. I tak dalej.
Widzimy stąd, że porządek indukcyjny jest w istocie
porządkiem antyleksykograficznym:
klasyfikujemy według ostatnich elementów. Dlatego np.
1578
679, bo końcowa dziewiątka drugiej liczby jest większa od
końcowej ósemki pierwszej. Oczywiście w wypadku równych
ostatnich patrzymy na przedostatnie: 2356 456.
Ile zbiorów o trzech elementach poprzedza {1,3,10,12}. Są to
po pierwsze wszystkie zbiory w których największy element to
11. Jest ich
11
3
165. Poza nim są jeszcze te postaci a, b, 12,
gdzie a, b 1, 3, 10. Z tych zbiorów wybierzemy najpierw
a, b, 9 - jest ich
8
2
28, a nastepnie zbiory
a, b, 10, gdzie a, b 1, 3. Taki zbiór jest tylko
jeden :
1, 2, 10. Łącznie daje to 165 28 1 194 zbiory.
5. W zbiorze P1, . . . 10, czyli w rodzinie wszystkich
podzbiorów zbioru liczb naturalnych 1, 2, 3, ..., 10
rozpatrujemy porządek następujący: A poprzedza B , jeżeli ma
mniej elementów, a jeżeli obydwa zbiory mają tyle samo
elementów, to wcześniejszy jest ten, który jest wcześniejszy w
porządku leksykograficznym.
a) Wyznaczyć zbiór, znajdujący się na miejscu 82.
Najpierw mamy zbiór pusty, potem 10 zbiorów o jednym
elemencie, potem
10
2
45 zbiorów o dwóch elementach.
Łącznie 56. Nasz zbiór ma zatem trzy elementy. Jest aż
9
2
36
zbiorów 1, a, b, a więc nasz zbiór "zaczyna się" od 1. Ile jest
zbiorów 1, 2, ∗. Oczywiście 8. Ile jest zbiorów 1, 3, ∗?
Oczywiście 7. . Ile jest zbiorów 1, 4, ∗. Oczywiście 6. Ile jest
zbiorów 1, 5, ∗? Oczywiście 5. Ale 56 8 7 6 5 82. Nasz
zbiór jest ostatni z tych, które są postaci 1, 5, ∗, a więc 1, 5, 10
.
b) wyznaczyć numer miejsca, na którym znajduje się zbiór
{3,7,9}.
Liczymy: , dziesięć jednoelementowców, 45 zbiorów o 2
elementach,
9
2
36 zbiorów 1, a, b,
8
2
28 zbiorów postaci
2, a, b. Dalej, 6 zbiorów 3, 4, ∗, 5 zbiorów 3, 5, ∗, cztery zbiory
3, 6, ∗. To daje 1 10 45 36 28 6 5 4 135 Następnie jest
{3,7,8} i na 137 miejscu {3,7,9}.
6. W zbiorze liczb naturalnych {1,2,4,5, ....29,33} , złożonym z
liczb niepodzielnych przez 3 i mniejszych od 30 oraz dodatkowo
z liczby 33 określamy relację wzorem x y x y ∨ x ≤ y − 4.
a) Wyznaczyć elementy minimalne. Odp.: 1,2,4. Liczby 3 nie
ma w tym zbiorze. Liczba 4 jest minimalna, bo nieprawda, że
1
4 , ani, że 2 4 . Jest dopiero 1 5 .
b) Wyznaczyć elementy maksymalne. Odp.: 33. Jest to nawet
element największy.
c) Wyznaczyć element największy. Odp.:33. Istotnie, każda
inna liczba z tego zbioru różni się od 33 co najmniej o 4, zatem
jest „mniejsza” od 33 w sensie relacji .
d) Wyznaczyć element najmniejszy. Odp.:brak. Są bowiem
trzy elementy minimalne, nie porównywalne.
e) Podać przykład najdłuższego łańcucha. Przypominam, że
łańcuchem nazywamy podzbiór liniowo uporządkowany.
Przykładem najdłuższego łańcucha jest
1
5 9 13 17 21 25 29 33. Jest to jedyny łańcuch tej
długości, to jest 9.
f) Wyznaczyć kresy zbioru {5,6,7}. Odp. Kres dolny 1, górnego
nie ma. Jakie są bowiem ograniczenia dolne dla 5,6,7? Jest to
tylko liczba 1, tylko ona jest mniejsza od 5, 6 i 7. Z drugiej
strony, ograniczeniem górnym zbioru {5,6,7} jest każda liczba
równa co najmniej 11. Z tych liczb nie da sie wybrać
najmniejszej.
7. Dane są permutacje g
1 2 3 4 5 6 7 8 9
3 5 1 6 2 4 9 8 7
,
h
1 2 3 4 5 6 7 8 9
2 4 5 3 6 9 1 7 8
.
a) Obliczyć h
−1
.
Rozwiązanie: Odwracam tabelkę i ustawiam ją
po kolei:
........................
b) Przedstawić g jako złożenie rozłącznych cykli.
Odp.: 1 32 54 67 99 78. Wniosek g g
−1
.
c) Obliczyć g
−1
∘ h. Odp.:
1 2 3 4 5 6 7 8 8
5 6 2 1 4 7 3 8 8
.
d) określić znak permutacji h. Odp. Jest to permutacja
nieparzysta.
Inwersje tworzą pary (4,3), (4,1), (5,3), (5,1), (3,1), (6,1), (9,1),
(9,7), (9,8).