试解

结论： 如果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