標籤：

現有6個1元面值硬幣正面朝上放在桌上，你每次必須翻轉5個，最少經過幾次翻轉可以使6個硬幣全部反面朝上？

12-02

有必要這麼麻煩嗎……
定義翻某5個為A類操作。
定義B操作，是把所有的硬幣全部翻面。
定義C操作，是翻某一個硬幣。

題主的問題是若干次A操作之後能否達到某個狀態，而一個A操作等同於做一次B一次C，注意到B和C操作是可交換的，因此可以理解為先做若干次數的C操作，然後再做相同次數的B操作，結束.
而做若干次C操作相當於一個一個硬幣地翻，這大家就都會了吧……

6次吧，每次都令一個不同的硬幣不翻即可

現有的大部分答案都不夠好。

題主的問題太過具體，而現有的答案都只是就事論事，方法都有很大的局限性，而且有不少答案方法其實是有漏洞的，只是湊巧得到了正確的結果罷了。所以，即使做對了這道題，但換個數字，方法失效，還是不會做。所以，我們來解決一下更本質的問題——

【有 n 個硬幣，一開始全部正面朝上，每次可以翻轉 k 個硬幣（ k 小於 n ），那麼至少要 p 次翻轉，才能讓所有硬幣反面朝上，求 p 的值】

高能預警：
本題所用的數學工具不超過初中畢業水平，但情況繁多，完整討論並不容易，結論寫在最後。

解：

本題的精髓在於對奇偶性的討論。

——情況1：若 n 為奇數——

1.1 若 k 為偶數 =&> 無解

證明：

若要讓所有硬幣最終翻面，則每個硬幣都要翻面奇數次，共有奇數個硬幣，所以所有硬幣的翻面總數為奇數，但每次只能翻面偶數個硬幣，顯然不可能。證畢！

1.2 若 k 為奇數 =&> p為不小於 n/k 的最小奇數

（例1：n=7，k=5，那麼 n/k =1.4 則 p=3 ）
（例2：n=25，k=7，那麼 n/k= 25/7 則 p=5）

證明：

必要性：
若要讓所有硬幣最終翻面，則每個硬幣都要翻面奇數次，共有奇數個硬幣，所以所有硬幣的翻面總數為奇數，而每次只能翻奇數個硬幣，所以總的翻轉次數必然是奇數次，而翻轉次數不到 n/k 次時，並不能使所有硬幣至少翻面1次，所以p至少是不小於 n/k 的最小奇數。

充分性：

  • 當 k=n-2 時，只要3次翻轉即可

給硬幣編號為1-n，
第1次翻轉編號：1~n-2
第2次翻轉編號：1~n-3、n-1
第3次翻轉編號：1~n-3、n
Done！（前 n-3 個硬幣翻面 3 次，後 3 個翻面 1 次）

  • 當frac{n}{3}leq k<n-2 時，依然只要3次翻轉

只要讓前面的frac{3k-n}{2} 個硬幣翻轉 3 次，後面的frac{3n-3k}{2} 個硬幣翻轉 1 次即可。這是顯然可以做到的。

  • 當k<frac{n}{3}時，需要p次翻轉（p為不小於 n/k 的最小奇數）

根據定義，pkgeq n,(p-2)k<n，由於k<n，所以pk<3n 這意味者翻轉 p 次後，平均來說，每個硬幣翻面次數小於3次。只要讓前面的frac{pk-n}{2} 個硬幣翻轉 3 次，後面的frac{3n-pk}{2} 個硬幣翻轉 1 次即可。

——情況2：若 n 為偶數——


2.1 若 frac{n}{2}<k<n-1 且為偶數=&> p=3

只要讓前面的frac{3k-n}{2} 個硬幣翻轉 3 次，後面的frac{3n-3k}{2} 個硬幣翻轉 1 次即可。
這個情況，和 n 為奇數是類似的。

2.2 若 frac{n}{2}<k< n-1 且為奇數=&>p為不小於 n/(n-k) 的最小偶數

這種情況比較特殊。
首先由奇偶性得出翻轉次數必為偶數，而每一枚硬幣翻轉的次數為奇數，則每一枚硬幣至少不翻轉 1 次。
其次，每次有 n-k 枚不翻轉，所以 p 必須不小於 n/(n-k) 。
方案：讓前面frac{kp-np+3n}{2} 硬幣翻轉 p-1 次，後面frac{np-kp-n}{2} 硬幣翻轉 p-3 次

2.3 若kleq frac{n}{2} 且為偶數=&> p為不小於 n/k 的最小整數

當 k=frac{n}{2} 時，顯然 p=2；
反之，只要讓前面的frac{pk-n}{2} 個硬幣翻轉 3 次，後面的frac{3n-pk}{2} 個硬幣翻轉 1 次即可。

2.4 若kleq frac{n}{2} 且為奇數=&> p為不小於 n/k 的最小偶數

當 k=frac{n}{2} 時，顯然 p=2；
反之，首先由奇偶性得出翻轉次數必為偶數，
只要讓前面的frac{pk-n}{2} 個硬幣翻轉 3 次，後面的frac{3n-pk}{2} 個硬幣翻轉 1 次即可。

————————————

綜上所述：

若 n 為奇數：

  • 若 k 為偶數 Rightarrow 無解
  • 若 k 為奇數 Rightarrow p 為不小於 n/k 的最小奇數

若 n 為偶數：

  • 若 k為偶數，且frac{n}{2}<k<n-1 Rightarrow p=3
  • 若 k為奇數，且frac{n}{2}<kleq n-1 Rightarrow p 為不小於 n/(n-k) 的最小偶數
  • 若 k為偶數，且kleq frac{n}{2} Rightarrow p 為不小於 n/k 的最小整數
  • 若 k為奇數，且kleq frac{n}{2} Rightarrow p 為不小於 n/k 的最小偶數

————————————

特別地，本題屬於情況 2.2，答案是 6。

————————————

從這個結果，對比本問題的其他回答，可以看到其他高票回答可能存在的問題：

蘇椰的回答，用圖解法很有創造性，但只有當n為偶數且 k=n-1 時才可使用，方法的局限性很大，而且它會產生一種「每個硬幣翻面次數差不多」的固定思維模式，對解題不利；
王箏的回答，類似集合的增補法，看起來很巧妙，也容易理解，但這個方法未能指出 「B操作必須是偶數次」的重要結論，而是默認本題必有解，這是很容易犯錯的；

所以，這個看似小學奧數的題，其實用非代數的方法來做，是不太妥當的，它要麼很容易讓你產生思維定式，要麼讓你看不清整除關係，如果沒有經過一定量的思維訓練，在這些地方都非常容易犯錯，而代數方法，對結果正確性的把握是比較大的。
這也是為什麼小學奧數往往只能針對特殊情況有解，但無法形成體系推廣開來，從而顯得很「難」，不能被大多數人所接受，最終被更正統的中等數學所替代的原因。

********************

本答案於 2014 年 11 月 12 日 發布
於 2015 年 9 月 23 日 修正瑕疵並簡化

如需轉載，請私信作者。

包括 @曾加 老師在內，所有的答案方法都麻煩了。

對，即使針對曾加老師提出的n硬幣每次翻轉k個的問題也是麻煩了，這個問題可以建立更簡單的模型，即求不定方程
xk=(2y+1)n
的最小正整數解，即
kx-2ny=n
的最小正整數解。由簡單的初等數論知識，這個方程有整數解的必要條件是k和2n的最大公約數也是n的約數，即不允許k是偶數而n是奇數的情況。在有解的情況下，這個方程可以用擴展歐幾里得演算法來解。

每次翻五個，可以理解成每個硬幣翻五次。
第一步，選第一個硬幣翻五次；
第二步，選第二個硬幣翻五次；
第三步，選第三個硬幣翻五次；
第四步，選第四個硬幣翻五次；
第五步，選第五個硬幣翻五次；
第六步，選第六個硬幣翻五次；

答案是六次。
也可以循環翻。
反對加沒有幫助。

這題放公務員考試這=_=，其實是腦筋急轉彎，翻五個=翻一個，一個一個翻過去，六次
----------------------------
為什麼翻五個等於翻一個？
從上面看，翻五個=從下面看，翻一個
上看ABBBBB
下看BAAAAA
上五AAAAAA
下一AAAAAA

其實灰常簡單，我相信只需要有奇數和偶數的概念就能看懂下面的證明了。
先假設需要操作的總次數為p

做一個很簡單的變換--把每次翻轉5個硬幣，分解成兩步：
1、把一個硬幣翻轉一次；
2、把所有的硬幣翻轉一次

如果p為偶數，那麼上面的第二步實際上被抵消了，所以相當於每次只做第一步。所以p=6.
如果p是奇數，那麼相當於每次只做第一步，最後把所有的硬幣翻一次面，這等價於只做奇數次第一步，最後保持所有的硬幣仍然是正面向上，這顯然是不能做到的。

綜上，p=6

看了排名前幾的答案，比如 @曾加@蘇椰@雷佳明 都是大神，以各種不同的思路給出了漂亮嚴謹的證明，所以證明我就不廢話多說了
要說的主要就是：這是公務員的行測考試題目！行測考試什麼狀況？1道題1分鐘不到的解答時間！所以大多數的答案都是在考場上不可行的！
首先要批評題主，在做行測試題的時候很明顯忽略了選項，行測數量關係選項是非常非常非常非常重要的好么！數量關係題目不是讓你真的算出那個答案，是讓你根據題目大概估算出哪個選項比較靠譜啊！所以你不把選項拿出來怎麼知道該怎麼解！
然後說下 @郭開升和 @張凌雲的答案，一個是實際操作，一個是理論計算，意思是差不多的，這兩個應該是考場上應該使用的方法，其中第一個比較適合文科生，第二個比較適合理科生。
至於這個題的最好的解法，明顯是選項帶入，看看真正操作幾次可以完成。
另外多說一句，這個題明顯是某公or某圖的年輕老師仿照多年前一道真題改編的
2009年山西真題：有7個杯口全部向上的杯子，每次將其中4個同時翻轉，經過幾次翻轉，杯口可以全部向下?

A．3次 B．4次 C．5次 D．幾次也不能

但是這個題將本來的簡單奇偶性定性判斷題目變成了複雜的奇偶性分情況分析，嚴重偏離了行測考試的本來目的——測試數學思想敏感和反應速度。

所以最後給題主一個忠告：不要做模擬題！一定一定要做真題！

想像一下，你的桌子是一個透明的茶几
你人不動一次翻五個，跟另一種操作是等效的，就是只翻一個，然後頭伸到茶几下面去，從下往上看
然後第二次，人不動一次翻五個，跟另一種操作是等效的，就是只翻一個，然後頭伸回到茶几上面來，從上往下看
就這樣每次只翻一個同時頭換一下位置
。。。。
然後六次操作以後，如果你每次翻的都是不一樣的，六個就全翻過來了，然後因為六是偶數，你的頭正好也在茶几上面，完畢

1. @曾加 的答案非常好，思路也對。我們在解決問題的時候不應該僅僅是想著解決這個問題就完事，可以想一想這個問題的其他變形嘛，或者是將問題更加泛化一下，看看自己想出來的這種方法能不能解決，所謂舉一反三吧。

2.難道沒有人看這個問題眼熟？這是CSDN上面的一道舊題，我們來看CSDN上面的題目描述：

有m個人面向南方站成一排(m ≥1)，每喊一次口號可以有n個人同時轉身一次(1≤n≤m)，問共需喊多少次口號所有人最終全部面向北方？請編寫一個函數，函數有兩個參數，分別為m和n，函數返回值為最終需要的次數，若經過無窮大次仍然無法全部轉向北方，則輸出-1.

怎麼樣，和@曾加 修改之後的問題是不是一模一樣？

這個問題下面有不少網友提出了自己的想法，有給程序的，也有和曾加一樣給出公式解的。

哦，忘記給鏈接了。學知識，請猛戳：一個演算法題，數學大牛們快過來-CSDN論壇-CSDN.NET-中國最大的IT技術社區

3.我是在今年的暑假看到這道題的，去雲南的前一天晚上。

第一眼看到這道題，我就沒想到去求公式解（顯然是因為我的數學不好）。

那天晚上，在紙上畫了一陣之後，發現這其實是一個搜索問題，並且搜索空間和硬幣的個數是線性關係。

然後用BFS的思路寫了個程序，代碼如下：

import java.util.ArrayList;
import java.util.Iterator;

import javax.management.openmbean.ArrayType;
import javax.management.openmbean.SimpleType;

public class OneAlgorithm {

/**
*
* @param x: x is number of zeros
* @param y: y is number of ones
* @return
*/
public static int max(int x, int y, int n){
int max = 0;
if(x &>= n)
max = n;
else
max = 2 *x - n;

return max;
}

public static int min(int x, int y, int n){
int min = 0;
if(y &>= n)
min = -n;
else
min = n - 2*y;

return min;
}

/**
*
* @param m
* @param n
* @return
*/
public static int BFS(int m, int n){
if(m % n == 0)
return n;

ArrayList& states = new ArrayList&();
ArrayList& floors = new ArrayList&();
int floor = 0;
int zeros = m;
floors.add(floor);
states.add(zeros);

int index = 0;

int max, min;
int x = m;
int y = 0;
max = max(x,y,n);
min = min(x,y,n);

while(true){
while(max &>= min)
{
zeros = x - min;
if(zeros == 0)
return floors.get(index)+1;
if(floors.indexOf(index) == floor)
floor++;
if(!states.contains(x-min))
{
states.add(x-min);
floors.add(floor);
}
min = min + 2;
}
index = index + 1;
if(index+1 &> states.size())
return -1;
x = states.get(index);
y = m - x;
max = max(x,y,n);
min = min(x,y,n);
}
}

public static void main(String[] args){
int temp = BFS(13,7);
System.out.println(temp);
}
}

對，用Java寫的，我很Low，拜託大家不要再說我了。

哦，後來還寫了一篇簡短的博客，裡面稍微寫了一點我的思路，但也很不詳細。地址是：CSDN論壇上的一道演算法題

4.最後
再次@曾加，能給出公式解，說明這個問題已經被完美解決了。這裡貼上我的代碼，僅僅是多給出一個解決思路。

我也看曾加（這是第幾次提到了）的答案，學知識去嘍。

我們不證明，不推理，只用最簡單的邏輯，為了解決題目，求最容易理解，求最快得到答案，因為只有6枚硬幣，若數字太大不建議採取以下邏輯。
一般邏輯就是連著的兩次翻轉不能是無效操作，即兩次翻轉不能正反相對，否則就翻還原了，那兩次就沒有翻得意義了。下面我們來實際操作，
將數字標記為A，花為B。
Start：
AAAAAA：6A（下劃線為將翻轉硬幣，以下皆是）
第一次翻轉，只能是5A（5個A，為方便看一下皆略去個），得到
BBBBBA：5B1A
第二次翻轉，只能是4B1A，肯定不能翻5B，如果那樣就翻回去了，得到
BAAAAB：4A2B
第三次翻轉，只能是3A2B，肯定不能是4A1B，否則又回去了，得到
AABBBA：3A3B
第四次翻轉，只能是3A2B，得到
BBAABB：2A4B
第五次翻轉，只能是4B1A，得到
AABAAA：5A1B
第六次翻轉，只能是5A，得到
BBBBBB：6B

其實仔細，從上往下觀察，就可以發現「加粗文字」、「加粗下劃線文字」，都會有規律的。
是不是很簡單，小學生都能看懂的邏輯？

粗略瀏覽下好像還沒人提到用線性方程的方法。
其實也可以這樣想，由於這六種操作是可以交換的，也就是說給定其中幾種操作，無論什麼按照順序進行結果是一樣的，而同一操作進行兩次等於沒有操作，那麼如果有解最多進行六步。
我們把每個操作看做是一個六維的列向量向量，比如第一枚硬幣不翻面的操作對應的向量是
( 0, 1, 1, 1, 1, 1 ) 的轉置（就是把這個向量豎起來得到的列向量），這樣得到了六個列向量記為A_1 到 A_6，而兩種操作的複合就是對應向量相加得到的向量，於是問題的解就是下面的線性方程（組）的解
A_1*x_1 + A_2*x_2 + A_3*x_3 + A_4*x_4 + A_5*x_5 + A_6*x_6 = ( 1, 1 1, 1, 1, 1 )的轉置
當然了， 是在二元域上求解（也就是 1+1 =0,1+0=0+1=1，1*1=1,1*0=0*1=0的那個域，感覺自己好啰嗦呀），我們要找的是步數最少的解，也就是解向量中1 最少的解，經過簡單高斯消元後發現解是唯一的，也就是恰好每種操作都進行一次。於是最少要六步！
這種方法雖然巧妙不足，但是簡單粗暴容易理解和推廣，一般的有關二元的問題手算都能很快搞定。

要讓所有硬幣翻過來，要做的就是每個硬幣翻奇數次。
總共六個硬幣，每次翻五個。
那麼情況就只有每個硬幣翻一次、三次、五次。
但是每次只能翻五個，不能多不能少，所以就要求總共翻的次數是5的整倍數。
所以就是每個硬幣翻五次。總共翻了5x6=30次
每次翻5個
30/5=6次
答：最少翻六次
＝＝

個人認為，你可以用兩個硬幣，一次翻一個做參考，感覺不行，就再加一個三個硬幣一次翻兩個，你就會發現答案的次數始終是跟硬幣的數量相等。公務員考試的時候，這種思維方法最有用，能節省很多時間。

我覺得就是 5k=(2n+1)6 最小正整數解是k=6 n=2
因為方程不違反對稱性 所以總可以找到一種方法滿足方程的解

要想得這麼複雜么？兩次就可以啦！
第一次，只翻動其中兩顆，結果是1顆反面朝上，5顆正面朝上；
第二次，把剩下的5顆翻了就可以了。
（作者沒說每次都要翻轉不同的硬幣）

等於是一次翻一個，六次

把題目翻譯成簡單的數學邏輯就是：求5和6的最小公倍數。是30，一次翻5個，那麼30/5=6次

解決了。。。

這道題告訴我們：學好小學奧數很重要。其實小學奧數就是赤裸裸的邏輯碾壓，能夠用邏輯解決的，就沒有方程什麼事了。因為方程其實是笨辦法，因為邏輯不夠才需要用方程簡單粗暴的解決。

@曾加的回答很贊，深表佩服.但2.2.3略有瑕疵，僅在n/2&3/4n時p的求解就等價為n中一次取n-k(結合王箏的回答)，轉為為2.2.5的情況了.

6個硬幣
如果是每次翻1個 6 1 6/1=6次
如果是每次翻2個 6 2約掉後3 1 3*1=3 3/1=3次
如果是每次翻3個 6 3約掉後2 1 2*1=2 2/1=2次
如果是每次翻4個 6 4約掉後3 2 3*2=6 6/2=3次
如果是每次翻5個 確定6 5 沒有公約數 6*5=30 30/5=6次
7個硬幣
每次翻3個 7 3 7*3=21 21/3=7
每次翻4個 7 4 7*4=28 28/4=7
問題來了 這個是不可能的， 6個硬幣的時候
每次翻的個數*次數/硬幣總數=奇數
硬幣要全翻面，每個硬幣都要翻面奇數次
7個硬幣總共也要翻奇數次
如果等於偶數就翻不過來

6和5的最小公倍數

老婆，答案是6次。 為什麼呢，因為我掐指一算就是這麼多，怎麼掐得呢。

這是正

這是反。
雙手一起就有6個指頭了。 嗯，你也掰下，很簡單的。 他們那樣算，考公務員的時候絕對沒時間做完呀，不推薦他們的。
逗逼答案。求不舉報，不反對T_T

有個很簡單的想法，每兩次翻面可完成0個或2個硬幣面被翻，因此任意2n個硬幣，最少需要2n次翻面行為
--------------------------------------
再補充一下，2n+1個硬幣是無法達成反轉的，首先用以上方法不可以。同時用若干個兩次操作加一個單次操作也是不可能的，因為若要最後單次操作成功，必須事先只有一個硬幣被反面，這一點也是若干雙次翻面無法達到的。

推薦閱讀：

※你是如何看待你的(與數學工作者的)數學直覺？
※除了靠猜和（不優雅的）構造，如何函數化特殊數列？
※數學期望的含義是什麼？
※數學領域有哪些經典的笑話？
※三門問題，將所有情況排列開來，得出的概率和正確答案不符，求解釋?

TAG:數學 | 公務員 | 公務員考試 | 行政職業能力測驗 |