Pałac

[mesquaki]

Królowi Pysznacemu Niewielkiemu opatrzył się już dotychczasowy pałac,
postanowił więc wybudować nowy. Pałac ma być piękny jak marzenie, a komnat
jak najwięcej, ale tak, żeby można było przejść z dowolnej komnaty do każdej
innej przez nie więcej niż pięć pośrednich. Ponadto drzwi w żadnym pokoju nie
może być więcej niż cztery.
Ile komnat może mieć pałac Pysznacego?

[bbaju]

A co z korytarzem? I czy okna musi mieć każda?

[mesquaki]

bbaju napisała:

> A co z korytarzem? I czy okna musi mieć każda?
Brak powyższych. A w każdym razie nas nie interesują. Przechodzi się
bezpośrednio z pokoju do pokoju (przez drzwi :).

mes

[Gość: pafcio]

a czy w takim razie kształt wszystkich pokoi jest taki sam? czy możliwe jest na
przykład że są pokoj który zaużmy mają kształt dość podłużny?
pzdr

[mesquaki]

Pokoje mogą mieć dowolne kształty.
m

[mmiga]

Wg mnie 18.

Jeśli za mało, to daj taką informację.

pozdrawiaMM

[Gość: Duncan]

Według mnie 16.

[Gość: pafcio]

no ja na razie stawiam na co najmniej 36

[kornel-1]

W przeciwieństwie do projektu Pafcia, który nazwałbym Pałacem Grafitowym, mój
projekt nazwę Pałacem Diamentowym.
1093
(jeśli czegoś nie pomyliłem)

Kornel

[bbaju]

Jeżeli nie ma żadnych ograniczeń architektonicznych i problem sprowadza się do
zwyczajnych grafów, to maksimum wynosi dokładnie 81.

:)
Pozdrawiam
Baj

[bbaju]

Zagladasz tu jeszcze czasami?
Mam nadzieję, że tak, wtedy być może i Tobie nasunęła się analogia do
sławetnego metra z LSK.

Pozdrawiam,
Baj

[tororo]

bbaju napisała:

> Zagladasz tu jeszcze czasami?
Zaglądam, jakżeby inaczej:)

> Mam nadzieję, że tak, wtedy być może i Tobie nasunęła się analogia do
> sławetnego metra z LSK.
Nasunęła się nasunęła ale łezka mi sie w oku zakręciła ze ktos jeszcze moja
ukochana LSK pamieta.
Dzieki Ci wielkie:)
Od razu w archiwan nurknąłem. Zadanie i owszem, przednie było:)
A jak Tobie wtedy poszło?

[tororo]

bbaju napisała:


> Mam nadzieję, że tak, wtedy być może i Tobie nasunęła się analogia do
> sławetnego metra z LSK.
ale sie doczytałem - i była dwa zadania w LSK podobne do tego
Jedno - to z metrem a drugie z koleją - i to drugie było bardziej podobne do
tego

a drugie to

[bbaju]

tororo napisał:

a drugie z koleją - i to drugie było bardziej podobne do
> tego
Kolei nie pamiętam, a może własnie to kolej była, hmmm..., sama już nie wiem.
W kazdym razie parametry byly odrobinę tylko inne. We wcześniejszym poście
pytałam już o ewentualne korytarze, okna (czyli czy koniecznie muszą być
zewnętrzne) - odpowiedź była dość jasna.

>A jak Tobie wtedy poszło?
Średnio.

Pozdrawiam,
Baj

[bbaju]

Zapomniałam dodać, że rolę tamtych torów pełnia zwyczajnie drzwi. W każdym
razie tak to potraktowałam.

Baj

[tororo]

A jak to jest z korytarzami w tym pałacu?
Sa, czy jednej z komnaty do drugiej przechodzi sie bezposrednio? a jeśli są
to czy moga sie krzyżować albo mijać w pionie (jeden pod drugim) czy nie?

nie ma (n/t)

[mesquaki]

[lotrzynapl]

Hmm jak narazie wychodzi mi 25...

pozdr.
ALP

[lotrzynapl]

Ale juz widze, ze da sie wiecej - ach te podluzne pokoje ;-)

pozdr.
ALP

[bbaju]

lotrzynapl napisał:

>- ach te podluzne pokoje ;-)

Podłużne pokoje narysujesz sobie później, na razie rozrysuj sobie graf, zaraz
pokoje cudownie się rozmnożą.

Baj

[lotrzynapl]

Grafy mialem tylko na Badaniach Operacyjnych i chyba jest to dosc szerokie
pojecie ?? Nie mam pomyslu jak rozrysowac graf do tej konkretnie sytuacji.
Jakiees programowanie dyskretne czy jak??? Sorry za malo profesjonalne
podejscie :) ale jakos nie widze tego rozwiazania - jeszcze :)

pozdr.
ALP

[bbaju]

lotrzynapl napisał:

> Grafy mialem tylko na Badaniach Operacyjnych i chyba jest to dosc szerokie
> pojecie ??

Naprawdę, nie potrzebujesz żadnej wiedzy, tylko samo przedstawienie jest
wygodne. Komnaty oznacz kółkami, a łączące 2 komnaty drzwi - linią łączącą te
kółka. A jak będziesz chciał na koniec narysować plan otrzymanego rozwiązania,
dobierzesz tylko odpowiednie kształty i wielkości. Zobaczysz, jak ładnie się to
wszystko samo ulokuje.

Powodzenia,
baj

[bbaju]

Zerknij do swojej gazetowej skrzynki

Baj

[tororo]

Mequaki - mam nadzieje ze sie nie poniewasz - ale mysle ze pomoze to
forumowiczom w poszukiwaniu najlepszego rozwiązania zadania o pałacu.
Otóz wiele lat temu - bo 12 - zamiesciłem w Gazecie Wyborczej w prowadzonej
przeze mnie Lidze Szarych Komórek takie oto zadanie:

Należy zaprojektować sieć kolejową. Z każdej stacji mogą wychodzić najwyżej
trzy tory. Tory nie mogą się krzyżować ani łaczyć poza stacjami. Nie moga też
przechodzić nad sobą. Przejazd z jednej dowolnej stacji do innej nie może
wymagać przemieszczania się przez więcej niż pięć stacji pośrednich.


Najlepsze rozwiazanie nadesłała .... - jedna z naszych forumowiczek. Na razie
nie zdradze nicka. Chyba ze się sama przyzna.

Zadania były punktowane - w tym przypadku - im wiecej stacji tym wiecej
punktów. Zadanie jest prostsze niz to z pałacem - bo z każdej stacji wychodzą
trzy tory a nie cztery. Ale jak zobaczycie jak wyglada rozwiązanie (38 stacji)
to zobaczycie że z Pałacem nie ma żartów.

A jak chcecie zobaczyc rozwiazanie to zajrzyjcie:
SIEĆ KOLEJOWA

Pozdr

tororo
www.rozgrywka.pl

[mesquaki]

Gratulacje dla Baj :).

[Gość: grzesiek]

Autor już pogratulował Baj (jak rozumiem rozwiązania 81), ale ja znalazłem
graf ze 104 węzłami. Wprawdzie nie wiem, jak ten graf zrealizować w postaci
pokoi, ale na wszelki wypadek go opiszę - może ktoś znajdzie realizację, albo
wykaże, że jest niemożliwa.

Wyobraź sobie najpierw drzewo: 1 rodzic, 4 synów, 12 wnuków, 36 prawnuków
(używam tej familijnej nomenklatury dla skrócenia opisu).
Następnie wyobraź sobie cztery takie drzewa, mające wspólne 36 węzłów -
prawnuków.
W sumie jest 36 + 4*(1+4+12) = 104 węzły.

Nie wiem jak ten graf narysować bez przecinania się połączeń. Czy jest jakiś
sposób na stwierdzenie czy jest to możliwe czy nie?

[bbaju]

Gość portalu: grzesiek napisał(a):

> Nie wiem jak ten graf narysować bez przecinania się połączeń. Czy jest jakiś
> sposób na stwierdzenie czy jest to możliwe czy nie?

Grafu nie narysujesz, potrzebny będzie Ci trzeci wymiar, ale pomysł jest i tak
świetny, bo przecież chodzi o pałac. Myślę, że można go sobie wyobrazić, jako
składającego się z części głównej (prawnuki - pozostańmy przy tym nazewnictwie)
i czterech skrzydeł, każdego rodzica z własnymi synami i wnukami, jedno.
Gratuluję i oddaję palmę.

Pozdrawiam,
Baj

PS. Zyczę wszystkim forumowiczom rozkosznego łamania głowy w 2005 roku