ACM中很多問題，不僅僅是博弈問題，都會涉及到解空間的結構的問題。
了解解空間結構，對于了解問題的本質，非常重要。
放硬幣問題：
有一個圓桌，2人輪流在上面放硬幣。硬幣可以放在桌面上的任何地方，但是不能超出桌面的范圍（極端情況是內切）
而且，硬幣和硬幣不能互相重合（極端情況是外切）
只要桌面上還能繼續放，就必須放。如果不能再放，那么游戲結束。
現在定義：最后一個放硬幣的人是勝者，請問誰有必勝策略，必勝策略是什么。
>
一，對可行狀態的說明
有些地方出現的這個題目沒有明確定義，怎么樣才算桌面上可以放硬幣。
有的人自行腦補，只要硬幣放在桌面上不會掉下去即可，還有的人自行腦補，是硬幣被桌面覆蓋。
我這里采用的是后者，但是實際上，因為兩者是一樣的。
假設桌面的半徑是R，硬幣的半徑是r，不用說，R自然比r大很多，雖然這并不影響題目的復雜性，但是會影響敘述答案的繁瑣程度，所以我先說明R比r大很多。
前者（只要硬幣放在桌面上不會掉下去即可）對于可行狀態的定義是，桌面和硬幣的距離不超過R，
后者（硬幣被桌面覆蓋）對于可行狀態的定義是，桌面和硬幣的距離不超過R-r
但是R和r根本沒給，所以到底是哪一種無關緊要。
二，對題目合理性的說明
首先，很明顯這個題目是沒有平局的。
其次，很明顯在有限的（比如[R*R/r/r]，[]是高斯函數）步數之內，博弈必將結束。
所以，肯定有一個人有必勝策略。
（對于中國象棋，是否有一個人有必勝策略目前還未知）
三，分析解空間結構，求出解
這個題目，稍微一想就能發現，解空間的結構炒雞復雜。
我大致能感覺到，解空間是一個無限維的空間。
可惜我不是數學專業的學生，高等代數學的一團糟，這個只是我的推測。
（我所有的博客，里面所有的內容，除了像這樣專門說明的，都是我確定的，而不是猜的，當然，不一定正確）
即使如此，本題的關鍵，仍然是探索解空間結構。
有個十分值得注意的地方，R和r的大小，對于解空間的影響十分巨大，但是題目卻沒有給出來。
這是很奇怪的，除非——解空間存在一個子集，R和r的大小對這個子集沒有影響。
（之所以說子集，而不用子空間這個概念，是因為解空間不是線性空間，我幾乎可以確定，它是沒有非平凡子空間的。）
既然如此，那么答案就呼之欲出了，很容易就能找到這個子集。
答案便是：先手有必勝策略。
必勝策略是：先手首先在桌面正中間放一枚硬幣，然后每次不管后手把硬幣放哪里，先手都把硬幣放在和它成中心對稱的地方。
答案揭曉了，好像沒感覺到解空間結構有什么用，不過，繼續看就不一樣了。
很多博弈問題，將勝負反過來定義，會變得復雜很多，這個問題也是如此。
現在重新定義：如果最后一個放硬幣的人是敗者，請問誰有必勝策略，必勝策略是什么。
要求解這個問題，首先得定義3個概念。
1，閉區域的特征值集合：
（這個特征值大致可以理解為能夠放下的硬幣的數量）
1）如果一個閉區域無法再放硬幣，那么它的特征值集合為{0}
（閉區域要想放下一個硬幣，必須要覆蓋這個硬幣，題目中的桌面就是極大的閉區域）
2）如果一個閉區域可以在一個地方放一個硬幣，那么放下這個硬幣之后剩下的地方仍然是一個閉區域，是原區域的子區域。
閉區域的所有子區域的特征值集合的并集就是這個閉區域的特征值集合。
2，固定區域與不固定區域：
如果一個區域的特征值集合是單元集，那它就是固定區域。否則，它就是不固定區域。
不能發現，不固定區域的特征值集合一定是由連續的整數構成的集合。
3，固定區域的奇偶性：固定區域的特征值集合是單元集，我們用其中唯一的那個元素的奇偶性來定義固定區域的奇偶性。
對于圓這個閉區域來說，如果半徑較小，那就是固定區域，如果半徑較大，那就是不固定區域。
桌面明顯比硬幣大的多，所以是不固定區域。而且不管在哪放一個硬幣，子區域仍然是不固定子區域。
現在關鍵來了，分析解空間。
（從這里開始，區域都特指，桌面在放了若干個硬幣之后得到的子區域。）
不管如何，總會有一個人，某一步操作，將不固定區域變成固定區域。
因為最后將不固定區域變成固定區域的這個人，可以控制這個固定區域的奇偶性，而奇偶性直接對應了勝負，所以這個人就是勝者。
那么，這個人到底是先手還是后手呢？
很巧，這個人仍然是先手，而且先手的必勝策略幾乎不變。
必勝策略：
首先在桌面正中間放一枚硬幣，
然后每次不管后手把硬幣放哪里，先手都把硬幣放在和它成中心對稱的地方，
最后到了先手將不固定區域變成固定區域的時候，只要選擇一個地方放硬幣，使得子區域為奇區域，那么他就是勝者了。
無論后面每次兩人把硬幣放在哪里，放的數量都是固定的，結果也是固定的。
至此，放硬幣問題就解決了。
就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161116/54138.html
文章列表
留言列表
