Nazwisko:.................................. Indeks:.................

Nr testu: 37-001

Kod testu

x

Formularz testu

Kurs: Matematyka Dyskretna
Test: Egzamin sesyjny
Termin: 2011-02-02
Sala: 0004,0089
Seria: 208:2011-02-02:202

***** Nim rozpoczniesz, przepisz numer testu
***** i kod testu na formularz odpowiedzi

1. Dane jest równanie rekurencyjne u

n+2

− 6u

n+1

+ 9u

n

= 0.

Wskaż zdania prawdziwe
A) Wielomian charakterystyczny ma dwa różne pierwiastki.
B) Jeżeli u

0

= 1, u

1

= 0, to funkcja tworząca ma wzór

6x−1

(1−3x)

2

.

C) Jeżeli u

0

= 1, u

1

= 0, to funkcja tworząca ma wzór

1−6x

(1−3x)

2

.

D) Rozwiązanie ogólne jest postaci u

n

= A · 3

n

, A ∈ R.

E) Każde rozwiąznie tego równania jest też rozwiązaniem rów-
nania u

n+3

− 5u

n+2

+ 3u

n+1

+ 9u

n

= 0.

2. Niech t, v, k, r, r

t

∈ N. Wskaż stwierdzenia prawdziwe.

A) Jeśli t-konfiguracja o parametrach (v, k, r

t

) istnieje, to

∀s = 1, ..., t − 1 (k − s)...(k − t + 1) | r

t

(v − s)...(v − t + 1).

B) Jeśli ∀s = 1, ..., t−1 (k−s)...(k−t+1) | r

t

(v−s)...(v−t+1),

to istnieje t-konfiguracja o parametrach (v, k, r

t

).

C) Jeśli k | vr, to istnieje konfiguracja o parametrach (v, k, r).
D) t-konfiguracja o parametrach (v, k, r

t

) istnieje wtw gdy

∀s = 1, ..., t − 1 (k − s)...(k − t + 1) | r

t

(v − s)...(v − t + 1).

E) Konfiguracja o parametrach (v, k, r) istnieje wtw gdy k | vr
i

vr

k

¬

v
k

.

3. Zaznacz odpowiedzi prawdziwe dla każdego grafu dwu-

dzielnego G = (X ∪ Y, E).
A) Dla każdych zbiorów A ⊂ X i B ⊂ Y jeśli istnieją przydzia-
ły M

A

i M

B

zawierające wszystkie wierzchołki odpowiednio ze

zbioru A i B, to istnieje przydział M zawierający wszystkie
wierzchołki ze zbioru A ∪ B.
B) Przydział M jest przydziałem zupełnym w G wtw, gdy nie
istnieje ścieżka alternująca względem M .
C) Jeśli istnieje k ∈ N takie, że graf G jest k-regularny, to w
G istnieje przydział zupełny.
D) Jeśli M jest przydziałem maksymalnym w G, to

#M = #J (X).

E) Jeśli istnieje k ∈ N takie, że graf G jest k-regularny, to w G
istnieje k rozłącznych przydziałów, których suma równa się E.

4. Niech G = (V, E) będzie grafem, w którym V = {1, . . . , n},

n ­ 8 oraz ij ∈ E ⇔ |i−j| ­ 3. Zaznacz odpowiedzi prawdziwe
dla każdego takiego grafu:
A) |E| <

n−2

2

,

B) G zawiera K

5

jako podgraf,

C) G ma cykl Hamiltona,
D) G nie jest planarny,
E) dopełnienie ¯

G grafu G ma własność χ( ¯

G) = 3,

5. A(x) jest funkcją generującą ciągu {a

n

}

n∈N

0

,

B(x) = A(0) + A(x

2

) + x

2

A(x)

jest funkcją generującą ciągu {b

n

}

n∈N

0

. Wskaż odpowiedzi praw-

dziwe dla wszystkich takich ciągów {a

n

}

n∈N

0

.

A) b

2n

= a

2n

+ a

2n−2

dla n ­ 1

B) b

2n+1

= a

2n−1

dla n ­ 1

C) b

1

= 0

D) b

2n

= a

n

+ a

2n−2

dla n ­ 1

E) b

0

= a

0

6. Rozważmy grupę dihedralną D

2·13

symetrii 13-kąta fo-

remnego. Wskaż stwierdzenia prawdziwe.
A) Liczba różnych 13-kątów o k wierzchołkach białych i l czar-
nych, to współczynnik przy a

k

b

l

w

1

26

[(a

13

+ b

13

) + 12(a + b)

13

+ 13(a + b)(a

6

+ b

6

)

2

].

B) Jeśli 7 wierzchołków pomalujemy na biało i 6 na czarno, to
otrzymamy

13

7

+ 13

6
3

różnych wielokątów.

C) Liczba różnych 13-kątów pokolorowanych 2 kolorami wyno-
si ξ

D

2·13

(2, . . . , 2).

D) Jeśli 11 wierzchołków pomalujemy na biało i 2 na czarno,
to otrzymamy 6 różnych wielokątów.
E) ξ

D

2·13

(x

1

, . . . , x

13

) =

1

26

(x

13

1

+ 12x

13

+ 13x

1

x

6

2

).

7. Zaznacz poprawne odpowiedzi:

A) dowolny graf spójny o n ­ 1 wierzchołkach ma co najmniej
n − 1 krawędzi,
B) w grafie niespójnym o n wierzchołkach takim, że dla każ-
dego wierzchołka v ∈ V d(v) > 0 może być dokładnie

n−1

2

krawędzi,
C) istnieje drzewo o parzystej liczbie krawędzi, w którym wszyst-
kie wierzchołki mają nieparzysty stopień,
D) dowolny graf o 2n wierzchołkach nie zawierający 3-klik ma
co najwyżej n

2

krawędzi,

E) dowolne drzewo o n ­ 2 wierzchołkach ma co najmniej 2
wierzchołki stopnia 1,

8. Niech ϕ będzie funkcją Eulera, m, n, p ∈ N, a p niech bę-

dzie liczbą pierwszą. Zaznacz odpowiedzi prawdziwe dla wszy-
skich takich m, n, p.
A) n =

P

d|n

ϕ(d), d ∈ N,

B) p | n

p+1

− n

2

,

C) ϕ(n

m

) = ϕ(n)

m

,

D) ∃x, y ∈ Z takie, że x

2

= y

2

(mod p) i x 6= ±y (mod p),

E) (p − 1)! = −1 (mod p),

9. Rozważamy graf G = (V, E), którego zbiorem wierzchoł-

ków jest V = {2, . . . , 1000}. Dla których zbiorów krawędzi graf
ten jest spójny?
A) xy ∈ E wtw, gdy |x − y| jest liczbą pierwszą,
B) xy ∈ E wtw, gdy x jest podzielne przez y lub y jest po-
dzielne przez x,
C) xy ∈ E wtw, gdy |x − y| jest równe 5 lub 7,
D) xy ∈ E wtw, gdy N W D(x, y) = 1,
E) xy ∈ E wtw, gdy x − y jest liczbą parzystą,

10. Rozważamy ciągi długości n ­ 1 o elementach ze zbioru

A = {a, b, c} × {d, e, f }. Zaznacz poprawne stwierdzenia:
A) wszystkich takich ciągów jest 9

n

,

B) wszystkich takich ciągów jest tyle samo, co ciągów
2n-elementowych o elementach ze zbioru B = {a, b, c, d, e, f },
C) wszystkich takich ciągów jest 6

n

,

D) wszystkich ciągów, w których para (a, e) występuje co naj-
mniej jeden raz jest 9

n

− 8

n

,

E) wszystkich ciągów, w których para (c, d) występuje co naj-
mniej jeden raz i para (c, f ) występuje co najmniej jeden raz

1

jest 9

n

− 8

n

+ 7

n

,

11. Funkcja generująca (1−x)

−2

określa pewien ciąg. Wskaż,

które z poniższych funkcji generujących określają ten sam ciąg.
A)

P

∞
n=0

n+1

n

x

n

B) x ·

P

∞
n=0

n+1

n

x

n

C) x · (

P

∞
n=0

x

n

)

0

D) (1 − x)

−1

(

P

∞
n=0

x

n

)

0

E) (

P

∞
n=0

x

n

)

0

12. Niech x ∈ N będzie najmniejszym rozwiązaniem układu

(

7x ≡ 17

(

mod 20)

4x ≡ 9

(

mod 15).

Zaznacz odpowiedzi prawdziwe.
A) x

30

≡ 2 ( mod 31)

B) x

442

≡ 16 ( mod 55)

C) x

2

≡ x

3

( mod 50)

D) 32|ϕ(x

5

)

E) Dla dowolnego y ∈ N, rozwiązania układu prawdziwa jest
równość y = x (mod 300)

13. Niech
F (x) =

1

1−x

2

1

1−x

4

Q

∞
i=1

1

1−x

2i−1

,

G(x) =

1

1−x

2

1

1−x

4

Q

∞
i=1

1

1−x

2i

,

H(x) =

1

1−x

2

1

1−x

4

Q

∞
i=1

(1 + x

i

).

Zaznacz odpowiedzi prawdziwe.
A) Dla k ∈ {1, 2, 3, 4, 5} współczynnik przy x

k

w F jest równy

współczynnikowi przy x

k

w

Q

∞
i=1

1

1−x

i

.

B) Istnieje nieparzyste n takie, że współczynnik przy x

n

w G

jest różny od zera.
C) F = H
D) Współczynnik przy x

n

w F jest równy liczbie podziałów n

na składniki równe 2 lub 4 lub będące liczbą nieparzystą.
E) F = G

14. Niech A

1

= {σ ∈ S

10

| σ(1) /

∈ {1, 2, 7}},

A

2

= {σ ∈ S

10

| σ(3) /

∈ {1, 3, 4}}, A

3

= {σ ∈ S

10

| σ(7) /

∈ {9}}

i niech A

i

= S

10

\ A

i

dla i = 1, 2, 3. Zaznacz odpowiedzi praw-

dziwe.
A) |A

1

∩ A

2

∩ A

3

| = 10! − 7 · 9! + 15 · 8! − 9 · 7!.

B) |A

1

∩ A

2

∩ A

3

| = 10! − 7 · 9! + 14 · 8! − 8 · 7!.

C) |A

1

∩ A

3

| = 3 · 7!,

D) |A

1

∩ A

2

| jest równe liczbie wszystkich 10-literowych słów

jakie można utworzyć z liter a, b, c, d, e, f, g, h, i, j tak, aby żad-
na litera się nie powtórzyła, na pierwszym miejscu nie może
być litery a, b, f , na trzecim miejscu nie może być litery a, c, d;
E) |A

1

∩ A

2

| = 8 · 8!,

15. Niech n > m ­ 2. n mężczyzn i m kobiet będzie jadło

kolację przy okrągłym stole. Zaznacz poprawne stwierdzenia.
A) Wszystkich możliwych rozsadzeń takich, że wszystkie ko-
biety siedzą obok siebie jest

n! m!
n+m

.

B) Wszystkich możliwych rozsadzeń tych ludzi przy stole jest
(n + m)!.
C) Wszystkich możliwych rozsadzeń takich, że wszyscy męż-
czyźni siedzą obok siebie jest tyle samo, co wszystkich możli-
wych rozsadzeń takich, że wszystkie kobiety siedzą obok siebie.

D) Wszystkich możliwych rozsadzeń takich, że dopóki to moż-
liwe sadzamy na przemian kobietę obok mężczyzny, a pozosta-

łych mężczyzn obok siebie jest

(

n

m

)

m!m!(n−m)!

n+m

.

E) Wszystkich możliwych rozsadzeń takich, że dopóki to moż-
liwe sadzamy na przemian kobietę obok mężczyzny, a pozosta-
łych mężczyzn obok siebie jest n! m!.

16. Dla jakich k, l ∈ N istnieje drzewo złożone z 2 wierz-

chołków stopnia 5, k wierzchołków stopnia 3, 2 wierzchołków
stopnia 2 i l wierzchołków stopnia 1?
A) dla k, l ∈ N takich, że l = k + 9
B) dla k, l ∈ N takich, że l = k + 8
C) dla dowolnych k, l ∈ N
D) dla k = 21, l = 29
E) dla k = 21, l = 30

17. Sieć G = (V, E) jest dana następująco:

V = {1, 2, 3, 4, 6, 12}, (i, j) ∈ E ⇔ i dzieli j oraz c(i, j) = j/i,
1 jest źródłem, a 12 jest ujściem. Wskaż prawdziwe odpowiedzi.
A) dla pewnego przekroju (S, T ) w G jest c(S, T ) = 21,
B) w G istnieje przepływ maksymalny nie wykorzystujący kra-
wędzi (1, 2),
C) w G istnieje przepływ maksymalny wykorzystujący krawędź
(2, 4),
D) jeśli (S, T ) jest przekrojem minimalnym w G, to 1, 6 ∈ S,
E) dla pewnego przekroju (S, T ) w G jest c(S, T ) = 22,

18. Danych jest 250 liczb całkowitych a

1

, . . . , a

250

. Wskaż

największą liczbę m ∈ N, co do której można mieć pewność, że
istnieją dwie liczby a

i

, a

j

(i 6= j) takie, że m|(a

i

− a

j

).

A) 124,
B) 250
C) 249
D) 126
E) 125

19. Niech n, k ∈ N.

n+k−1

n

oznacza

A) liczbę całkowitych i nieujemnych rozwiązań równania

x

1

+ . . . + x

k

= n,

B) liczbę podziałów n na co najwyżej k składników,
C) liczbę możliwych sposobów umieszczenia n nierozróżnial-
nych kul w co najwyżej k rozróżnialnych szufladach,
D) liczbę możliwych sposobów umieszczenia n nierozróżnial-
nych kul w k rozróżnialnych szufladach, przy czym żadna szu-
flada nie jest pusta,
E) współczynnik przy x

n

w szeregu (1 − x)

−k

,

20. Niech G = {id, (1 2)(3 4 5), (1 2)(3 5 4), (3 4 5), (3 5 4), (1 2)}

będzie podgrupą grupy permutacji (S

6

, ◦). Zaznacz odpowiedzi

prawdziwe.
A) Stabilizator G

6

= G

B) ξ

G

=

1
6

(x

6

1

+ 2x

1

x

2

x

3

+ 2x

3

1

x

3

+ x

4

1

x

2

)

C) Orbita G3 = {3, 4, 5}
D) Stabilizator G

1

= {id}

E) Grupa G ma dwie orbity