試解

結論： 如果n是偶數，至少需要翻轉n次。 如果n是奇數，則多少次都不可能

證明： 以f(k)表示在第k次翻轉後朝上的杯子數, 則f(0)=n, f(1)=n-(n-1)=1. 本題為求最小的整數m使得f(m)=0
考慮任意第k次翻轉的情況，設翻轉的(n-1)個杯子中在翻轉之前有t個是朝上的，則第k次翻轉把t個杯子由朝上變成了朝下，把(n-1-t)個杯子由朝下變成了朝上。朝上杯子數的變化是
   (n-1-t) - t = n-1-2t
即  f(k) = f(k-1) + (n-1-2t)
        = f(k-1） + (n-1) - 2t
因此        
    f(k) ≡ f(k-1) + (n-1)   (mod 2)   

i） 如果n是奇數， 則f(0)=n≡1 (mod 2)
   f(k) ≡ f(k-1) + (n-1) ≡ f(k-1）   (mod 2)
因此對任意整數m 都有 f(m) ≡ f(0) ≡ 1   (mod 2)
f(m)不可能為0

ii) 如果n是偶數, 則f(0)=n≡0 (mod 2)
   f(k)  ≡ f(k-1) + (n-1)
         ≡ f(k-1） + 1  (mod 2)
   故 0 = f（m) ≡ f(m-1)+1 ≡ f(m-2)+2
        ≡ ... ≡ f(0) + m
        ≡ m   (mod 2)
m必為偶數。 設這m次翻轉為 A[1], A[2],... A[m-1], A[m]. 把每兩次翻轉合並為一次變換，得到如下的m/2次"合成變換":
    B[1] = A[1], A[2]
    B[2] = A[3], A[4]
    ...
    B[m/2] = A[m-1], A[m]
注意對每一個B[i]由兩個(n-1)次翻轉組成，它又有如下兩種情況
a)兩個(n-1)次翻轉一模一樣，則B[i]沒有引起任何變化
b)兩次(n-1)次翻轉不一樣，由於總共隻有n個杯子，必有(n-2)個杯子在兩次變換中都被翻轉，剩下的兩個杯子各被翻轉一次。也就是B[i]的總體效果是翻轉了兩個杯子而其餘保持不變。
因為m是最少次數，a)不可能發生，因此每個B[i]都恰好翻轉兩個杯子。 顯然最小的次數是每次都翻轉不同的兩個杯子。總共需要的B變換次數是n/2
   因此  m/2 = n/2
也就是 m=n

所有跟帖： 

• 牛！ -wxcfan123- ♂ (0 bytes) () 04/08/2024 postreply 09:44:19