تقسيم كيك

من علاقه مند هستم كه درستي الگوريتم هاي زير را به كمك منطق بازي ها ثابت كنم. دانشجويان علاقه مند به من مراجعه كنند



فرض كنيم مي خواهيم كه يك كيك عادلانه بين n نفر تقسيم شود. الگوريتمهاي زير نمونه اي از الگوريتم هاي چند عاملي براي n=3 هستند.


تعريف: گوييم يك تقسيم كيك بين n عامل عادلانه است هرگاه هر عامل باور داشته باشد كه حداقل يك nام كيك به او رسيده است.



الگوريتم زير عادلانه بودن تقسيم را برآورده مي­كند.

1- ابتدا بازيكن 1 كيك را به دو قسمت مساوي از لحاظ خود تقسيم مي­كند (فرض كنيد a1,a2 )

2- بازيكن 2 يكي از دو قسمت­ را كه از لحاظ خود از ديگري بزرگتر است براي خود بر مي­دارد (فرض كنيد a2 را برداشته است)

3- بازيكن­ 1 قسمت خود را به 3 قسمت مساوي از لحاظ تقسيم مي­كند (فرض كنيد a11,a12,a13)

4- بازيكن 2 قسمت خود را به 3 قسمت مساوي از لحاظ خود تقسيم مي­كند (فرض كنيد a21,a22,a23)

5- بازيكن 3 از 3 قسمت a11,a12,a13 بزرگترين قسمت از لحاظ خود را بر­مي دارد. (فرض كنيد a12)

6- بازيكن 3 از 3 قسمت a21,a22,a23 بزرگترين قسمت از لحاظ خود را بر­مي دارد. (فرض كنيد a21 )


بعد از انجام الگوريتم بازيكن 1 قسمت­هاي a11,a13، بازيكن 2 قسمت­هاي a22,a23 و بازيكن 3 قسمت­هاي a12,a21 را خواهد داشت.




تعريف: گوييم يك تقسيم كيك بين n عامل از حسادت آزاد است هرگاه هيچ عاملي به عاملي ديگر حسادت نكند.




الگوريتم زير به يك تقسيم حسادت آزاد منجر مي­شود. خوب بود اگر نويسنده پايان­نامه بتواند بصورت فرمال اين موضوع را ثابت كند.

1. بازيكن اول كيك را به سه قسمت a1,a2,a3 از لحاظ خود مساوي تقسيم مي­كند.

2. بازيكن دوم سه قسمت تقسيم شده را از لحاظ خود از بزرگ به كوچك مرتب مي­كند. فرض كنيد a1>a2>a3 . سپس تكهe>=0 را طوري از a1 جدا مي­كند كه a'1=a1-e=a2 شود.

3. بازيكن سوم از بين تكه­هاي a'1,a2,,a3 تكه بزرگتر از لحاظ را انتخاب مي­كند و براي خود بر مي­دارد.

4. اگر بازيكن سوم را a'1 بر ندارد a'1 به بازيكن دوم داده مي­شود و تكه ديگر باقيمانده (از سه تكه a'1,a2,,a3) به بازيكن اول داده مي­شود. اگر بازيكن سوم a'1 را بردارد، بازيكن دوم از بين دو قسمت ديگر بزرگترين را از لحاظ خود انتخاب مي­كند و براي خود بر مي­دارد. تكه ديگر باقيمانده نيز به بازيكن اول داده مي­شود.

5. بعد از اجراي 4، يا بازيكن دوم يا بازيكن سوم a'1 را دارد. آن بازيكني كه a'1 را دارد بازيكن P1 و بازيكن ديگر (از بين بازيكن­هاي دوم و سوم) را بازيكن P2 بناميد.

6. بازيكن P2 قسمت e را به سه قسمت از لحاظ خود مساوي تقسيم مي­كند و بازيكن­ P1 ، بازيكن اول و بازيكن P2 به ترتيب هر يك، يك قسمت را براي خود بر مي­دارد.




تا آنجا كه من مي­دانم الگوريتم حسادت آزاد براي تقسيم بين n>=5 عامل هنوز معرفي نشده است. اين موضوع مي­تواند به عنوان يك پژوهش در نظر گرفته شود كه آيا منطق به پيدا كردن اين الگوريتم­ها كمك كند. آيا مي­توان وجود يا عدم وجود اين الگوريتم­ها را ثابت كرد.