7090996905

W. Guzicki: Zadania z kombinatoryki

Rozwiązanie. Postępujemy tak samo jak w zadaniu 10. Mamy dwa sposoby rozwiązania zadania. W sposobie pierwszym definiujemy pomocniczy zbiór B w następujący sposób:

•    zbiór B składa się z trójek (i,j) takich, żel<i<j<fc<n-|-2.

Wówczas trójkę (i, j, k) należącą do zbioru A łączymy w parę z trójką (i,j + 1, k + 2) należącą do zbioru B. Niech na przykład n = 8. Wówczas:

•    trójkę (2,4,6) łączymy w parę z trójką (2,5,8),

•    trójkę (5,5,7) łączymy w parę z trójką (5,6,9),

•    trójkę (5,5,5) łączymy w parę z trójką (5,6,7),

•    trójkę (1,3,8) łączymy w parę z trójką (1,4,10).

Sprawdzenie, że ten sposób łączenia w pary trójek należących do zbiorów A i B spełna warunki (R.1), (R2) i (R3), pozostawię jako ćwiczenie. Zatem |j4| = \B\. To, że \B\ = |ć>3(n + 2)|, wynika z zadania 8. W drugim sposobie rozwiązania znów piszemy n — 1 zer i numerujemy liczbami od 1 do n miejsca rozdzielone tymi zerami. Następnie, trójkę (i,j, k) łączymy w parę z ciągiem zerojedynkowym, w którym oprócz wypisanych n — 1 zer mamy 3 jedynki wpisane w miejscach o numerach i, j i k. Oczywiście, jeśli któreś liczby w rozważanej trójce są równe, to w miejsce o tym numerze wpisujemy obok siebie odpowiednią liczbę jedynek. Popatrzmy znów na przykład. Niech nadal n = 8. Znów mamy 7 zer i 8 ponumerowanych miejsc. Wówczas:

•    trójkę (2,3,8) łączymy z ciągiem 0101000001,

•    trójkę (3,3,5) łączymy z ciągiem 0011001000,

•    trójkę (6,6,6) łączymy z ciągiem 0000011100.

Sprawdzenie, że taki sposób łączenia w pary spełnia warunki (Rl), (R2) i (R3), pozostawię jako ćwiczenie. Zatem |A| = |S2(n+ 1)|.

12. Dane są dwie liczby naturalne k i n takie, że k,n> 1. Definiujemy następujące dwa zbiory ciągów:

•    zbiór A składa się z ciągów (ai,..., a*) takich, że 1 < ai < ... < a* < n,

•    zbiór B składa się z ciągów (6j,..., bk) takich, że 1 < &i < ... < bk < n + k — 1.

Udowodnij, że |^4| = |B|.

Rozwiązanie. Weźmy ciąg (aj,...,a*,) taki, że 1 < ai < ... < a* < n. Łączymy go w parę z ciągiem (&i,... ,bk) zdefiniowanym w następujący sposób:

bi = Oi,

i>2 ⁼ 02 + 1>

&3 = 03 + 2, bk = ot + k - 1.

Nietrudno sprawdzić, że wtedy 1 <&i < ... < bk <n + k— 1. Zatem ciąg (61,..., bk) należy do zbioru B. Popatrzmy na kilka przykładów. Niech k = 4 i n = 7. Wówczas:

•    ciąg (1,2,2,4) łączymy w parę z ciągiem (1,3,4,7),

•    ciąg (2,5,7,7) łączymy w parę z ciągiem (2,6,9,10),

•    ciąg (7,7,7,7) łączymy w parę z ciągiem (7,8,9,10).

Oczywiście możliwe jest, by A; > n. Niech na przykład n = 5 oraz k = 7. Wówczas:

•    ciąg (1,1,1,1,1,1,1) łączymy w parę z ciągiem (1,2,3,4,5,6,7),

•    ciąg (2,2,2,2,3,4,5) łączymy w parę z ciągiem (2,3,4,5,7,9,11),

•    ciąg (1,1,1,3,5,5,5) łączymy w parę z ciągiem (1,2,3,6,9,10,11).

Sprawdzenie, że każdy ciąg ze zbiorów A i B znajduje się w dokładnie jednej parze, a więc spełnione są warunki (Rl), (R2) i (R3), jest bardzo łatwe i zostawię to jako ćwiczenie. Zatem \A\ = \B\.

13. Dane są liczby naturalne k i n takie, że k,n> 1. Definiujemy zbiór A w następujący sposób:

• zbiór A składa się z ciągów (ai,..., o*,) takich, że 1 < 01 < ... < a*, < n.

Udowodnij, że wówczas |.A| = \Sk(n + k — 1) |.

Warszawa, 19-20 października 2013 r.