7090996918

W. Guzicki: Zadania z kombinatoryki

Inaczej mówiąc, jeśli A = {ai,..., a_m} oraz |B_a, ] = ...= |B_am | = n, to zbiór {(01,6): 6 € B_a,} U ... U {(fl_m>6) : b € B_am}

ma m • n elementów.

Zasadę równoliczności można rozszerzyć w następujący sposób. Własności (Rl) i (R3) pozostawmy bez zmian. Własność (R2) zastąpmy natomiast własnością mówiącą, że każdy element zbioru A występuje w dokładnie k parach z k różnymi elementami zbioru B, gdzie k jest ustaloną liczbą naturalną. Wówczas ta uogólniona zasada równoliczności mówi że zachodzi równość: k ■ |A| = |B|. Oczywiście dla k = 1 otrzymujemy zwykłą zasadę równoliczności. W notacji teoriomnogościowej ta uogólniona postać zasady równoliczności oznacza, że jeśli istnieje funkcja

/ : B A

taka, że dla każdego a € A mamy |/^_1(a)| = k, to k ■ |A| = \B\.

Reguły dodawania i mnożenia można rozszerzyć na większą liczbę czynności. Dokładne sformułowania obu reguł w przypadku większej liczby czynności pozostawię jako ćwiczenie.

Z reguły dodawania wynika poprawność ważnego sposobu zliczania elementów zbioru. Przypuśćmy, że mamy dane dwa zbiory A i B takie, że AC B. Chcemy policzyć, ile elementów ma zbiór A. Jedna z metod polega na tym, by policzyć wszystkie elementy zbioru B, następnie policzyć te elementy zbioru B, które do zbioru A nie należą i wreszcie otrzymane liczby odjąć. Wzorami można to zapisać w postaci

|A| = |B|-|B\A|.

Z reguły dodawania wynika bowiem, że

|A| + |B\A| = |AU(B\jtJJ«|B|.

Mówiąc obrazowo, zliczamy wszystkie możliwe elementy (tzn. wszystkie elementy zbioru B), a następnie zliczamy, ile wśród nich jest elementów „złych”, to znaczy elementów nienależących do zbioru A. Wtedy od liczby wszystkich elementów odejmujemy liczbę elementów złych.

Ten sposób zliczania zastosujemy teraz do wyprowadzenia ważnego wniosku. Wykażemy mianowicie, że jeśli m < n, to

|{m, to+1, ...,n}| = n — m+1.

Niech bowiem A = {m, m + 1,..., n} oraz B = [n]. Wówczas B \ A = [m — 1], skąd wynika, że

|A| = \B\ — \B \ A\ = |[n]| - |[m — 1]| = n - (m — 1) = n — m+ 1.

Częsty błąd uczniów polega na tym, że piszą, iż \A\ = n — m.

3. Zasada równoliczności

W tym rozdziale pokażę kilka zadań ilustrujących zasadę równoliczności. Rozumowania prowadzące do rozwiązania niektórych z nich są czasem nazywane rozumowaniami „przez symetrię”. Powody dla takiej nazwy staną się — mam nadzieję — jasne po obejrzeniu tych rozwiązań.

A oto te zadania wraz z rozwiązaniami.

1. Ile jest liczb trzycyfrowych podzielnych przez 7? Ile jest liczb trzycyfrowych podzielnych przez 17? Ile liczb trzycyfrowych daje resztę 1 przy dzieleniu przez 7? Ile liczb trzycyfrowych daje resztę 6 przy dzieleniu przez 7? Ile liczb trzycyfrowych daje resztę 4 przy dzieleniu przez 7?

Rozwiązanie. W tym zadaniu uczniowie często popełniają typowe błędy. Pierwszy błąd polega na tym, że źle obliczają liczbę liczb trzycyfrowych: od 999 odejmują 100, otrzymując wynik 899. Ten błąd opisywałem wyżej. Następnie wykorzystują ten zły wynik w dalszych obliczeniach, często też błędnych. Co ciekawe, w niektórych zadaniach powyższej postaci uzyskują poprawny wynik, mimo popełnianych błędów. Popatrzmy na następny błąd. Uczniowie rozumują w następujący sposób: co siódma liczba jest

Warszawa, 19-20 października 2013 r.