Nyilván mindenki tudja, hogyan lehet „igazságosan” elosztani egy tortát két ember között. Egyik oszt, másik választ. Az „igazságos” definíciója valami olyasmi, hogy egyik fél sem érezheti úgy, hogy önhibáján kívül a neki járó résznél kevesebbet (helyesebben rosszabbat) kapott. Persze a torta két fele nem lesz ugyanolyan. Az egyiken több a csoki, a másikon több a marcipán, vagy épp a gyertyáról ráolvadt viasz. Tehát nem definiálható egyértelmű objektív sorrend, még az is előfordulhat, hogy az osztozkodás végén mindkét fél úgy ítéli meg, hogy ő kapta a jobb szeletet.
Ezt a problémát három vagy még több emberre is fel lehet tenni, és meg is lehet oldani. Két lényegesen különböző megoldást is ismerek. Persze itt már az is fontos, hogy néhány játékos együtt összejátszva se tudjon kitolni valaki mással.
A mostani feladat valami hasonló, és szintén a való élet szülte.
Hárman együtt keresünk közös albérletet. Találtunk is egyet, ami mindnyájunknak tetszik, és úgy érezzük, az egész lakás megéri a fizetendő összeget. Elhatároztuk tehát, hogy kibéreljük. A közös használatú helyiségeken (előtér, konyha, fürdő és egy nagyobbacska nappali) kívül van három kisebb szoba, tehát mindenkinek jut egy-egy. Ez a három kisebb szoba azonban különbözik méretben, alaprajzban, tájolásban, kilátásban, és természetesen szubjektíven is mindnyájunknak mindegyik más-más mértékben tetszik. Sőt, egyikünk például semmiképp sem szeretne a legkisebb szobába költözni, mert azt túl kicsinek tartja. A feladat kitalálni egy algoritmust, amelyik eldönti, hogy ki melyik szobába kerül, és cserébe mekkora részt fizet a bérleti díjból. Az algoritmussal szemben támasztott kritérium nagyjából az, ami a tortás feladatnál volt: senki se érezhesse úgy, hogy annyit fizet a neki jutott szobáért (és persze a közös helyiségek megosztott használatáért), amennyit neki az nem ér meg.
Ha valakinek ez nem eléggé formális specifikáció (merthogy tényleg nem az), akkor számára a formális specifikáció helyes megalkotása is a feladat részét képezi.
Várom az ötleteket :-)
Feliratkozás:
Megjegyzések küldése (Atom)
11 megjegyzés:
Mindenki mond mindegyik szobara egy 0 es 1 kozotti erteket, hogy a berleti dij hanyad reszet lenne hajlando fizetni azert cserebe hogy o abban a szobaban lakhasson/kelljen laknia.
(Persze nem is kell hogy 0 es 1 koze essen a szam, de azert ugy normalis ha igen :)
Kivalasztjatok azt a beosztas kombinaciot amikor ezen szamok osszege a legnagyobb. Ha ez nagyobb mint 1, akkor boldogsag van, lenormaljatok 1-re es mindenki orulhet mert meg kevesebbol meg is uszta mint amit raszant volna.
Ha az osszeg kevesebb mint 1, akkor szivas van. Vagy felnormaljatok 1-re es mindenki elfogadja, vagy uj szavazas. Ha tobb szavazas utan sincs eredmeny, akkor mas lakas utan neztek :)
Azt meg nem dolgoztam ki, hogy a kiindulasi ertekeket hogyan kellene egymassal kozolni, de szerintem mindenki felirja egy papirra, aztan osszevetitek.
Érdekes, szinte mindenki arra indul el, amerre te is. Ha a felírt 0-1 közti számoktól elvárjuk, hogy 1 legyen az összegük (amit ugyebár elvárunk), akkor asszem nem fordulhat elő, hogy a 6 lehetséges szobabeosztásra kalkulált összegek közül a legnagyobb is 1 alatt legyen. Vagy mégis? Mindjárt végiggondolom...
Végiggondoltam. Persze hogy nem fordulhat elő.
Akkor tehat megvan az algoritmus? :)
Nem gondoltam ra hogy elvarjuk hogy az osszeg 1 legyen. Ha csak annyit tudtok pl hogy 3an szeretnetek egy lakasban lakni, akkor lehet hogy valakinek igazabol egyik szoba sem tetszik, es akkor nem fair megkovetelni az 1-es osszeget. Szoval szerintem nem egyertelmuen jo ez a szabaly, de sokat egyszerusit.
Kivancsian varom a vegeredmenyt, es a szamokra is nagyon kivancsi lennek!
Ha nem követeled meg, hogy 1 legyen az összeg, akkor mindenki írhat csupa nullát is, és akkor a végén semmit sem fizet. Ezzel kábé azt fejezi ki, hogy neki egyik szoba sem tetszik. Akkor meg keresünk másik lakótársat helyette :-)
Szóval az a kiindulási szitu, hogy nagyjából mindenkinek tetszik a lakás, mindenki szívesen lakna itt, persze azon belül szeretne minél nagyobb szobát kapni minél kevesebb pénzért.
A számokra én is kíváncsi leszek. Majd beszámolok az eredményről.
Lenyegeben ugyanez a megoldas, azaz: ha mind a h�rman ugyanazt szeretitek a legjobban, akkor arverest kell rendezni, az indul�s: 33.33%. A gyoztes - mondjuk - p %-ot ad. Ekkor ketten a masodikert arvereztek: az indulas: (100-p)/2. Ha netan mindketten pl. (100-p) %-ot is megadnatok, akkor Monte Carlo modszer, azaz sorsolas. Avagy: sportosabb megoldas: lementek a grundra es 11-es rugasokkal eldontitek!
Hmm.De azt se felejtsétek el, hogy a fűtés számlára is ki kell találni algoritmust, mert azért a kisebb szobát könnyebb kifűteni:)))
Valamint gyakorlati kérdésként felmerült bennem, hogy a hűtőt is a szobák mérete alapján fogjátok felosztani? ;) (Még egy pár eszembe jutott, de attól megkíméllek;)
Minek ide matematika. Tudjátok a ruszkik ceruzát használtak az űrben.:)
Egyszerűen csak meghatározott időnként mindenki átköltözik másik szobába, és minden költséget harmadoltok.
Jó feladat, bár Szindbád az első jónéhány lakást elengedte volna az orra előtt (mennyit is?).
Persze a tiszta versenyhelyzet (két ember csakis a nagy szobát akarja) nem fog eldőlni az algoritmussal, ott jön a B terv, fej vagy írás. Pénztelenek kedvéért: kő-papír-olló.
apu: vicces login nevet választottál. Valami azt súgja, hogy nem sok másik ember blogjába tervezel megjegyzést írni ;-)
apu és zormac: ilyen típusú sorsolásra nyilván nem kerül sor, senki nem olyan hülye közülünk, hogy sok pénzért a nagyobbik szobába akarjon menni, ha szinte ingyen megkaphatja a kisebbet (plusz természetesen a közös helyiségek használatát).
mimke: a fűtés tudtommal benne van az árban, viszont jöhetnek egyéb ötletek, fölmerült például az is, hogy lehet a közös helyiségek takarításával is beszállni a versenybe.
dole: a lakás bútorozatlan, mindenki magának fogja berendezni a saját szobáját, figyelembe véve az adottságokat. De szerintem még ha mindegyikben lenne szekrény, polc, ágy, asztal, TV, akkor sem lenne kedvünk rendszeresen áthurcolkodni. Egyébként nem sikerült kitalálnom, hogy ki vagy, pedig kíváncsi lennék :-)
zormac: eddig egy lakást engedtünk el az orrunk előtt, ami pont eggyel efölött volt. A kilátás ott végtelenszer szebb lett volna (onnan átlátni a szomszéd házak teteje fölött nagyon messzire, innen csak a szomszéd házak felső szintjét látni), viszont a belső beosztása nem volt ennyire jó, ott még azt sem sikerült használhatóan kitalálni, hogy melyek legyenek a hálószobák és melyik a nappali. Egyébként is egyes vélemények szerint ha este 11-re érünk haza a munkából, akkor nem tök mindegy hogy milyen a kilátás? :-)
Egyszer találkoztunk és pár mondat erejéig dumáltunk az első csomagoló partin. Olyan kuksoló, nem túlságosan sokat dumáló, Linux power user vagyok.. Az egyszerűbb utak keresője...:)
Még valami, valamikor réges-régen a kilencvenes évek elején én is voltam a svájci hegyekben, a haverok állították, hogy ameddig aludtam láttak enyhén lilás árnyalatú tehenet. _Na ez azóta bizgeti a fantáziám, én csak muskátlit láttam ebben a színben, ha ennek utána járnál, eléggé sok mindent megmagyarázna. Egy kicsit közelebb vagy a tűzhöz. :)
Megjegyzés küldése