Dwa pytania
a) Rysunek 25.1 jest rysunkiem zadania 9, o tym zadaniu zaś wiemy, że ma rozwiązanie.
Wszystkie pola, które na rys. 25.1 były białe, pozostały białe także na rys. 25.2. Wskutek tego każde takie rozwiązanie, które można wstawić do rys. 25.1, można także wstawić do rys. 25.2.
b) Gdyby istniał taki dowód, który by się nie opierał na istniejącym już jednym rozmieszczeniu wież, oznaczałoby to, że takie ustawienie wież już istnieje. Czyli:
"Jeżeli w każdym rzędzie i w każdej kolumnie szachownicy typu n X n znajdują się przynajmniej dwa wolne pola, to w tablicy można rozmieścić n wież w taki sposób, by:
I. każda wieża stała na jakimś ,,wolnym polu",
II. żadna nie mogła bić drugiej."
Ale w rozwiązaniu zadania 25 widzieliśmy, że takie rozmieszczenia wież na szachownicy typu n X n oznaczają jednocześnie rozwiązania odpowiedniego zadania typu n X n} o powiązaniu elementarnym. Twierdzenie ujęte w cudzysłów jest więc równoważne z poniższym:
"Jeżeli w każdym rzędzie i w każdej kolumnie zadania dwuwymiarowego o powiązaniu elementarnym są co najmniej dwa białe pola, to zadanie ma rozwiązanie."
To jednak nie jest prawdą: dowodzą tego rys, 20.1, 20.2, 22a, b oraz 23a i c.
Tych wszystkich rysunków nie trzeba nawet było wymieniać: już jeden jedyny kontrprzykład obala twierdzenie.
Podsumowanie
1. W zadaniach tych na podstawie danych informacji trzeba wyznaczyć wzajemnie jednoznaczne przyporządkowanie pomiędzy dwoma danymi zbiorami skończonymi *> (poniżej oznaczamy te dwa zbiory przez A i B).
Na to, aby pomiędzy elementami dwóch zbiorów istniało wzajemnie jednoznaczne przyporządkowanie, obydwa te zbiory muszą oczywiście składać się z tej samej liczby elementów. (Liczbę ich elementów oznaczamy przez n: zatem zarówno A jak i B są zbiorami n-elemen-towymi.)
Dane informacje są często złożone: zawierają one jednocześnie szereg informacji elementarnych. Te informacje elementarne w najprostszym przypadku **> mogą być dwojakiego rodzaju:
powiązania elementarne, które stwierdzają bezpośrednio, że któryś element zbioru A jest powiązany z którymś elementem zbioru B (bezpośrednie informacje "decyzyjne");
wyłączenia elementarne, które stwierdzają tylko to, że któryś element zbioru A nie jest powiązany z którymś z elementów zbioru B.
Wobec tego jedno powiązanie elementarne jest równoważne ft-1 wyłączeniom elementarnym. Mianowicie to, że element a zbioru A jest powiązany z elementem b zbioru B, oznacza także, że nie jest on powiązany z pozostałymi n-1 elementami zbioru B.
*> Podkreślamy, że mowa o zbiorach skończonych, dlatego że istnieją także zbiory nieskończone: np. zbiór wszystkich liczb całkowitych lub zbiór ułamków (właściwych) o wartościach pomiędzy 0 a 1, lub też zbiór wszystkich punktów znajdujących się na odcinku prostej itd.
**) To trzeba podkreślić dlatego, że można sobie wyobrazić także takie informacje, które nawet mniej mówią od jednego wyłączenia elementarnego.
168
Zatem uzasadniony może być pogląd, że tylko wyłączenie elementarne jest informacją elementarną, natomiast powiązanie elementarne nią nie jest.
Te powiązania elementarne i wyłączenia elementarne są oczywiście często ukryte w informacji. Zatem pierwszą operacją jest zawsze to, że informacje trzeba "przełożyć" na język powiązań i wyłączeń elementarnych. Poniżej zakładamy, że ten "przekład" - co często nie jest łatwym zadaniem - już miał miejsce. Tak więc moglibyśmy także powiedzieć, że informacje zadań o powiązaniu elementarnym są ostatecznie wszystkie bądź powiązaniami elementarnymi, bądź wyłączeniami elementarnymi.
Rozwiązaniem zadania nazywamy każde wzajemnie jednoznaczne przyporządkowanie zbiorów A i B, które jest zgodne z wszystkimi podanymi warunkami. (Jednocześnie "rozwiązanie" jest drogą prowadzącą do wyznaczenia tego przyporządkowania.)
2. Rozwiązanie zadania (po poprzednich uwagach) zaczynamy zawsze od tego, że ustalamy bezpośrednio dane powiązania elementarne: z nimi mianowicie nie ma już żadnego problemu.
Jeżeli zadanie podaje bezpośrednio p powiązań elementarnych, to zagadnienie zawęża się: z elementami występującymi w podanych powiązaniach nie mamy już nic do roboty. Tak więc zarówno ze zbioru A jak i ze zbioru B pozostaje po w- p elementów; tworzą one zbiór A* i zbiór B*. Poniżej stosujemy oznaczenie n - p = n*.
Rozwiązywanie kontynuujemy w ten sposób, że sprawdzamy, czy w zbiorze A* lub B* znajduje się taki element, o którym na podstawie informacji można stwierdzić, że nie może być powiązany z żadnym elementem drugiego zbioru, z wyjątkiem jednego jedynego. Wtedy powiązanie jest możliwe tylko z tym jedynym elementem; mamy wobec tego możliwość jednoznacznej decyzji (..wyłączenia elementarne łączą się w informację decyzyjną"), w następstwie czego zadanie znowu zawęża się (każdy z obydwu zbiorów zmniejsza się o jeden element) i wobec tego rośnie szansa, że będziemy mieli możliwość nowej jednoznacznej decyzji. Jeżeli to rzeczywiście następuje, to znowu możemy zawęzić zadanie, i tak dalej.
O ile to postępowanie można kontynuować nieprzerwanie tak długo, aż wyjaśnimy wszystkie powiązania, to wtedy mówimy, że zadanie można rozwiązać nieprzerwanym łańcuchem jednoznacznych decyzji.
Udowodniliśmy twierdzenie o jednoznaczności, które orzeka, że każde zadanie o powiązaniu elementarnym, którego rozwiązanie jest jednoznaczne - czyli ma dokładnie jedno rozwiązanie - można rozwiązać za pomocą nieprzerwanego łańcucha decyzji jednoznacznych.
3. Jeżeli informacje składają się już tylko z wyłączeń elementarnych (tzn. jeżeli mamy już do czynienia tylko z ?i*-elemantowymi zbiorami A* i B*), to wtedy metoda tablicowa czyni zadanie bardzo przejrzystym, a jego rozwiązanie łatwym i automatycznym. Polega ona na tym, że przygotowujemy dwuwejściową tablicę, mającą na każdym z dwóch boków n* podziałów (wobec tego tablica składa się z n* o n* = n*2 pól).
W podziały wpisujemy w dowolnej kolejności po jednej stronie elementy zbioru A*, po drugiej stronie - elementy zbioru B*;
pola, w których według podanych wyłączeń elementarnych znajdują się elementy niepowiązane, malujemy na czarno;
pola wypadające na skutek zawężenia zadania także malujemy jakimś kolorem (w dotychczasowych zadaniach czyniliśmy to kolorem szarym).
Tak więc decyzję jednoznaczną otrzymujemy w każdym rzędzie i kolumnie, w których pozostaje dokładnie jedno białe pole. To jedyne białe pole jest rubryką powiązań ("polem połączeń"). Jeśli zadanie jest rozwiązane, to w tablicy musi być łącznie TŁ* pól połączeń, tak by do każdego rzędu i do każdej kolumny dostało się dokładnie jedno pole połączeń (zatem dowolne dwa pola połączeń powinny się znaleźć zawsze w różnych rzędach i różnych kolumnach).
Jeśli w tablicy zaznaczymy także, które wyłączenie elementarne pochodzi od której informacji, to wtedy metoda tablicowa nadaje się także do analizy: porównania różnych dróg rozwiązania, W ten sposób za pomocą tablicy możemy wyszukać krótką, elegancką drogę rozwiązania. Tę drogę możemy później także opisać, jak gdyby tablicy nie było.
4. Odnośnie do liczba rozwiązań rozróżniamy trzy przypadki: gdy ta liczba wynosi 0, 1 i więcej niż 1.
a) Gdy liczba rozwiązań wynosi 0, czyli gdy zadanie nie ma rozwiązań, wówczas warunki są sprzeczne (tworzą układ sprzeczny).
W zadaniach o powiązaniu elementarnym najprostsza postać sprzeczności występuje wtedy, gdy przy jednym elemencie któregoś zbioru dane wyłączenia nie umożliwiają połączenia z żadnym elementem drugiego zbioru (w jednym rzędzie lub w jednej kolumnie tablicy wszyst-
170
kie pola są czarne, ^p. zadanie 19). Występuje jednak także bardziej ukryta \postać, gdy sprzeczność ujawnia się tylko przy "zawężaniu" zadania (np. zadanie 20, 22a,b,
23a,c,d).
Jeśli natomiast liczba rozwiązań nie wynosi 0, czyli
jeśli istnieje rozwiązanie {które jest zgodne z każdym warunkiem), to układ warunków jest niesprzeczny.
b) Jeśli liczba rozwiązań wynosi 1, to wtedy mówimy, że rozwiązanie zadania jest jednoznaczne (zadanie można rozwiązać jednoznacznie). W tym przypadku układ warunków jest niesprzeczny i zupełny. (Nazywamy go zupełnym dlatego, że ,,mówi o wszystkim".)
Jeśli zadanie dwuwymiarowe o powiązaniu elementarnym ma dokładnie jedno rozwiązanie, to można je zawsze uzyskać za pomocą łańcucha decyzji jednoznacznych (twierdzenie o jednoznaczności).
c) Jeśli liczba rozwiązań jest iviększa niż 1, to zadanie ma wprawdzie rozwiązanie, ale nie jest ono jednoznaczne {zadanie "nieokreślone"). W tym przypadku układ warunków jest wprawdzie niesprzeczny, ale nie jest zupełny ("nie mówi wszystkiego'').
5. Jak zmieniają się układy warunków różnego typu, gdy odrzucimy któryś z warunków (informacji), lub dodamy nowe warunki?
Sprzeczny układ informacji pozostaje sprzeczny także w przypadku dodania nowej informacji (nowych informacji). Natomiast jeśli odejmiemy od niego informację, to jest możliwe, że stanie się niesprzeczny.
Niesprzeczny układ warunków pozostaje niesprzeczny także w przypadku odjęcia dowolnie wielu informacji. W przypadku dodania nowych informacji
pozostaje on nadal niesprzeczny, jeśli wśród rozwiązań układu można znaleźć takie, z którym jest zgodna każda poszczególna nowa informacja;
jeśli takiego rozwiązania nie można znaleźć, tzn. jeśli do każdego poszczególnego rozwiązania można znaleźć sprzeczną z nim informację, to układ staje się sprzeczny. Układ warunków zupełny (i zarazem niesprzeczny) pozostaje nadal zupełny, jeśli dodamy do niego takie nowe informacje, które zachowują niesprzeczność; jednakże jeśli odrzucimy z niego jakąś informację, to wtedy układ może ewentualnie już stracić zupełność i staje się
niezupełny.
6. Układ warunków (informacji), z którego można
odrzucić warunki (informacje) tak, że rozwiązania zadania pozostają nadal takie same, nazywamy redundancyj-nym. Redundancja oznacza, że informacje układu nie są od siebie niezależne.
Jeśli wszystkie informacje zadania dwuwymiarowego o powiązaniu elementarnym składają się z wyłączeń elementarnych, jeśli ten układ informacji jest mesprzecz-ny i zupełny (czyli zadanie ma dokładnie jedno rozwiążą-
nie) oraz zawiera dokładnie o--^-^--------wyłączeń elemen-
tarnych, to układ nie jest redundancyjny.
Jeśli natomiast taki układ zawiera
n* (n* - 1)
mz
więcej wyłączeń elementarnych, to jest on redundan
cyjny. W przypadku, gdy liczba wyłączeń elementarnych
Tl* (TL* - 1)
wynosi----------------- + k, można z układu wybrać k wyła-
czeń elementarnych tak, by układ po ich odrzuceniu pozostał nadal zupełny.
Najprostsza postać redundancji w zadaniach o wyłączeniu elementarnym występuje wtedy, gdy poszczególne informacje zawierają identyczne wyłączenia elementarne (zadanie 4*). Bardziej złożona, ukryta postać redundancji występuje wtedy, gd}^ ujawnia się ona tylko przy okazji ,,zawężeń" (zadanie 9).
7. Zadanie dwuwymiarowe o powiązaniu elementarnym rozpada się na dwa niezależne od siebie zadania częściowe, jeżeli na wykresie można wybrać pewną liczbę rzędów i tyle samo kolumn tak, żeby
wszystkie białe pola wybranych rzędów znalazły się w miejscu przecięcia się z dowolnie wybraną kolumną, lub żeby
wszystkie białe pola wybranych kolumn znalazły się w miejscu przecięcia się z dowolnie wybranym rzędem. Pola znajdujące się na przecięciu się wybranych rzędów i kolumn lub pozostałych rzędów i kolumn tworzą dwa niezależne od siebie zadania częściowe.
Jeśli zadanie rozpada się na niezależne zadania częściowe, to liczba rozwiązań równa się iloczynowi liczby rozwiązań niezależnych zadań częściowych.
|