Labirynt

[Gość: stomek]

Na standardowej szachownicy będziemy budować labirynt w
taki sposób, że w każdym kroku dostawiamy ścianę
pomiędzy dwoma polami sąsiadującymi bokami.
Ile można maksymalnie wstawić ścian aby istniało
przejście między dwoma dowolnymi polami szachownicy
(można przechodzić tylko między polami sąsiadującymi
bokami)?
Jak to będzie dla szachownicy uogólnionej o rozmiarze MxN?

Tomek

[Gość: lukkasz]

dla zwyklej szachownicy to bedzie co najmniej 81 scianek, czyli ogolnie
MxN+M+N+1. Obstawiam, ze wiecej sie nie da.

[Gość: stomek]

zdaje się, że niedokładnie przeczytałeś treść zadania
81 ścianek nie wejdzie

Tomek

[Gość: lukkasz]

No tak, doliczylem sciany zewnetrzne. No to wychodzi 49?
pzdr,
lukkasz

[tororo]

Czyli ostatecznie mamy wzory:

dla szachownicy MxN
M x N - M - N +1

a dla szachownicy N x N

(N - 1)­­**2 (do kwadratu)

pozdr
Tororo

[Gość: stomek]

tororo napisał:

> Czyli ostatecznie mamy wzory:
> dla szachownicy MxN
> M x N - M - N +1

Ja bym zapisał to (N - 1)*(M - 1).
A może ktoś poda chociażby szkic dowodu, że to jest
faktycznie maksymalna liczba ścian.

Tomek

[tororo]

Ja to liczylem dla nieco innych założeń a mianowicie ze konstruujemy taki
labirynt, który zapewni nam odwiedzenie wszystkich pol bez „powtarzania drog”
czyli:
- zaczynamy na jedym polu przechodzimy wszystkie konczac na innym i nie
przechodzimy miedzy dwoma tymi samymi polami wiecej niż jeden raz.

Dla takiego przypadku myslalem tak:


Zalozmy na poczatek ze kazde pole ma 4 „swoje” scianki.
W sumie jest tych pol M * N

Aby z kazdego do kazdego można było przejsć „nie cofając się” maksymalnie pole
może mieć dwie scianki za wyjątkiem pól początkowego i startowego, które mogą
mieć po trzy scianki.

Zatem całkowita liczb sciane wynosi
LS = M*N*2 + 2.

Teraz odejmijmy sciany zewnetrzne, ktorych nie liczymy
Mamy wiec

LS = M*N*2 + 2 – 2*(M + N)

Ale zalozylismy najpierw ze kazde pole ma „swoje” scianki. A przeciez kazda z
nielezacych na brzegu szachownicy scianek należy do dwóch pól.

Wiec ostatecznie mamy

LS max= M*N – M – N + 1, czyli jak slusznie zauwazyl Tomek

LS max = (M-1)*(N – 1)

Jednak to nie jest dokladnie to samo zadanie co zadal Tomek. Tam nie było
warunku o jednorazowym przekraczaniu granicy miedzy dwoma polami. I wtedy
liczba pol, które maja tylko jedna wolna sciankę może być wieksza ( z trzech
stron ścianki mają). Wydawac by się moglo wiec ze powyzszy wzor nie będzie
sluszny w przypadku wersji Tomka. Jednak jeśli wstawiamy w srodek szachownicy
pola z trzema sciankami, to zaczynaja się tam również pojawiac pola tylko z
jedna scianka (z trzema wolnymi). Nie potrafilem „złapać” tej zalezności –
ale podejrzewam ze kazda dostawiona jako trzecia scianka na jakimś polu w
efekcie powoduje ze jedno z pozostalych pół posrodku szachownicy będzie miało
tylko 1 ścianę. Ale nie musi tak być bo inaczej w obu wersjach wyglada
stawianie scianek na polach skrajnych. W mojej wersji kazde brzegowe pole może
mieć najwyzej 1 scianke. U Tomka – 2. W kazdym razie w żaden sposób na malych
szachownicach (do 6 x 6) nie udalo mi się wstawic wiecej scianek niż wyynika to
ze wzoru.
Jak ktos policzy wzor dla wersji Tomka to jest wielki.

Pozdr
Tororo

[Gość: lukkasz]

Wzor dla przejscia bez zawracania (czyli kazdy kwadrat ma max 2 scianki oprocz
brzegowych i do tego dodajemy 2 krancowe) jest tez dobry dla przechodzenia z
zawracaniem, czyli dla trzy-sciankowca wstawionego w srodek. Przeciez kiedy juz
ustawimy taka trase bez zawracania przez szachownice to widac ze zeby dolozyc
do tego gdzies scianke to trzeba tez gdzies zlikwidowac bo sie inaczej blokuje
przejscie.
Albo inaczej - jak sa w ukladzie 4 kwadraty o 3 sciankach (czyli dwoch dla
brzegowych) to musi byc jakies przejscie miedzy tymi dwoma "tunelami", ktorych
one sa koncami, czyli musza byc tez dwa kwadraty o tylko 1 sciance.
Chyba sie zgadza.

[Gość: stomek]

Podoba mi się to rozumowanie z jedną ścieżką bez powrotów
i wyprowadzeniem wzoru. Ja na to nie wpadłem. Faktycznie
dokładając do środkowego pola z takiego układu trzecią
ściankę blokujemy i trzeba gdzieś wyciąć dziurę. Ale
trzebaby jeszcze udowodnić, że jedna dziura zawsze
wystarczy i że przy dokładaniu kolejnych ścianek zawsze
potrzebna będzie dokładnie jedna dziura.
Ja do dowodu podszedłem zupełnie od innej strony. Nie
próbowałem wyprowadzić wzoru tylko ....
Pomęczcie się jeszcze - odpowiedź za tydzień.

pozdrawiam,
Tomek

[Gość: lukkasz]

Pytanie przeciez bylo o maksymalna ilosc scianek, wiec nie trzeba udowadniac,
ze jedna dziura wystarczy, ale ze przynajmniej jedna trza dodac, a to chyba
jest oczywiste.

[Gość: stomek]

Sprowokowałeś mnie więc piszę.
Pomysł z jedną ścieżką pokazuje, że istnieje pewna klasa
labiryntów, która ma (N-1)(M-1) ścian. Jednak nie
dowodzi, że KAŻDY labirynt ma co najwyżej tyle ścian bo
przecież istnieje MNÓSTWO labiryntów nie zbudowanych z
jednej ścieżki. Idąc dalej tropem "jednościeżkowym"
należy udowodnić, że KAŻDY labirynt spełniający warunki
(tzn. z przejściem między dowolnymi polami) może być
skonstruowany z "jednościeżkowego" przez przekładanie
ścian, i że w każdym kroku przekładania dokładamy nie
więcej ścian niż usuwamy.
Wasz dowód pokazuje tylko, że nie da się dołożyć ściany
do "jednościeżkowego" nie usuwająć innej.

Tomek

Rozwiązanie z dowodem (długie)

[Gość: stomek]

Obiecałem dowód więc go przedstawiam. Kiedyś, gdy
wymyśliłem ten problem, mi się wydawało, że to można w
prosty sposób wykazać, ale chyba mi się tylko wydawało.

Definicja 1
Labirynt otwarty – labirynt, w którym między dwoma
dowolnymi polami istnieje ścieżka.

Definicja 2
Labirynt pełny – labirynt otwarty, w którym dołożenie
dowolnej ściany powoduje, że przestaje być otwarty.

Definicja 3
Labirynt maksymalny – taki labirynt pełny, że nie
istnieje labirynt pełny o większej liczbie ścian.

Lemat 1 (intuicyjny)
W labiryncie pełnym nie ma ścieżki, która jest cyklem
(tzn. zaczyna się na pewnym polu i wraca do tego pola
przechodząc co najwyżej raz przez każde pole).

Dowód (przez zaprzeczenie)
Załóżmy, że istnieje labirynt pełny, w którym istnieje
ścieżka będąca cyklem i oznaczmy zbiór jej pól przez S.
Wstawmy ścianę między dwoma sąsiednimi polami z S – po
tej operacji cały czas będzie istniała ścieżka między
dwoma dowolnymi polami z S (jak na bieżni stadionu
postawimy zaporę to cały czas można po całej bieżni
biegać – tylko już nie dookoła).
Założenia o pełności labiryntu z dowolnego pola nie
należącego do S istnieje ścieżka do pewnego pola
należącego do S. Możemy przyjąć, że taka ścieżka nie
zawiera pól z S (oprócz ostatniego pola) – gdyby
zawierała wcześniej pole z S to możemy ją skrócić.
Jeśli więc weźmiemy dowolne dwa pola A i B nie należące
do S to między nimi będzie ścieżka z A do S, potem między
pewnymi polami S a potem z S do B.
Uzyskaliśmy sprzeczność – po dołożeniu ściany cały czas
istnieją ścieżki między dowolnymi polami więc labirynt z
cyklem nie jest pełny

Lemat 2 (bardzo przydatny)
Każdy pełny labirynt posiadający tylko pionowe ściany ma
jedną brakującą ścianę pomiędzy każdą parą sąsiednich
kolumn i w sumie ma (M-1)(N-1) ścian.

Dowód (indukcja po kolumnach)
Ostatnia kolumna pełnego labiryntu jest oddzielona od
przedostatniej pionową ścianą z dokładnie jedną dziurą
(ściana złożona z M-1 ścianek między polami). Gdyby nie
było żadnej dziury to nie będzie przejścia. Gdyby były
dwie dziury to będzie cykl (bo obu stronach ściany
przejście między dziurami bo nie ma poziomych ścian), a z
Lematu 1 cykli nie ma w pełnym labiryncie.
Po odcięciu ostatniej kolumny cały czas labirynt jest
pełny bo ścieżki między jego polami nie należącymi do
ostatniej nie mogły przechodzić przez ostatnią kolumnę
(bo tam było tylko jedno wejście).
Odcinając kolejno N-1 kolumn po M-1 ścianek doprowadzamy
labirynt do postaci jednokolumnowej bez ścianek, a po
drodze usunęliśmy (M-1)(N-1) ścianek.

Lemat 3 (oczywisty)
Labirynt pełny posiadający (M-1)(N-1) pionowych ścian nie
może mieć poziomych ścian.

Dowód
Jeśli labirynt ma (M-1)(N-1) pionowych ścian to na
dokładnie jedną brakującą ścianę między każdymi
sąsiednimi kolumnami. Nie może mieć więcej bo wtedy
między innymi kolumnami musiałby być komplet pionowych
ścian co jest niemożliwe.
Nie powiedzie się próba wstawienia poziomej ściany do
żadnej kolumny. Jeśli spróbujemy powyżej lub poniżej
dziur do sąsiednich kolumn to odetniemy koniec jednej
kolumny, a jeśli pomiędzy dziurami to rozetniemy labirynt
na dwie części.

Lemat 4 (kluczowy)
Każdy labirynt maksymalny posiadający przynajmniej jedną
poziomą ścianę można przekształcić na inny maksymalny
usuwając jedną poziomą ścianę, a dokładając jedną pionową
ścianę.

Dowód
Weźmy dowolny labirynt maksymalny posiadający poziomą
ścianę. Musi on mieć przynajmniej dwie kolumny
(jednokolumnowy nie może mieć poziomej ściany bo nie
będzie przejścia) i przynajmniej dwa wiersze (w
jednowierszowy nie da się wstawić poziomej ściany).
Muszą w tym labiryncie istnieć dwie sąsiednie kolumny
między którymi brakuje dwóch pionowych ścian. Gdyby
takich nie było labirynt miałby (M-1)(N-1) pionowych
ścian i zgodnie z Lematem 3 nie posiadałby poziomej
ściany co jest sprzeczne z założeniem.
Weźmy te kolumny i dwie najwyższe dziury między nimi. W
jednej z tych kolumn nie istnieje ścieżka łącząca pola
przy dziurach nie przechodząca przez dziury. Gdyby w obu
kolumnach były takie ścieżki to będziemy mieli cykl
(przez górną dziurę, ścieżką do pola przy dolnej dziurze,
przez dolną dziurę, ścieżką do pola przy górnej dziurze)
co jest sprzeczne z Lematem 1.
Skoro dla jednej kolumny nie ma takiej ścieżki to
istnieje ciąg ścian rozpoczynający się ścianą poziomą w
tej kolumnie pomiędzy dziurami, a kończący się ścianą
sąsiadującą z brzegiem labiryntu. Ten ciąg ścian blokuje
możliwość wytyczenia takiej ścieżki.
Jeżeli teraz wstawimy pionową ścianę w górną dziurę to
rozetniemy labirynt na dwie części, a linia podziału
będzie przebiegać od góry między dwoma kolumnami, a dalej
ciągiem ścian opisanym powyżej. Linia podziału będzie
więc zawierać poziomą ścianę. Wyróżnijmy tę poziomą ścianę.
W każdej z dwóch części labiryntu będzie istniała ścieżka
między dwoma dowolnymi polami tej części (nie dowodzę
tego, ale to chyba oczywiste). W szczególności w każdej
części będzie istniała ścieżka od dowolnego pola do pola
leżącego obok wyróżnionej poziomej ściany. Jeśli tę
ścianę usuniemy to będzie istniała ścieżka między dwoma
dowolnymi polami labiryntu (w jednej części do pola obok
wyróżnionej ściany, przez dziurę po usunięciu tej ściany
i w drugiej części do pola docelowego).
Usunęliśmy ścianę poziomą i dołożyliśmy pionową
zachowując liczbę ścian i istnienie ścieżek między
dowolnymi polami. Nowy labirynt jest więc otwarty.
Jest też pełny bo gdyby nie był pełny, to moglibyśmy
dokładać do niego ściany uzyskując pełny o większej
liczbie ścian. Jest to jednak niemożliwe bo wejściowy
labirynt był maksymalny i nie może istnieć labirynt pełny
o większej liczbie ścian.
Skoro jest pełny to jest maksymalny bo liczba ścian nie
zmieniła się.

Twierdzenie
Każdy labirynt maksymalny ma dokładnie (M-1)(N-1) ścian.

Dowód
Weźmy dowolny labirynt maksymalny. Dopóki ma ściany
poziome to przekształcamy go z wykorzystaniem Lematu 4
usuwając ściany poziome, dokładając pionowe, zachowując
liczbę ścian i zachowując jego maksymalność. Gdy zostaną
same pionowe to zgodnie z Lematem 2 ma (M-1)(N-1) ścian,
a ponieważ przy przekształceniach zachowywaliśmy liczbę
ścian to pierwotny labirynt też miał (M-1)(N-1) ścian.

c.b.d.o.

Jak ktoś to udowodni w prostszy sposób to chętnie się
zapoznam z wynikami.

pozdrawiam tych co to przeczytali,
Tomek