Twierdzenie o jednoznaczności
Twierdzenie w tej postaci nie byłoby łatwo udowodnić. Trudno jest mianowicie skonstruować łańcuch jednoznacznych decyzji w całej ogólności, abstrakcyjnie. Łatwiej jest zbadać przypadek przeciwny: gdy łańcuch jednoznacznych decyzji gdzieś się urywa.
Następujące twierdzenie jest równoważne z twierdzeniem, które mamy udowodnić: jeżeli łańcuch jednoznacznych decyzji gdziekolwiek się urywa, to zadanie nie może mieć jedynego rozwiązania *>. To udowodnimy.
Początkową część procedury, w której jeszcze można operować łańcuchem jednoznacznych decyzji, a więc tej, która trwa do pierwszego przerwania łańcucha jednoznacznych decyzji - pomijamy. Jeżeli mianowicie opuszczamy ,,rozwiązane już" rzędy i kolumny, a rozwiązanie pozostałego "zawężonego" zadania nie jest jednoznaczne, 10 oczywiście rozwiązanie pierwotnego zadania nie może być jednoznaczne. Wobec tego ograniczymy się do takich zadań, w których już na początku nie ma możliwości jednoznacznych decyzji.
Istnieją dwie następujące możliwości:
a) w którymś rzędzie lub kolumnie nie ma ani jednego białego pola,
b) w każdym rzędzie i w każdej kolumnie są co najmniej dwa białe pola.
Dwa twierdzenia nazywamy wtedy równoważnymi, gdy są jednocześnie albo prawdziwe, albo fałszywe: gdy pierwsze jest prawdziwe, to jest prawdziwe także drugie, oraz jeśli drugie jest prawdziwe, to jest prawdziwe pierwsze.
W przypadku a) zadanie jest oczywiście sprzeczne: nie ma ani jednego rozwiązania. Wtedy nie istnieje rozwiązanie jednoznaczne.
Pozostaje przypadek b). Wówczas też może się zdarzyć, że nie ma rozwiązania (porównaj rys. 20.1, 20.2,
22a, b).
Teraz jeszcze musimy wykazać, że jeżeli rozwiązanie
istnieje, to nie może ono być jedyne, czyli:
Jeżeli w każdym rządzie i w każdej kolumnie na rysunku jakiegoś zadania o powiązaniu elementarnym są przynajmniej dwa białe pola i zadanie ma jedno rozwiązanie, to ma ono także (co najmniej) jeszcze jedno rozwiązanie.
Co oznacza jednak "rozwiązanie"? Jeżeli zadanie szuka rozwiązania między elementami dwóch zbiorów o n elementach, czyli jeżeli tablica jest tablicą typu n X n, to oznacza to, że na wolnych polach tablicy jest n kółek połączeń rozmieszczonych w ten sposób, że dowolne dwa koła mieszczą się w różnych rzędach i różnych kolumnach. Dowodzone twierdzenie możemy więc sformułować również następująco:
Jeżeli w każdym rządzie i w każdej kolumnie tablicy typu n X n występują co najmniej dwa białe pola i w tablicy jest rozmieszczonych n kółek w taki sposób, że I. każde kółko stoi na jakimś polu, II. żadne kółko nie występuje z żadnym drugim kółkiem w tym samym rzędzie lub kolumnie,
to n kółek w tej samej tablicy można umieścić także inaczej, tak by warunek I i II nadal był spełniony.
Powyższe twierdzenie jest dokładnie tym samym twierdzeniem z zadania 24c. Różnica polega jedynie na tym, że tablicę nazwaliśmy tam "szachownicą", białe pole "wolnym" polem, a kółko "wieżą", drugi warunek wyraża zaś to, że żadne (kółko lub wieża) nie występuje razem z żadnym drugim w tym samym rzędnie lub kolumnie; wyraziliśmy to tam: "żadna wieża nie może bić drugiej". Twierdzenie z zadania 24c udowodniliśmy już, dlatego prawdziwe jest także obecne identyczne twierdzenie, a zatem także twierdzenie o jednoznaczności.
Uzupełnienie
Na podstawie udowodnionego teraz twierdzenia o jednoznaczności możemy już uczynić to, czego w rozwiązaniu zadania 14 jeszcze nie mogliśmy zrobić: możemy dokładniej określić zakres ważności obliczania redundancji, które zostało dokonane w zadaniu 10. W tym celu jednak warto najpierw w sposób bardziej ogólny i prosty sformułować uzyskany tam wynik.
Widzieliśmy, że - w przypadku zaistnienia odpowiednich warunków - dla zadania typu 6X6 wystarczy 1 + 2 + 3 + 4+5 wyłączeń elementarnych. Podobnym sposobem rozumowania dojdziemy do tego, że na przykład dla zadania typu 8X8 potrzeba 1 + 2 + 3 + 4 + 5 + + 6 + 7, dla zadania typu 5X5 potrzeba 1 + 2 + 3 + 4 i ogólnie, dla zadania typu n X n potrzeba 1 + 2 + 3 + + .. . + (n - 3) + (n - 2) + (n - 1) wyłączeń elementarnych.
Trzykropek znajdujący się w środku sumy oznacza, że nie możemy wypisać wszystkich następujących po sobie członów, gdyż liczba ich zależy także od n (mamy ra - 1 członów). Dlatego przekształcimy wzór w ten sposób, by "w formie zamkniętej" wyraził liczbę potrzebnych informacji.
(Ci, którzy w szkole średniej uczyli się wzoru na sumę postępu arytmetycznego, teraz na pewno rozpoznają stosowany tam sposób rozumowania.)
Niech potrzebna liczba wyłączeń elementarnych wynosi E:
E = 1 + 2 + 3 + ... + (n- 3) + (n - 2) + (n - 1)
Napiszemy to samo dwa razy jedno pod drugim; raz w kolejności takiej jak powyżej, drugi raz zaś umieszczając wyrazy po prawej stronie równania w odwrotnej kolejności:
E = 1 + 2 + 3 + , . . + (n - 3) + (n -.....2) + (n - 1)
E = (n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1
Suma członków napisanych jeden pod drugim po prawej strome wszędzie jest równa n:
1 4- (n - 1) = 2 + (n - 2) = 3 + (n - 3) = ... = n
Tak więc dodając obustronnie dwa równania otrzymujemy:
2? = 71 + n + n + . .. + n + n + n +
a ponieważ po prawej stronie mamy n - 1 członów
2? = (Ti - 1) o n więc liczba potrzebnych wyłączeń elementarnych wynosi
E = n(n- 1) 2
Teraz możemy postawić pytanie: kiedy jest ich tyle?
Ustaliliśmy już, że wtedy, gdy zadanie można rozwiązać nieprzerwanym łańcuchem jednoznacznych decyzji. Według twierdzenia o jednoznaczności jest tak zawsze, gdy rozwiązanie zadania jest jednoznaczne.
Uważajmy jednak! Jeżeli nawet rozwiązanie zadania jest jednoznaczne, ale nadmiar wyłączeń usuniemy tak, że
zostawimy -^--------- wyłączeń elementarnych, a resztę
zabierzemy tylko tak "na oko", to może się zdarzyć, że w toku tego działania zostanie utracona jednoznaczność rozwiązania i nieważna stanie się także prawidłowość, że
n (n - 1)
wystarcza -wyłączeń.
2
Rozpatrzmy na przykład znów zadanie 9. Wszystkie wyłączenia elementarne tego zadania widoczne są na rys. 9.1. Kopią rys. 9.1. jest rys. 25.1, z tą różnicą, że tu już wszystkie wyłączenia elementarne oznacza ten sam szary kolor (tylko dwa pola są ciemniejsze od innych, ale to ? innego zupełnie powodu).
Zadanie 9 jest typu 6 X 6; w przypadku jednoznacznej rozwiązalności liczba potrzebnych wyłączeń elementarnych wynosi ponieważ tu n = 6 (tyle otrzymaliśmy także w rozwiązywaniu zadania 10: 1 + 2 + 3 + 4 + 5 = 15). Ze względu na to, że występuje tu 19 ciemnych pól, w przypadku jednoznacznej rozwiązalności można opuścić z nich 19 - - 15 = 4, 4 informacje były redundancyjne (tyle znaleźliśmy ich także w rozwiązaniu 9c).
Tak, ale spróbujemy opuścić zamiast czterech tylko dwa wyłączenia elementarne, zaznaczone na rys. 25.1 zupełnie czarnym kolorem. Otrzymujemy rys. 25.2, a ten już w każdym swym rzędzie i w każdej kolumnie ma przynajmniej dwa białe pola. To oznacza, że rozwiązanie zadania przedstawionego na rys. 25.2 już nie jest jednoznaczne: występują tu co najmniej dwa rozwiązania *>.
Zatem: dwa wyłączenia elementarne z zadania 25.1, zaznaczone zupełnie czarnym kolorem, nie są informacjami redundancyjnymi. Spośród 19 wyłączeń elementarnych z rys. 25.1 4 są redundancyjnymi, ale nie dowolne cztery. Należy opuścić 4 spośród 19 wyłączeń elementarnych tak jednak, by jednoznaczność rozwiązania nadal została zachowana.
Jak można opuścić w taki sposób 4 wyłączenia? Na to teraz nie ma recepty, możemy powiedzieć o tym dopiero po rozwiązaniu zadania. (W odpowiedzi podanej na pytanie 9c możemy zauważyć trzy różne sposoby.)
Teraz możemy już dokładnie sformułować to, co odkryliśmy o informacjach koniecznych i redundancyjnych.
Na to, by zadanie dwuwymiarowe o powiązaniu elementarnym typu n X n można było rozwiązać jednoznacznie, potrzeba co najmniej
n (n - 1)
wyłączeń elementarnych
Jeżeli zadanie jest rozwiązalne jednoznacznie, i co więcej, jest w nim danych
wyłączeń elementarnych, to spośród nich można wybrać k wyłączeń elementarnych tak, że rozwiązanie po ich opuszczeniu pozostanie nadal jednoznaczne (i oczywiście takie samo).
|