Rozw MD4 2008, studia, matematyka dyskretna

[ Pobierz całość w formacie PDF ]
Cz.Bagi«ski–Materiałydydaktyczne
MatematykaDyskretna4/2008
1.
Ile jest liczb naturalnych mniejszych od10
n
;w których zapisie dziesi¦tnym obok siebie nie
wyst¦puj¡ dwie jednakowe cyfry.
2.
Udowodni¢, »e dla ka»dej liczby naturalnejnzachodzi równo±¢
2
n
n
0
+2
n1
n+1
1
+2
n2
n+2
2
++
2n
n
=2
2n
:
Rozwi¡zanie.
Dlan=1suma po lewej stronie jest równa stronie prawej. Rzeczywi±cie
2
1
1
0
+2
0
2
1
=21+12=4=2
21
:
Załó»my teraz, »e wzór jest prawdziwy dla pewnegok,k
>
1;tzn. zakładamy, »e
2
k
k
0
+2
k1
k+1
1
+2
k2
k+2
2
++2
2k1
k1
+
2k
k
=2
2k
: (1)
Na podstawie tego zało»enia udowodnimy jego prawdziwo±¢ dlak+1, tzn. udowodnimy, »e
2
k+1
k+1
+2
k
k+2
1
+2
k1
k+3
2
++2
2
2k
k1
+2
2k+1
k
+
2k+2
k+1
=2
2(k+1)
: (2)
Dla dowodu wykorzystamy dobrze znan¡ własno±¢ symbolu Newtona:
n
m
=
n1
m1
+
n1
m
(3)
Otrzymujemy z niej, »e
k+1
0
=
k
0
;
k+2
1
=
k+1
+
k+1
;
0
1
k+3
2
=
k+2
+
k+2
;
1
2
2k
k1
=
2k1
k2
+
2k1
k1
;
2k+1
k
=
2k
+
2k
k
;
2k+2
k+1
=
2k+1
k1
+
2k+1
:
k
k+1
Wstawmy teraz prawe strony tych równo±ci w odpowiednie miejsca wyra»enia po lewej stronie
równo±ci (2) i zapiszmy j¡ (t¦ lew¡ stron¦, któr¡ oznaczymy symbolemL) w dwóch wierszach.
Mamy
+2
k1
k+2
++2
2
2k1
+2
2k
k
+
+2
k
k+1
1
+2
k1
k+2
2
++2
2
2k1
k1
+2
2k
+
2k+2
:
(4)
0
1
k2
k1
k+1
Zauwa»my teraz, »e ostatni składnik sumy z drugiego wiersza spełnia zale»no±¢
2k+2
k+1
=
2k+1
k
+
1
2
2k+2
k+1
Zast¡pmy teraz ten składnik praw¡ stron¡ ostatniej równo±ci, a nast¦pnie w pierwszym wierszu
wyra»enia (4) wył¡czmy przed nawias2, w drugim za± wył¡czmy przed nawias
1
2
. Otrzymujemy
L=2(2
k
k
0
+2
k1
k+1
+
1
2
2
k+1
k+1
1
+2
k2
k+2
2
++2
2k1
k1
+
2k
k
)+
:
+2
k
k+2
++2
3
2k1
+2
2
2k
+2
2k+1
+
2k+2
0
1
k2
k1
k
k+1
1
0
L=2
k+1
k
0
+2
k
k+1
Cz.Bagi«ski–Materiałydydaktyczne
W pierwszym nawiasie mamy lew¡ stron¦ równo±ci (1), w drugim – lew¡ stron¦ równo±ci (2).
Korzystaj¡c z zało»enia indukcyjnego otrzymujemy wi¦c
L=22
2k
+
1
2
L:
St¡dL=42
2k
=2
2k+2
=2
2(k+1)
, a to wła±nie chcieli±my udowodni¢. Na mocy zasady indukcji
matematycznej wzór jest prawdziwy dla dowolnej liczby naturalnejn:
3.
Udowodni¢, »e wszystkie podzbiory zbioru sko«czonego mo»na ustawi¢ w ci¡g, którego
kolejne wyrazy ró»ni¡ si¦ jednym elementem.
4.
NiechZbedzie zbioremn-elementowym. Znale¹¢ liczb¦ takich par zbiorów(A;B);»eAB
iBZ. Przyjmujemy, »e ka»dy zbiór zawiera siebie i zbiór pusty.
5.
Na ile sposobów mo»na wybra¢6kart z talii52kart tak, aby w±ród nich były karty wszystkich
czterech kolorów.
6.
Wyznaczy¢ liczb¦ takich podzbiorów zbioru f1;2;:::;ng;które nie zawieraj¡ dwóch kolej-
nych liczb.
Rozwi¡zanie.
Przeza
n
oznaczymy liczb¦ takich podzbiorów. Na pocz¡tek policzymy warto±ci
a
n
dla małychn. W poni»szej tabelce podane s¡ wszystkie podzbiory spełniaj¡ce warunki zadania
dlan=1;2;3;4;5.
n Zbiór Podzbiory a
n
1 f1g ;;f1g 2
2 f1;2g ;;f1g;f2g 3
3 f1;2;3g ;;f1g;f2g;
f3g;f1;3g 5
4 f1;2;3;4g ;;f1g;f2g;f3g;f1;3g
f4g;f1;4g;f2;4g 8
5 f1;2;3;4;5g ;;f1g;f2g;f3g;f1;3g;f4g;f1;4g;f2;4g
f5g;f1;5g;f2;5g;f3;5g;f1;3;5g 13
Pocz¡tkowe warto±ci ci¡gua
n
sugeruj¡ zwi¡zek z liczbami Fibonacciego deﬁniowanego wzorami
F
0
=0;F
1
=1;F
n
=F
n1
+F
n2
dlan
>
2. Sposób wypisania podzbiorów, natomiast, sugeruje
zale»no±¢ rekurencyjn¡. Je±li ju» mamy wypisane wszystkie podzbiory dla warto±ci mniejszych
odn, to w celu wypisania wszystkich podzbiorów dlan, najpierw wypiszmy wszystkie, które nie
zawieraj¡n– s¡ to wszystkie podzbiory, które spełniaj¡ warunki zadania i s¡ zawarte w zbiorze
f1;2;:::;n1g, a zatem jest icha
n1
. Pozostałe zawieraj¡n, a wi¦c nie mog¡ zawiera¢n1. Wobec
tego nale»y wzi¡¢ wszystkie podzbiory zbioru f1;2;:::;n2g, które spełniaj¡ warunki zadania i
dopisa¢ do ka»dego z nich liczb¦n. Ich ilo±¢ jest równaa
n2
. Razem mamy wi¦ca
n
=a
n1
+a
n2
podzbiorów. Nietrudno teraz zauwa»y¢, »ea
n
=F
n+1
dla wszystkichn
>
1.
7.
Dana jest liczba naturalnan: Wyznaczy¢ liczb¦ wszystkich uporz¡dkowanych czwórek
(a;b;c;d)takich, »e(1abcdn):
Rozwi¡zanie.
Oznaczmy przezx
1
liczb¦ jedynek wyst¦puj¡cych w tym ci¡gu, przezx
2
– liczb¦
dwójek, itd., przezx
n
– ilo±¢ liczb równychnw tym ci¡gu. Ci¡g ma cztery wyrazy wi¦c
x
1
+x
2
++x
n
=4
2
Cz.Bagi«ski–Materiałydydaktyczne
i oczywi±cie ilo±¢ wyst¡pie« ka»dej liczby jest
>
0, tzn.x
i
>
0dlai=1;2;:::;n. Jak wiadomo,
liczba całkowitych nieujemnych rozwi¡za« równania postaci
x
1
+x
2
+:::+x
n
=k
jest równa
n+k1
n1
=
n+3
4
. Zatem liczba uporz¡dkowanych czwórek, o które chodzi w tre±ci zadania jest
.
r+1
:
9.
Ile liczb naturalnych mniejszych od10
n
ma zapis dziesi¦tny, którego cyfry tworz¡ ci¡g
niemalej¡cy.
10.
NiechX=f1;2;:::;ng:Je»eliAjest podzbiorem zbioruX, to przezs(A)oznaczymy sum¦
wszystkich liczb nale»¡cych do zbioruA. Obliczy¢ sum¦
P
AX
s(A):
11.
Na okr¦gu danych jestnpunktów. Od ka»dego z tych punktów do ka»dego poprowadzono
ci¦ciw¦. Zakładaj¡c, »e »adne trzy ci¦ciwy nie maj¡ punktów wspólnych we wn¦trzu okr¦gu obliczy¢
liczb¦ punktów przeci¦cia tych ci¦ciw.
12.
Notacja
P
k
6
n
n
k
2
kn
jest niejasna bez znajomo±ci kontekstu. Oblicz t¦ sum¦: a) jako
sum¦ wzgl¦demk; b) jako sum¦ wzgl¦demn.
Przygotował: Cz. Bagi«ski
3
równa
n+3
n1
8.
Dane s¡ liczby naturalnenir;1rn:Rozwa»my wszystkie podzbiory zbioru f1;2;:::;ng
zło»one zrelementów. W ka»dym z tych podzbiorów wybieramy liczb¦ najmniejsz¡. Udowodni¢,
»e ±rednia arytmetyczna tych liczb jest równa
n+1
[ Pobierz całość w formacie PDF ]

Rozw MD4 2008, studia, matematyka dyskretna

Tematy