
pahaadi-peeth bhoomi vibhajan samasya

fair cake-cutting samasya kaa nimnalikhit sanskaran 1983 mein taid hill dwara pesh kiya gayaa thaa.
aine" deshon key nikat ack kshetra "dee" haye. pratyek desh "dee" key vibhinn upasamuchchay koo alag-alag roop seey mahatva detaa haye. desh "dee" koo unake beach uchit roop seey vibhajit karna chaahenge, jahaan "fair" kaa arth haye aanupaatik vibhajan. isake alawa, "pratyek desh koo aavantit hissa usa desh seey judaa honah chaahiye aur usase satey honah chaahiye. yeh bhaugolik baadha iss samasya koo paaramparik fair cake-cutting seey alag karati haye.
aupchaarik roop seey, pratyek desh "see" koo "dee" kaa ack alag tukada praapt karna chaahiye, jise "dee" chihnit kiya gayaa haye, jaise kii "see" aur "dee" key beach kii seema kaa ack hissa "see ≤ dee" key aantarik bhaag mein nihit hoe.
asambhavata aur sambhavana.
aise mamle hain jinamen samasya kaa samadhan naheen kiya jaa sakata haih
1983 mein, pahaadi ney saabit kiya kii yadi "dee" mein pratyek bindu kaa moolya sabhi deshon key liye 0 haye, aur "dee" kii seema kaa moolya sabhi deshon key liye 0 haye, tou aasann baadha key saath ack aanupaatik vibhajan maujood haye. unakaa pramaan kewal astitvagat thaa-koee algorithm varnit naheen thaa.
algorithm.
4 saal baad, anatol beck ney iss tarah key vibhajan koo praapt karane key liye ack protocol kaa varnan kiya. sankshep mein, protocol antim ghataane vaale protocol kaa ack vistaar haye. yeh deshon koo "dee" key kuchh hisson key liye bolly lagaane detaa haye, apane bolidata koo sabse chhoti bolly detaa haye aur shesh "aine"-1 deshon key beach vibhajit kartaa haye. yeh sunishchit karane key liye kii nikatata baadha santusht haye, kuchh bhinnataon kii aavashyakta hoti haye.
saralata seey judaa huaa kshetra.
jaba "dee" saralata seey judaa hotaa haye, tou nimnalikhit algorithm kaa upayog kiya jaataa haye.
1. ack reeman maanchitran "aich" khojen joe ikai disk key liye "dee" kaa maanchitran kartaa haye, jaise kii sabhi deshon key liye, mool parr kendrit pratyek vritt kaa moolya 0 haye aur mool seey pratyek trijya kaa moolya 0 haye (iss tarah key "aich" kaa astitva ack ginati tark dwara saabit hotaa haye).
2. pratyek desh koo ikai disk maanchitra "aich" ("dee") parr, 1/"aine" key moolya key saath mool parr kendrit ack disk kheenchane key liye kahein. yeh iss shart key kaaran sambhav haye kii mool parr kendrit sabhi vritton kaa moolya 0 haye.
3. disk "d" 1 koo sabse chhoti trijya key saath khojen, "r" 1.
dou mamle hain.
ekal vijeta.
4. yadi "dee" 1 kewal ack desh dwara kheencha gayaa thaa, tou kahein "see", tou iss disk koo "see" koo dein. anya deshon key liye iska moolya 1/"aine" seey cumm haye, isaliye humm "see. aaee" koo isake aavantit disk seey jodane vaalaa ack chhota atirikt tukada dey sakate hain. 
aisaa karane key liye, "see" aur "dee" key beach kii seema kii chhavi seey "dee" 1 koo jodane vaalaa ack kshetra banaaen. pratyek desh ("see. aaee". key alawa) iss kshetra koo iss tarah seey chhaanten kii sabhi desh disk aur kshetra key sangh koo adhikatam 1/"aine" key roop mein mahatva dein. yeh iss shart key kaaran sambhav haye kii mool seey sabhi trijyon kaa moolya 0 haye. "see" koo "dee" 1 aur chhantaai kiye gaye kshetra key sangh koo aavantit karein. 
shesh saralata seey judaa huaa haye aur shesh "aine"-1 deshon key liye cumm seey cumm ("aine"-1)/"aine" kaa moolya haye, isaliye vibhajan charan 1 mein punaraavarti roop seey aage badh sakata haye.
kaee vijeta.
yadi "dee" 1 "key" key "> 1 deshon dwara kheencha gayaa thaa, tou ack aise desh koo khojane key liye kuchh aur parishkrit nilamiyon kii aavashyakta hoti haye jise humm ack disk aur ack jodane vaalaa kshetra dey sakate hain.
5. ack manmana vijeta desh chunein aur ise "ghoshanakar", "see" 1 kahein. ise apane vartamaan kshetra seey "dee" 1 koo jodane vaale kshetra koo jodane dein, aur anya deshon koo usa kshetra koo iss tarah seey trim karane dein kih
6. pratyek vijeta desh koo ack naee trijya "aar" (apani pahali bolly seey chhoti) kii bolly lagaane dein, jaise kii chhantaai kiye gaye kshetra kaa moolya aur trijya "aar" kii disk bilkul 1/"aine" hoe. iss tarah kii sabse chhoti disk kaa chayan karein, "dee" 2. phir seey dou mamle hainh
yadi "c" 1 bolly lagaane vaale deshon mein seey ack haye "d" 2, tou ise "d" 2 (joe mool "d" 1 seey thodaa chhota haye) aur jodane vaalaa kshetra dein. "see" 1 sahmat huaa kii moolya 1/"" aine "" haye aur anya desh sahmat hue kii yeh adhikatam 1/"" aine "" haye, isaliye humm charan 1 parr punaraavarti roop seey aage badh sakate hain. 
anyatha, "c" 1 sahmat haye kii "d" 2 kaa kull moolya aur jodane vaalaa kshetra 1/"n" seey cumm haye. sabhi gair-vijetaon koo bhee iss parr sahmat honah chaahiye kyonki "dee" 2 "dee" 1 seey chhota haye. isaliye "see" 1 aur anya sabhi desh joe iss parr sahmat hain, unhein vijetaon key samooh seey hataa diyaa jaataa haye.
7. shesh vijetaon mein seey, ack nayaa ghoshanakar "see" 2 chunein. ise apane vartamaan kshetra mein "dee" 2 koo jodane vaalaa ack aur kshetra jodane dein, aur anya deshon koo usa kshetra koo charan 5 key roop mein trim karane dein. 
dhyaan dein kii abb "dee" 2 dou alag-alag kshetron seey judaa huaa haye-"see" 1 aur "see" 2. yeh ack samasya haye kyonki yeh shesh kshetra koo disconnect curr detaa haye. ise hull karane key liye, "see" 2 koo ack anya kshetra lene kii anumati haye, iss samay kii lambai 1 seey cumm haye taaki yeh sampark koo nuksan naa pahunchaae. usa teesare kshetra koo phir seey sabhi deshon dwara charan 5 key roop mein chhantani kii jaati haye. badale mein, "see" 2 koo "dee" 2 seey "see" 1 koo jodane vaale kshetra key kuchh hisse koo chhodane kii aavashyakta hoti haye, jiska moolya praapt teesare kshetra key moolya key barabar haye. 
"see" "2 key ummidwar aavantan mein abb nimnalikhit bhaag hainh" "dee" "2, lambai 1 kaa ack kshetra joe" "dee" "2 seey" "see" "2 koo jodata haye, aur dou chhote kshetra joe" "dee" "kii seema taka naheen pahunchate hain. see" 2 key liye iss nirmaan kaa moolya 1/"aine" haye, gair-vijetaon key liye iska moolya 1/"aine" seey cumm haye, aur shesh vijetaon key liye iska moolya adhikatam 1/"aine" haye.
yeh prakriya shesh vijetaon key saath taba taka jaari rahati haye jaba taka kii kewal ack vijeta naheen reh jaataa.
parimit roop seey judaa huaa kshetra.
yadi kshetra "d" "k" haye-ack seemit "k" key saath judaa huaa haye, tou vibhajan "k" parr preran dwara aage badh sakata haye.
jaba "k" = 1 ", d" saralata seey judaa huaa haye aur pichhale khand key protocol dwara vibhajit kiya jaa sakata haye.
anyatha ("key"> 1), "dee" kii baahari seema koo "bee" 1 seey aur isaki aantarik seemaon koo "bee" 2 seey chihnit karein..., bee" "key".
baahari seema "b" 1 koo aantarik seema "b" k "seey jodane vaali ack rekha" l "khojen, jaise kii sabhi desh" l "koo 0 key roop mein maan dete hain. yeh nimnalikhit ginati tark seey sambhav haye. b" 1 aur "b" k "koo jodane vaali jodeedaar-vichhed rekhaaon kii ack anginat anantata haye aur" d "mein nihit haye. lekin "dee" kaa maap seemit haye, isaliye ack sakaratmak maap key saath rekhaaon kii sankhya seemit honey chaahiye.
d"\"l" sett ("k" −1)-judaa huaa haye. ise punaraavarti roop seey vibhajit karein, phir isake buggle mein kissy bhee desh koo manmaane dhang seey "l" nirdhaarit karein. yeh aavantan kii nishpakshata koo prabhaavit naheen kartaa haye kyonki sabhi deshon key liye "l" kaa moolya 0 haye.