(更新至5/5.)
1.
熟知的問題,有些細節根據定義不同差異太多..舉些栗子..
某人"滿意"可以指"認為自己最多",也可以指"認為自己達到均值".
像兩人分,一人分一人挑就可以認為兩個都滿足.
下面說些N人的:(還是說成切蛋糕順口..)
- 不斷將液體倒到某杯中/刀在蛋糕上逐漸移動/...,直到有人認為到均值喊停,分給ta.
這個可以符合"達到均值"的要求,但不符合"自己最多"的要求.同時,需要額外的設定:分出的一部分的數量可以連續變化.(關于這點..這么說吧..通常是假設要多少就能切出多少,但沒有假設這個數量可以連續變化.) - 另一個方法,從整塊開始,第一人到最后一人依次看剩的是否夠均值,若有多則削剩均值.最后,這塊歸最后一個動的人所有.
同樣,這個也只是符合"認為自己達到均值"而不符合"認為自己最多". - 再說一個方法,也是"達到均值"的版本.
第一人分成2份,第二人選認為不少的一份.此時兩人都認為自己有至少1/2.
前兩人將自己的分成3份,第三人從兩人處各取一份,這樣三人都認為自己至少有1/3.
前三人將自己的分成4份,第四人從三人處各取一份,這樣三人都認為自己至少有1/4.
...
重復N次即可. - 最后再說一個三人的免嫉妒分割 (envy-free division)(也就是"認為自己最多"的版本)的方法Selfridge-Conway算法.比較長,直接復制粘貼吧..反正估計沒多少人細看....
首先，A 把蛋糕分成三等份（當然是按照自己的看法來分的，后面提到的切分、選取也都是這樣）。如果 B 認為這三塊蛋糕中較大的兩塊是一樣大的，那么按照 C、B、A 的順序依次選取蛋糕，問題就解決了。麻煩就麻煩在 B 認為較大的兩塊蛋糕不一樣大的情況。此時，B 就把最大的那塊蛋糕的其中一小部分切下來，讓剩余的部分和第二大的蛋糕一樣大。被切除的部分暫時扔在一旁，在第二輪分割時再來處理。接下來，按照 C、B、A 的順序依次選蛋糕，但有一個限制：如果 C 沒有選那塊被修剪過的蛋糕，B 就必須選它。
這樣，三人就各分得了一塊蛋糕。由于 A 是切蛋糕的人，對于他來說拿到哪一塊都一樣，因此 A 不會嫉妒別人。由于 B 選取的是兩個較大塊中的一個，因此 B 也不會嫉妒別人。由于 C 是第一個選蛋糕的，顯然他也不會嫉妒別人。因此，就目前來說，三個人之間是不會有嫉妒發生的。
但是，還有一小塊被切除的部分沒分完，因此分割流程進入第二輪。
在 B 和 C 之間，一定有一個人選擇了那塊被修剪過的蛋糕。不妨把這個人重新記作 X，另一個人就記作 Y。讓 Y 把最后那一小塊分成三等份，按照 X、A、Y 的順序依次挑選蛋糕，結束第二輪流程。這一輪結束后，每個人都又得到了一小塊蛋糕。由于 X 是第一個選蛋糕的人，X 顯然不會嫉妒別人；由于 Y 是分蛋糕的人，Y 也不會嫉妒別人。由于 A 比 Y 先選，A 不會嫉妒 Y。最后，A 也是不會嫉妒 X 的，因為即使 X 擁有了第二輪中的全部蛋糕，X 手里的蛋糕加起來也只是第一輪開始時 A 等分出來的其中一塊蛋糕，這是不可能超過 A 的。這就說明了，三個人之間仍然不會有嫉妒發生，Selfridge-Conway 算法的確滿足免嫉妒條件。
這就說完了.至于免嫉妒分割的N人版本(N>3),還沒有結論.記得在猴子的貼里這些也都說過了.
2.
熟知的二進制.
首先要假設的是我們的做法:取若干瓶各少許混合給一只老鼠喝,對不同老鼠選法不同,需要的是設計選法使得能從死了哪些老鼠判斷出哪瓶有毒.
顯然,總共N只老鼠,每只都有死和不死兩種可能,那么總共至多能分辨2^N種可能性,也就是酒的瓶數不超過2^N.
而熟知這個界是可以達到的,而且做法唯一(或者說等價):給酒編號0到2^N-1,對其中每個數,二進表示中哪些數位是1,就給哪些老鼠喝;也就是說,將這2^N個數中某位為1的所有酒(取少許)混合后給對應的老鼠喝.
顯然,老鼠死說明毒酒此位為1,于是用01表示老鼠是否死了,串起來就是毒酒編號.
ps.這里N=16,那么答案是2^16=65536.
3.
再一次,題目敘述不清.明明問的是有多少種幾種坐法,答案就是N!.但是又明確表示"連續兩回合不能坐同一張椅子",全然看不懂這和問題有啥關系.(應該說,我只能明確看出題目肯定有表述問題.)
反正據我猜測,出題人的意思可能是"某一輪都坐成功了,問下一輪有多少坐法".
如果真的是這個意思,那這就是熟知的bernoulli錯排問題/放錯信箋問題/...,答案是N!(1/2!-1/3!+1/4!-...±1/N!),證明的話直接容斥原理然后化簡下就好了,不贅述.也有遞推的版本,同樣,反正想知道的問度娘.
ps.這里N=8,那么答案是14833.
ps2.看到lz前邊認為正確的答案也是14833,說明我這個題意猜測應該是對的.
4.
熟知,八卦貫石.
掛八卦貫石,殺.若不護駕直接死,否則二位郭嘉先護駕,開八卦,拿天妒牌和八卦兩張用貫石補中.
甄姬忠臣只能護駕和無懈而不能給桃,故對貫石補中沒辦法;沒用錦囊,故無懈也沒用.
5.
熟知的結論是98,0,1,0,1,也就是能分到98.
如下考慮:如果僅剩45兩人,4全給4自己然后自己同意即可,所以123死的話5啥都得不到.
所以3提方案的時候無論如何2會反對,而只要給5東西5就會同意.
...
以下同理,略.
剛才沒看清,現在看清了.又有表述問題..這次我不猜原意了..
第一句是"當且僅當達到半數或者超過半數的人同意時"
第二句是"當且僅當超過半數的人同意時"
差異這么大,還怎么以次類推??
好吧..題目改了..那就沒事了..
================ 以上據說只是背景的不是題目的 ================
================ 以下的才是題目的 ================
我又想吐槽題目了..如果三個人的方案都沒通過怎么辦?連這都沒提到還讓人怎么玩??
"如果違反任何協議就會損失300枚金幣的公證處門前"只是描述那個公證處這樣而已,跟三人有個喵關系吖??
退一萬步講,就算是跟三人有關系,那三人現在又不是在定啥協議,結果還是木有個喵關系吖?!
再退一萬步講,如果這些 提方案 算是協議的話,那為了用這條件,是不是說"他啥都不分給我,可我已經同意了.可我突然又暴起弄死了他們倆搶走了那300塊錢,所以我算是'違反了協議',所以300塊錢又要被沒收"??
既然lz提到liar game..大概也許想學里頭那樣玩支票吧..
hmm..匯報最新進展..私下已使用協議將題目玩崩....隨便搞幾個自涉就悖論了....還有什么"支持我我保證不打死你""支持我我做你仆人"或者簡單的公證個欠條什么的..也完全無法衡量不同方案了吖- -
本帖最后由 天馬行空 于 2014-11-13 16:08 編輯 |
