翻硬币问题精

1、翻硬币问题桌面上有n枚硬币，初态是全部正面向上，现让你每轮把其中的 (2mw n)枚翻转，希望最终全部反面向上.请建立数学模型研究n,在什么条件下此问题有解或无解 .解答：1. 概念与性质定义：纯翻转m个都是正面的一轮翻转；(混合)翻转 取a (>0)个正面，m-a个反面的一轮翻转. 显然，纯翻转是混合翻转的特例(a=m).设n = sm t ,(i)其中，t为n除以m的余数，0咗t：；m, s为正整数.记变量k表示当前的正面数.显然，从开始，经过 s轮纯翻转后k=t;当k=0时，就成功了 .性质1.选a个正面和m-a个反面的一轮翻转后，正面数的变化 量为.k = m - 2a , (2

2、)特别是，做纯翻转时，丄k =m.性质2.当k(<2m)为偶数时，只需再翻两轮必会成功.证明：若k=m ,则做一轮纯翻转必成功.若k = m，则先选k/2个正面和m-k/2个反面做一轮翻转，(注：因 2m<n<2n-k,故 2m<2n-k, 2m-k<2n-2k, m-k/2<n-k, n-k 是反面数，即这样选取是可行的.)则翻转后的正面数k k k 二 k (m - k)二 m再做一轮纯翻转，k 0，就成功了 .因为k - m时，只翻一轮必定未能成功，故翻两轮必是最佳方法(轮数最少)2. 情形一，m是奇数(不论n是奇数还是偶数).先做s-1轮纯翻转，得k

3、=m+t.只有如下3种可能：(i) t=0. k=m,再做一轮纯翻转就成功.(ii) t (<m)是奇数.k已是偶数，且 m<k<2m.由性质2,只需再翻两轮必会成功.(iii) t (<m)是偶数.再做一轮纯翻转后化为 k=t.由性质2 ,只需 再翻两轮必会成功.3. 情形二，n, m都是偶数.由(1)式知t是偶数或0,经s轮纯翻 转后，k=t,由性质2,至多再翻两轮就会成功.4. 情形三，n是奇数，m是偶数.由式知t是奇数，由式知,k是偶数或0,故无论翻转多少轮，k始终是奇数，不会出现 k=0,即不会成功.5. 综合条件轮数m奇t=0st奇s+1t偶s+2n, m偶

4、t=0st>0s+2n奇m偶无解6.例子例 1. n=8, m=3, s=2, t=2.翻 4 轮必成功0正面，1反面步骤过程（0）0 0 0 0 0 0 0 0（1）1 1 1 0 0 0 0 0（2）1 1 1 1 1 1 0 0（3）1 1 1 1 0 0 1 0（4）1 1 1 1 1 1 1 1例 2 .n=7, m=3, s=2, t=1.翻 3 轮必成功步骤过程（0）0 0 0 0 0 0 0（1）1 1 1 0 0 0 0（2）1 1 01 1 00（3）1 1 1 1 1 1 1推广把以上的条件2m< n ,改为m< n。条件2m< n等价于(1)式中

5、S> 2,此情况以上已经讨论清楚。 以下只讨论S=1的情况。设 n=m+t (0 < t<m) (3)性质3.设k(>2)是偶数，t> 1, j=min(k/2, t).按如下方法做完两 轮翻转后，正面数下降 2j.先取k-j个正面，m-k+j个反面，(m-k+j < m+t-kw n-k,可行) 做一轮翻转，k = m 2k 2j, k 二 k k = mk 2j.再取k个正面，mQ个反面，做一轮翻转，k = m - 2k , k = k k = m - k = k - 2 j.特别是当偶数kw 2t时，j = k/2, k =0.即至多翻两轮就必成功。情

6、形一 ,m是奇数(不论n是奇数还是偶数).只有如下3种可能：(i) t=0.做一轮纯翻转就成功.(ii) t (<m)是奇数.先做一轮纯翻转，再取t个正面，m-t个反面做一轮翻转，此时 k=m-t已是偶数.若kw 2t,则由性质3,只需再翻两轮必会成功；否则，用性质 3的方法， 每做两轮翻转就使 k下降2j.至多(m-3t)/2次(即m-3t轮)必满足kw 2t，只需再翻两轮必会成功。(iii) t (2wt<m)是偶数.做一轮纯翻转后化为 k=t.由性质3,只需再翻两轮必会成功 情形二,n, m都是偶数.由(1)式知t是偶数或0,经1轮纯翻转后， k=t，由性质3,至多再翻两轮就

7、会成功.情形三，n是奇数，m是偶数.由式知t是奇数，由式知，人k是 偶数或0，故无论翻转多少轮，k始终是奇数，不会出现k=0,即不会 成功.综合条件轮数m奇t=01t奇m< 3t4m3tw 4+m-3tt偶3n, m偶t=01t>03n奇m偶无解例子n=16， m=13, t=3.至多翻8轮必成功(0正面,1-反面)步骤过程备注(0)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0(1)1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0k=t=3(2)1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1k=10,j=3,a=7(3)0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0k=9,a=9(4)1 1