Question

【題目】甲乙兩人作游戲，甲先在紙上任意寫下一個由L、R構(gòu)成的長為的序列，然后乙將個質(zhì)量互不相同的砝碼逐一放在天平上，每放一個砝碼(已放的砝碼不再拿下)，乙都在紙上按順序?qū)懸粋�字母：如果天平傾向左邊則寫L，否則寫R．當(dāng)所有砝碼都放在天平上時，乙也寫下一個由L、R構(gòu)成的長為的序列．規(guī)定：當(dāng)乙寫的序列與甲寫的序列相同時乙勝，否則甲勝．試問：誰有必勝策略?

Answer 1

【答案】乙有必勝策略

【解析】

記個砝碼的質(zhì)量依次為 設(shè)甲寫的序列為A．下面證明：乙有辦法寫下序列．不妨設(shè)的最后一項為，且為偶數(shù).乙的策略滿足如下要求： (1)任何時刻天平上砝碼的下標(biāo)都是連續(xù)的自然數(shù)； (2)偶下標(biāo)砝碼放在天平的左邊，奇下標(biāo)砝碼放在天平的右邊．由以上兩點知，任何時刻天平總是傾斜向含有最重砝碼的那一邊．此外，還滿足：(3)序列從某項到下一項改變字母天平從某個砝碼到加下一個砝碼改變傾斜方向新放的是一個比已放的都重的砝碼；序列從某項到下一項不改變字母天平從某個砝碼到加下一個砝碼不改變傾斜方向新放的是一個比已放的都輕的砝碼．這樣一來，乙可按下述規(guī)則將砝碼排列順序：從最后一項開始逆向往前排，當(dāng)排列右起第個砝碼時，如果序列的右起第項與它左邊一項不同，則排剩下的最重的砝碼，否則，排剩下的最輕的砝碼(如，則砝碼排列的順序是)．現(xiàn)在，按從左向右的順序依次將砝碼放在天平上，且下標(biāo)為偶數(shù)的砝碼都放在天平的左邊，下標(biāo)為奇數(shù)的砝碼都放在天平的右邊，則此放法對應(yīng)寫下的序列恰好為．