Dla kazdego kto chce sobie mozg polamac

Coz ... ostatnio czytalem sobie forum w tyl i natrafilem na zapytanie na temat sieci neuronowych itp.. Doszlo tam do wymiany zdan na temat grafow i szukania drogi. Przypomnialem sobie pewien moj problem z przeszlosci. Calosc rozchodzi sie o rozwiazanie nastepujacego zadania: na dwuwymiarowej powierzchni mamy 3 kropki i 3 kwadraty. Nalezy poprowadzic z kazdej kropki po 3 linie. Kazda z lini ma laczyc sie z osobnym kwadratem. Linie moga miec dowolny ksztal i dlugosc. Nie maja prawa sie przecinac. Nad zadaniem mysleli nauczyciele z mojej szkoly i znajomi. Wyszyscy dochodzili do wniosku ze sie nie da go rozwiazac. Ale osoba, od ktorej je dostalismy mowi ze da sie. I oto potrzebuje kogos kto napisal by program ktory odpowie na pytanie: Czy to jest do rozwiazania. Wydaje mi sie ze to kwestia wlasnie jakiegos grafu czy metody szukania drogi. Myslenie pozostawiam wam :>. Oto link, pod ktorym jest rysunek przykladowego blednego rozwiazania (bo jak na razie dobrego nie mam :]). Powodzenia

Link do przykladu: http://www.xewan.webpark.pl/przyklad.jpg

Jesli znajdziecie rozwiazanie w postaci programu to prosze przeslac mi tak owy na maila: [email protected]

Swietne zadanie :D Siedze przed kompem od ok 15h i powiem szczerze ze mila odmiana :D Ciezko mi idzie ;p

Mam ndzieje ze ktos na tym forum to ort! :D juz nie mowie o programie ale chociaz rysunek =] Bede czekal z niecierpliwoscia ^^ Miedzy czasie oczywiscie sam sie glowie ;p

Mam nadzieje ze na prawde jest rozwiazanie, ze nie wyjde na glupka :P siedzac przy zadaniu bez rozwiazania <lol>

Ja tak tylko napisze, ze nie jest napisane, ze kropki nie moga lezec "jedna na drugiej", czyli jest to dozwolone i problem znika :-P

xewan, uściślij te zadanie... czy np. figury mogą się nakładać? albo czy linie mogą się nakładać? czy linie mogą przecinać inne kółka? jeżeli jedno z tych warunków jest spełnione, to faktycznie jest to do rozwiązania. Pozdrawiam.

zadanie jest do rozwiązania jesli linie mogą przecinać kwadraty, kwadraty mogą być zawarte w sobie bąć być nałożone na sobie, kropki mogą być wewnątrz kawdratów

jeśli natomiast linie nie mogą nic przecinać ani na nic się nakładać (tylko łączyć punkt z kwadratem) oraz wszystkie figury muszą być w innych punktach, to zadanie jest niewykonalne. Dowód: jeśli dwa punkty połączymy 6 liniami z trzema kwadratami, to automatycznie odizolujemy jeden z kwadratów od pozostałego punktu. Na nic kombinowanie z ustawieniami linii, prędzej czy później któryś z kwadratów musiałby zostać odizolowany od jednego z punktów :/

No coz ... Niestety ale figury nie moga sie nakladac, linie przecinac itp.. Zgadzam sie z wami ze to zadanie najprawdopodobniej jest nie do wykonania... tylko czemu nauczycielka (wrocila ze studiow z USA) twierdzi ze jest do wykonania ? :\ nie mam pojecia ... dlatego chce aby ktos napisal program ktory sprawdzi wszystkie powiazania.

edit:
Przy okazji - kolezanka kumpla, ktora zajmuje sie grafami ponoc rozwiazala to zadanie. Dlatego pchnelo mnie cos w strone grafow. Zas nauczycielka dala jej z to na koniec 6 z i infy :]

Coz zycze powodzenia :]

trudno taki program napisać, trzebaby chyba w nim uwzględnić, że punkty należące do linii mogą leżeć w dowolnym miejscu na płaszczyźnie (tylko nie na kółkach i kwadratach)..... a może by tak zaprząc do tego algorytmy genetyczne:] (tajna broń hehe:D)</image>

Przy okazji - kolezanka kumpla, ktora zajmuje sie grafami ponoc rozwiazala to zadanie. Dlatego pchnelo mnie cos w strone grafow. Zas nauczycielka dala jej z to na koniec 6 z i infy :]

wniosek: albo kolezanka popelnila błąd, który trudno dostrzec (każdy moze się machnąć w plątaninie linii i podobnych do siebie figur:D) albo nie dorastamy jej do pięt w rozwiązywaniu takich łamigłówek:) [lol]

a jeśli chodzi o program, to na prawdę nie ma sensu go pisać - zadanie nie do wykonania (sztab nauczycieli i znajomych nie mógł tego rozwiązać, a jedna uczennica nagle przyszła z rozwiązaniem? Coś mi tu nie pasuje:) Człowiek jest niestety omylny (nauczyciele też:))))

Na chama to mozna zalozyc, ze w zadaniu nie ma nic o tym, ze linia nie moze przechodzic przez kwadrat/punkt. Wtedy by sie nie przecinala z inna... (Chocby w blednym przykladzie - zielona linie przeprowadzic przez 3 kolko i do kwadratu :)
Wiem ze to kombinowanie, ale skoro ktos to rozwiazal, to moze znalazl wlasnie taki blad...

Według mnie nie ma rozwiązania. Do rozwiązania zadania należy użyć grafu przecięć i pokolorować go dwoma kolorami, a to jest niewykonalne w tym wypadku (albo mam błąd w programie testowym ;p ). Zadanie jest podobne do zadania "Autostrady" z X Olimpiady Informatycznej (2002/2003).

Rozłożenie kropek i kwadratów na płaszczyźnie (jeżeli się nie pokrywają) nie ma żadnego znaczenia.

Powtarzam, [b]moim zdanie nie ma rozwiązania!![/b]

To znane zadanko o 3 domkach i podłączaniu wody, gazu i prądu do każdego z nich. Rozwiązanie znajduje się np. tutaj http://groups.google.pl/groups?q=woda+gaz+prad+group:pl.sci.matematyka&hl=pl&lr=&ie=UTF-8&group=pl.sci.matematyka&selm=3829ad16.18390208%40155.158.99.2&rnum=1 ALe warto samemu pogłówkować i zastanowić się dlaczego nie wychodzi ;>

pzdr,

y.

Wywod pana Marka, niewatpliwie fachowy i w ogole, jest jednak dla mnie niezrozumialy :)
Moglby ktos to tak bardziel po ludzku wytlumaczyc?

Z wywodów pana Marka wynika, że graf ten nie jest planarny (czyli nie da się go narysować na płaszczyźnie łącząc każdą kropkę z każdym kwadratem, tak aby krawędzie się nie przecinały). Jeśli nauczycielka twierdzi, że się da tzn. że albo przemilczała jakieś dodatkowe założenia (np. można wykopać tunel w ziemi ;>) albo obaliła tw. Kuratowskiego co zasługuje na lola albo na medal Fieldsa za wybitne osiągnięcia ;p , co kto woli ;>

pzdr,

y.

Jak zrobic zadanie, ktorego nie zna sie tresci?? Powiedziales cos o jakims zadaniu i o co mniej wiecej chodzi. Teraz daj jego pelna tresc. Duzo zagadek polega na tym ze trzeba znalezdz haczyk, tu pewnie tez gdzies jest.

Jak zrobic zadanie, ktorego nie zna sie tresci?? Powiedziales cos o jakims zadaniu i o co mniej wiecej chodzi. Teraz daj jego pelna tresc. Duzo zagadek polega na tym ze trzeba znalezdz haczyk, tu pewnie tez gdzies jest.

to nie podstawowka i zadanko z trescia tylko klasyczna lamiglowka logiczna... - nie rob sobie jaj..

znam odp mi sie udało linie sie nie przecinają itd. nie przechodzą prze kwadraty itd. i prze koła też nie geniusz ze mnie siedziałem na tym 10 min!!!!!!!!!!!

znam odp mi sie udało linie sie nie przecinają itd. nie przechodzą prze kwadraty itd. i prze koła też nie geniusz ze mnie siedziałem na tym 10 min!!!!!!!!!!!

Może zechcesz nas oświecić swoim geniuszem i wskażesz drogę przez ciemną dolinę głupoty, w jakiej się tłoczymy?

A ja jestem na 99% pewne że to nie ma rozwiązania.
Doszedłęm do wniosku że samo ułożenie tych kólek i kwadratów nie jest same z siebie istotne. Więc argumentując moją tezę (ale mi tu filozofią zajechało :D ) najlepiej zrobić tak:
Narysować okrąg i na przemian umieszczać kołka i kwadraty.I już mam po 2 połączenia. I teraz jeden kwadrat połączyć z jednym kółkiem( przez środek okręgu) i inny z innym na zewnątrz okrągu. I już lipa bo mamy odciętego jeden kwadrat od ostatniego kólka [sciana] I na tym przykładzie ławto można zauważyć że sie teog nie da zrobić :/

Doszedłem do wniosku że samo ułożenie tych kólek i kwadratów nie jest same z siebie istotne.

Dokładnie. Można to też zrozumieć na trochę innym przykładzie. Wyobraźmy sobie, że wszystko to znajduje się w układzie współrzędnych (dowolnie połączone, nie spełniające zadania). Teraz przesuńmy kilka figur w kierunku (y+) - to nic nie zmieni, najwyżej możemy przedłużyć linie. Możemy teraz spłaszczyć całość (przesuwając wszystko np. w stronę x-) - tak możemy osiągnąć dowolną sytuację w położeniach figur.

x-,y+ oznaczają odpowiednie "kierunki" osi współrzędnych.

Jeżeli dochodzimy do wniosku, że wszystkie sytuacje są identyczne, to możemy postawić figury na jednej prostej (np. "poziomej"). Wiemy teraz które połączenia nie mogą przebiegać po tej samej stronie - to jest oczywiste. Mając te dane możemy zbudować graf przecięć. Ponieważ nie da się go pokolorować dwoma kolorami tak aby sąsiednie wierzchołki miały różne kolory - zadanie nie ma rozwiązania.

mi wyszedl usmiechniety chlopek z profilu

http://venus.wsb-nlu.edu.pl/~jmigacz/prv/graf.GIF

Gdyby jeszcze ten chłopek mógł sobie nieinwazyjnie wsadzić brodę do nosa to byłoby ok ;>

pzdr,
y.

// dobre, dobre [soczek] - ŁF

Zadanie nie ma rozwiazania, ktokolwiek twierdzi inaczej niech je przedstawi, a nie mowi ze ktostam to na pewno rozwiazal.