Praznična logična dlakocepolicija (2)

    Po objavi izpred dveh dni je tu še druga (in skoraj gotovo zadnja) objava o napakah knjige Dennisa Shashe Šifre, uganke in zarota. Saj ne, da bi se lahko primerjal s profesorjem Shasho po pedigreju računalniške logike. A se mi vseeno zdi, da je nekaj narobe, če takle ljubiteljski logik brez posebnih težav najde par tovrstnih logičnih napak v knjigi, ki bi po definiciji ravno morala biti brez njih.

    Kakorkoli že, tu je še drugi problem:

    100 tovarn izdela po 100 kosov posameznega sestavnega dela za izdelavo rakete, za katero pa so potrebni sestavni deli iz vseh tovarn. Za končno sestavitev rakete je tako treba doseči, da bo v vsaki tovarni po en kos sestavnega dela iz vsake tovarne, da jih v tovarni sestavijo skupaj, vendar pa zmanjkuje časa in ga je na voljo le 100 ur. Na voljo imate 100 tovornjakov, od katerih lahko vsak naloži do 100 kosov sestavnih delov (vsi so enako veliki), vendar pa med tovarnami lahko potujejo le sorazmerno počasi: med poljubnima dvema tovarnama pridejo v 5 urah, prav tako pa potrebujejo 5 ur, da do poljubne tovarne pridejo od začetnega parkirišča.

    Ali obstaja način, da tovornjaki uspejo sestavne dele razpeljati v 100 urah? (Pri čemer velja, da tovornjaki ne izgubljajo časa s prekladanjem in tudi nimajo premorov, naenkrat pa lahko v eni tovarni nakladata in razkladata dva tovornjaka.)

    14 KOMENTARJI

    1. Sam bi se tega lotil s "simpleks metodo" – lahko da bi brcnil v temo 🙂 – ampak se mi niti pod razno ne da "zezati" s tem :).

      problemi

    2. Anonimni, kot je bilo rečeno pri prvi objavi o cepljenju dlak, si lahko moj odziv o misteriju US preberete v posebni objavi, tu pa se osredotočimo na zastavljeno uganko.

      Problemi, "simpleks metoda" je tudi meni najljubša in pri zastavljeni nalogi človek v bistvu ne potrebuje svinčnika in papirja, zadošča že ena malo daljša avtobusna vožnja v mesto. (Če človeka seveda povsem ne okupirajo reklamni ekrani s sporočili SMS tipa "UCER JE BLO FAAAJN", "MARI MAHA MIHA <3" in "Zakaj se spet nism dost ucila slovooo???".)

      Kar človeka tu res zaskrbi, je Shashina predlagana rešitev naloge. Takole pravi:

      "Osnovna ideja rešitve v 100 urah je preprosta. Vseh 100 tovornjakov mora delovati sočasno. Vsak tovornjak najprej pelje v 10 tovarn. V vsaki izmed njih si naloži 10 kopij tamkajšnjih proizvodov. Po desetih obiskih je tovornjak polno naložen in prevaža po 10 kopij 10 različnih proizvodov. V drugi fazi tovornjak znova obišče 10 tovarn in tokrat v vsaki odloži po eno kopijo vsakega od 10 proizvodov, ki jih ima. Če na tak način prevaža vseh 100 tovornjakov, bo potreben le en tak krog in v vsaki tovarni bomo naenkrat potrebovali le en prostor za nakladanje in razkladanje tovornjaka."

      Rešitev je potem ponovljena še z enačbami, ki pojasnijo, da je seveda treba paziti le na to, da tovornjaki obiščejo "pravih" 10 tovarn, da 10 različno naloženih tovornjakov obišče 10 istih tovarn in tako v vsaki na koncu najdemo po eno kopijo vsakega izmed 100 proizvodov.

      A vendarle lahko na rešitev rečemo le: Shasha, a s to rešitvijo ti misliš resno?*

      Ali lahko najdete boljšo rešitev?

      (*Očitno res, kajti "matematični genij dr. Jacob Ecco" v knjigi prof. Scarletu zastavi še dodatno vprašanje: "Koliko tovornjakov bi potreboval, da bi opravil delo v 40 urah? Predpostavi, da lahko v vsaki tovarni naenkrat natovarja in raztovarja 20 tovornjakov."

      Ponujeni odgovor? "[N]ajboljši način, ki s[e] ga je zmogel domisliti Ecco", potrebuje 1500 tovornjakov. Ja, 1500.)

    3. Matej, mislim, da si predlog reševanja s "simpleks metodo" narobe razumel (no, razen, če je šlo za šaljivo pripombo). Simpleks je čisto prava matematična metoda (algoritem) za reševanje problemov linearnega programiranja, med katere spadajo tudi transportni problemi.

    4. Sam sem mislil na "simpleks metodo", kot jo je zgoraj opredelil shrink. Povsem resno sem mislil, vendar kolikor sem sam delal s to metodo in pretežno ravno na "transportnih problemih" je precej zamudna. Seveda govorim za primer, da se zgornjega primera lotiš "peš".

      problemi

    5. Shrink je kar zadel – metode simpleks ne poznam (kot nemara še marsikatere matematične metode ne) in sem mislil, da gre za malo nenavadno poimenovanje metode sanae mentis rusticorum (=zdrave kmečke pameti) oziroma navdahnjenega ugibanja o tem, kaj bi lahko bila prava rešitev. Še toliko bolj zato, ker je bilo govora o brcanju v temo. Pardon in hvala za pojasnilo. 🙂

      Res pa je, da gre za tako brcanje v temo morda tudi pri pravi simpleks metodi, če jo je Shasha uporabil za svoj izračun. Shashina rešitev je namreč hudo potratna – s 100 tovornjaki potrebuje kar 100 ur, oziroma najmanj 95 ur, če je zadnji tovarniški postanek od prvih desetih hkrati tudi prvi postanek v drugem krogu desetih obiskov tovarn.

      Sam sem brez papirja prišel do rešitve, ki vse proizvode razporedi v 40 urah. Nato sem videl, da je z malenkost drugačno potjo do enakega rezultata prišel tudi recenzent knjige Tomaž Cedilnik. V obeh primerih pa sva torej nalogo s 100 tovornjaki uspela opraviti v 40 urah, torej v tistem času, za katerega naj bi Ecco potreboval kar 1500 tovornjakov. Zvečer ali jutri bom obe rešitvi tudi zapisal v novem komentarju, do tedaj pa me lahko prehitite s svojo.

    6. No, vprašanje je, če se gornji problem sploh da zapisati kot linearni program; če se namreč da (nisem poskusil), potem simpleks vselej da optimalno rešitev (za nek izbrani kriterij optimizacije – pri transportnih problemih so ponavadi kriterij transportni stroški).

      Seveda pa verjamem, da se da problem rešiti (tudi) s kako drugo metodo iz nabora metod operacijskih raziskav. Če je Tomaž Cedilnik tisti, za katerega mislim, da je (namreč: matematik), potem je zelo hitro našel pravi način. Nenazadnje bi ga moral tudi Shasha, ki ima PhD iz uporabne matematike.

    7. Shrink, strinjam se, zato sem tudi napisal, da bi lahko brcnil v temo. Imaš pa vsekakor prav, da ti simpleks vselej da optimalno rešitev (kakor tudi metodi "stopalniki" in "modi"). No, moral bi si osvežiti znanje in preveriti ali je v primeru, če je sistem "degeneriran" (vedno) več rešitev.

      Mogoče bi se dalo "poiskali" kriterialno funkcijo (max, min, zgoraj verjetno minimum) tudi za zgornji problem.

      problemi

    8. Tukaj sta obljubljeni rešitvi Tomaža Cedilnika in moje malenkosti (Tomaž Cedilnik je po mojem isti, na katerega misliva oba – v mojem primeru v kontekstu gimnazijskih spominov, čeprav ni ista generacija). Ker sta malo daljši, ju bom objavil vsako v svojem komentarju.

      Cedilnik predlaga najprej tovarne razdeliti na 4 skupine po 25 tovarn, potem pa sledi rešitev v več korakih (pri 2. in 3. vožnji se v knjigi sicer tudi ta rešitev malo zatipka, a se s takim pristopom s popravkom lapsusa vendarle izide).

      1. vožnja: tovornjaki gredo vsak do svoje tovarne.

      nato izvirno po knjižnem besedilu:

      2. vožnja: iz tovarne n peljemo 36 kosov v tovarno (n-8) mod 25. (Iz tovarne 1 v tovarno 18, iz 2 v 19 in tako vse do vožnje iz 25 v 17.) Na koncu ima vsaka tovarna n 36 kosov tovarne (n+8). [To drži, a ni pravi začetek.]

      3. vožnja: izvirno iz tovarne n peljemo 32 delov št. (n+8) mod 25 v tovarno (n-4) mod 25";
      sedaj naj bi imela vsaka tovarna n 4 kose št. n in po 32 kosov št. (n+4), (n+8) in (n+12)."

      [Z opisanima vožnjama ne pridemo do zapisane razporeditve, pač pa je treba v 2. vožnji iz tovarne n v tovarno (n-8) odpeljati 64 kosov št. n, v 3. vožnji pa nato iz tovarne n v tovarno (n-4) 32 kosov št. (n+8) in 32 kosov št. n – s tem pridemo do zaželene razporeditve po 3. vožnji. Naprej pa je rešitev prava:]

      4. vožnja: Iz tovarne n po 16 kosov št. (n+4), (n+8) in (n+12) v tovarno n+2.

      5. vožnja: Iz tovarne n po 8 kosov št. (n+2), (n+4), (n+6), (n+8), (n+10) in (n+12) v tovarno n+1.

      6. vožnja: Iz tovarne n po 4 kose št. 1-12 v tovarne n+13. S tem ima vsaka tovarna po 4 kose vsake tovarne iz svoje četrtine.

      7. vožnja: tovarne 1-25 in 26-50 izmenjajo po 2 kosa vsake tovarne, enako tudi tovarne 51-75 in 76-100.

      8. vožnja: tovarne 1-50 in 51-100 izmenjajo po en kos vsake tovarne in rešitev je na dlani.

      Cedilnik sicer nato še pravi, da le tretja vožnja zahteva, da na en tovornjak naložimo več kot 50 kosov, in nato predlaga alternativno rešitev, da se izognemo tudi taki obremenitvi. (Da v 3. vožnji iz tovarne n peljemo 4 kose št. n in 32 kosov št. (n+8) v tovarno (n-4), nato pa tovarne preštevilčimo n->(n+4) in smo na istem.) Po mojem se to žal ne izide in rešitev v resnici zahteva dve vožnji, v katerih prevažamo po 64 kosov.

      A vsekakor je to že rešitev, ki močno prekaša "matematičnega genija Ecca" oziroma Shasho, ki za rešitev v 40 urah potrebuje kar 1500 tovornjakov.

      Kot rečeno, pa sem sam do rešitve prišel nekoliko drugače – in, rade volje priznam z nasmehom, pri moji pa res ni nikoli potrebe po prevažanju več kot 50 kosov.

    9. Moja rešitev pa gre takole:

      1. vožnja: vsak tovornjak pelje v svojo tovarno.

      2. vožnja: vsak tovornjak pelje 50 kosov tovarne n iz n v n+1 (mod 100) (iz tovarne 1 v tovarno 2, iz tovarne 2 v tovarno 3 in vse do vožnje iz tovarne 100 v tovarno 1).

      3. vožnja: tovornjaki peljejo po 25 kosov n in (n-1) v tovarno (n+2) (iz tovarne 1 v tovarno 3, itd.).

      4. vožnja: tovornjaki peljejo po 12 kosov n do (n-3) v tovarno (n+4) (iz tovarne 1 v tovarno 5, itd.).

      5. vožnja: tovornjaki peljejo po 6 kosov n do (n-7) v tovarno (n+8) (iz tovarne 1 v tovarno 8, itd.).

      6. vožnja: tovornjaki peljejo po 3 kose n do (n-15) v tovarno (n+16) (iz tovarne 1 v tovarno 17, itd.). Na tej točki ima vsaka tovarna po 4 kose iz tovarn n do (n-3) in po 3 kose iz tovarn (n-4) do (n-31).

      7. vožnja: tovornjaki peljejo po 1 kos iz tovarn (n-4) do (n-31) in po 2 kosa iz tovarn n do (n-3) v tovarno (n+32) (iz tovarne 1 v tovarno 33, itd.). Na tej točki ima vsaka tovarna po 2 kosa iz tovarn n do (n-35) in po 1 kos iz tovarn (n-36) do (n-63).

      8. vožnja: tovornjaki peljejo po 1 kos iz tovarn n do (n-35) v tovarno (n+64) (iz tovarne 1 v tovarno 65, itd.). In vse tovarne imajo po en kos iz vsake tovarne.

      Na nek način prav lepa rešitev, mar ne? (Ki tudi ne zahteva tistega, kar si je kot dodaten izziv zadal Cedilnik, namreč da bi tovornjaki prevažali več kot 50 kosov.)

      Predvsem pa nalogo reši veliko učinkoviteje kot Shasha, ki za isti rezultat potrebuje vojsko 1500 tovornjakov. Še vedno ne vem, kako se je lahko tako uštel.

    10. Matej, poskusi pobarati Shasho o tem problemu. Morda mu ne bo izpod časti odgovoriti.

      Drugače pa so lahko na videz preprosti problemi zelo trd oreh, vsaj kar se iskanja najboljše rešitve tiče. V tem smislu mi je zanimiv problem kuharja, ki speče n palačink različnih velikosti in jih povsem poljubno razvrsti eno na drugo na krožnik. Vprašanje je sedaj, kolikšno je najmanjše možno število premetavanj palačink, da bodo te razporejene od največje do najmanjše. Verjetno je komu znano, da je ta problem (ki je kar težek) reševal med študijem na Harvardu tudi Bill Gates, katerega rešitev je čez nekaj let objavil en njegov profesor, ki je poslušal razlago.

    11. Shrink, lahko poveš rešitev glede problema "kuhar"?

      V primeru, da bi kuhar poljubno (naključno) že polagal palačinke od največje do najmanjše – zelo majhna verjetnost, pa vendarle – bi bilo najmanjše možno število premetavanj 0. Bi bila naloga že opravljena:).

      problemi

    12. Ha, očitno gre za tole nalogo, išče pa se najmanjše število obračanj, pri katerem vedno (tudi iz najslabšega možnega izhodišča) prideš do prave razporeditve.

      Na prvo žogo je očitno, da pri n palačinkah število ni večje od (2n-3), a očitno obstaja še boljša (in zapletenejša) rešitev.

    PUSTITE KOMENTAR

    Vpiši svoj komentar!
    Prosimo vpišite svoje ime

    This site uses Akismet to reduce spam. Learn how your comment data is processed.