Zadanie

Dokonaj podziału zbioru 4 osób na pary w taki sposób, aby pary najlepiej pasowały do siebie wzrostem.

Przestrzeń stanów

O - zbiór osób

O = {1, 2, 3, 4}

Dla tego zadania stan jest podziałem zbioru osób na pary, gdzie możliwe są podziały:

P1 = {{1, 2}, {3, 4}}
P2 = {{1, 3}, {2, 4}}
P3 = {{1, 4}, {2, 3}}

Dla tego zadania przestrzeń stanów jest zbiorem wszystkich podziałów zbioru osób na pary.

U = {P1, P2, P3}
U ⊇ R

Dyskusja rozwiązań

W zależności od wzrostu osób możemy wyróżnić trzy różne przypadki.

jedno rozwiązanie     dwa rozwiązania     trzy rozwiązania

      |                     |             | | | |
    | |                 | | |             -------
  | | |               | | | |             \ / \ /
| | | |               -------
-------               \ / \ /             \ \/ /
\ / \ /                                    \/\/
                      \ \/ /
                       \/\/               \ \/ /
                                           \  /
                                            \/

Liczba podziałów

Niech zbiór osób O będzie zbiorem parzystym. Ile jest możliwych podziałów zbioru osób O na pary?

Z: #O = n, n = 2*k, k ∈ N \ {0}

T: #U = 1 * 3 * 5 * ... * (n-1)

#O - moc zbioru O
#U - moc zbioru U

Dowód tego twierdzenia przeprowadza się indukcyjnie.

Uwagi

Zadanie z podziałem zbioru osób na pary sprowadza się do problemu sortowania.