Question

7、A，B兩人玩一個游戲，A提供若干硬幣，B可以任意將這些硬幣全部擺放在頂點上，并確定一個目標(biāo)頂點u．規(guī)則是：A可以選擇一個上面至少有兩枚硬幣的頂點v，并選擇一個與它相鄰的頂點w，將v上的兩枚硬幣取走，并放回一枚硬幣在w上．A若在有限步內(nèi)根據(jù)規(guī)則在u上放上一個硬幣則獲勝．已知B不想讓A贏且他很聰明，試問在這兩種情況下A各需要至少幾個硬幣才能保證自己能贏．

Answer 1

分析：先判斷出B選的頂點u，v；為了最后放到u上硬幣，得到各個頂點需要有的硬幣個數(shù)，得到需要至少幾個硬幣

解答：解：∵B不想讓A贏且他很聰明
∴當(dāng)頂點在一條直線上時，B將目標(biāo)頂點u選在最右邊，將所有硬幣放在最左邊

為最后放在u上硬幣，則?3處需2枚硬幣；?2處需4枚硬幣；需?1處有8枚；v處有16枚
故當(dāng)頂點在一條直線上時需要至少16個硬幣才能保證自己能贏
當(dāng)頂點在一圓上時，
B不想讓A贏且他很聰明
所有B選的u，v將所有硬幣放在最v上
如圖所示

為最后放在u上硬幣，則?2處需2枚硬幣；需?1處有4枚；v處有8枚
故當(dāng)頂點在圓上時需要至少8個硬幣才能保證自己能贏

點評：本題考查需要根據(jù)實際情況，判斷出頂點U，V；判斷出各個點上最少的硬幣數(shù)．