MatDys 2008 3

MatDys 2008 3, studia, matematyka dyskretna

[ Pobierz całość w formacie PDF ]
MatematykaDyskretna3/2008
1.
(a) Udowodni¢, »e je±li w trójk¡cie równobocznym o boku długo±ci4jednostek umie±cimy17
punktów, to odległo±¢ dwóch spo±ród nich nie przekracza1jednostki.
(b) W sze±cianieS, którego kraw¦d¹ ma długo±¢7wybrano342punkty. Czy mo»na znale¹¢ taki
sze±cian o boku1zawarty w sze±cianieS, który nie zawiera »adnego z tych342punktów?
(c) Udowodni¢, »e w±ród dowolnie wybranych dwudziestu jeden punktów le»¡cych w kwadracie o
boku1istniej¡3, które le»¡ w pewnym kole o promieniu
1
7
:
(d) Udowodni¢, »e w±ród sze±ciu punktów umieszczo
n
ych w prostok¡cie o wymiarach34zawsze
mo»na znale¹¢ dwa, których odległo±¢ nie przekracza
5:
2.
Danych jest dziesi¦¢ odcinków, których długo±ci s¡ wi¦ksze od1cm i mniejsze od55cm.
Udowodni¢, »e w±ród nich istniej¡ trzy odcinki, z których mo»na zbudowa¢ trójk¡t.
3.
NiechSb¦dzie zbiorem25punktów, takim, »e w ka»dym3-elementowym podzbiorze istniej¡
dwa punkty, których odległo±¢ nie przekracza1. Udowodni¢, »e istnieje13-elementowy podzbiór zbioru
S, który mo»na przykry¢ kołem o promieniu1:
4.
W turnieju szachowym uczestniczy66zawodników. Ka»dy z ka»dym rozgrywa jedn¡ par-
ti¦. Rozgrywki odbywaj¡ si¦ w czterech miastach. Udowodni¢, »e pewna trójka zawodników rozegra
wszystkie partie mi¦dzy sob¡ w jednym mie±cie.
5.
Czy mo»na znale¹¢ tak¡ pot¦g¦ liczby3, która ko«czyłaby si¦ cyframi0001(w zapisie dziesi¦t-
nym)?
6.
(a) Ile jest wszystkich liczb trzycyfrowych (w układzie dziesi¦tnym), których co najmniej jedna
z cyfr równa si¦3lub7lub9?
(b) Ile liczb trzycyfrowych (w układzie dziesi¦tnym) ma co najmniej jedn¡ z cyfr równ¡ 3 i co
najmniej jedn¡ z cyfr równ¡7?
7.
Wyznaczy¢ liczb¦ wszystkich liczb naturalnychn;1n2:000;które:
(a) nie s¡ podzielne przez »adn¡ z liczb2;3;5;
(b) nie s¡ podzielne przez »adn¡ z liczb2;3;5;7;
(c) nie s¡ podzielne przez »adn¡ z liczb2;3;5ale s¡ podzielne przez7.
8.
Wyznaczy¢ liczb¦ wszystkich całkowitych nieujemnych rozwi¡za O równaniax
1
+x
2
+x
3
+x
4
=
21;dla których:
(a)0x
i
dla1i4; (b)0x
i
<8dla1i4;
(c) 5x
i
10dla1i4; (d)0x
1
5;0x
2
6;3x
3
7;3x
4
8
9.
Funkcj¡ Eulera nazywamy funkcj¦':
N
!
N
okre±lon¡ wzorem
'(n)=jfm2(N):1
6
m
6
n1;NWD(m;n)=1gj;
innymi słowy'(n)– to ilo±¢ liczb naturalnych mniejszych odn, które s¡ znwzgl¦dnie pierwsze, np.
'(2)=1;'(3)='(4)='(6)=2;'(5)='(8)='(10)='(12)=4:Obliczy¢:
(a)'(n)dlan2f51;420;12:300g;
(b)'(2
n
)oraz'(2
n
p)gdziepjest nieparzyst¡ liczb¡ pierwsz¡.
10.
Jakich funkcji jest wi¦cej, czy ze zbioru5-elementowego na3-elementowy, czy te» ze zbioru
6-elementowego na2-elementowy?
11.
a) Ile jest wszystkich funkcji rosn¡cych ze zbioru f1;2;:::;ng w zbiór f1;2;:::;mg?
b) Ile jest wszystkich funkcji niemalej¡cych ze zbioru f1;2;:::;ng w zbiór f1;2;:::;mg?
p
12.
Udowodni¢, »e je±likins¡ liczbami naturalnymi, to
n
0
n
1
(n1)
k
+
n
2
(n2)
k
++(1)
n
1
n
n1
1
k
=
(
0 dlak<n;
n! dlak=n
(1)
Przygotował: C. Bagi«ski
n
k
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl