邏輯推理趣題進階版

[曾阿牛 10]

上一次發的帖子　有大大回應思考過程太過簡單...

嗯...　我會告訴我的學弟妹和學生說：當你不了解時　會覺得它很難　當你了解後　會覺得它很容易

以上的兩個誤解　分別造就了兩種負面情緒　第一　恐懼(以為它難)　第二　輕視(以為它容易)

這兩種情緒的作用　都是用來阻礙一個人的學習　所以

在學習時　應該專注在了解問題上　而不要考慮問題的難易　　

難易與否　是依賴個人當時的了解狀況　　每個人都有各自的狀況

譬如　解一元一次方程式　對(大部分)小學生來說就很難　對(大部分)中學生來說就很容易

可是　一元一次方程式問題本身的難度　就是一個　怎麼會有人覺得容易　又有人覺得難

這也好像相對論一樣　站在不同的觀測者坐標系統　觀測的結果就會不一樣

又像盲人摸象一樣　三個盲人摸的部位不一樣　對於大象的描述也不一樣

當您告訴別人說：這題很簡單　　或許可以贏得別人對您的刮目相看

但很可能也會造成　還不了解題目的人心裡的負擔

其實要讓人刮目相看　只要看您的答案(以及解說)就知道了　　如果有人看不出來　那是他沒眼光　也不用太理他

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

歹勢喔　以上的牢騷　　以下是進階的兩個題目

1. 在一個製鎖技術還沒成熟的時代　當時一個鎖只有一個鑰匙孔

有一個神秘集團　總共有10人　很可能以前是江洋大盜

他們雖然彼此合作　但也存在著嫌隙　不放心把所有財寶交給哪一個人保管

最後他們決定　把財產放在寶箱裡並且上鎖

如果只上一把鎖而且每人都有一把鑰匙　那麼任何一個成員　都可以獨自一個人開鎖把財產全拿走

所以　他們希望　要湊足三人　才能開寶箱　不到三人就無法開寶箱

那麼　問題來了　請問　他們至少要幾個鎖　才能達成他們的希望？

2. 話說 有100名成員的梅式(math)旅行團來到一個觀光景點,

但方圓百里之內僅有一家名為皮菌厚(pigeonhole)的旅館,

所以 旅團的人不得不在這旅館住宿.

雖然旅館每間都是空房, 但是總共也才90間房間.

而且梅式旅行團的團員們彼此之間非常不合, 所以要求一定要自己一間房睡.

好在 旅團的人每晚總是會有10個人在外遊蕩,

也就是說只會剩90人需要房間過夜.

(1). 如果你是皮菌厚旅館老闆, 最少要打幾把鑰匙給梅式旅行團, 才能讓每個團員每晚都有各自的房間安睡, 而不用來向你拿房間鑰匙, 也不用需要團員間彼此交換鑰匙.

(2). 又該如何分配那些鑰匙給團員呢?

(3). 又為什麼不能再少呢? (也就是說 請說明 (1) 的答案的理由)

舉個例子好了 :

1. 如果 給每人90把不同房間鑰匙的話, 不論剩下哪90人 要住宿的人總是可以打的開空房睡上一晚. 但是這樣一來 就需要100*90=9000把, 但這不會是最少的數量.

2. 假設 A 和 B 是旅團成員, A 有 1 和 2 號房的鑰匙 但是 B 只有 1 號房的鑰匙. 如果 A 已經在 1 號房 但 B 還沒有房間睡, 這時 B 可以請 A 換到 2 號房, 於是 A 和 B 就都有房可睡.

同理 90個人 彼此也可以互相商量好, 在不交換鑰匙的情況下都能有房間可睡

[曾阿牛 10]

瀏覽此帖的人數還不算少　但目前還沒有人回答......

難道是開學後大家開始忙碌起來？

標題之所以出現"進階版"　除了略為困難之外　也是因為跟上一題有關　即　它們的數學觀念有重複

所以　藉此問題　希望能讓那些輕視上一題的人　能了解　輕視問題確實會阻礙一個人的學習

個人我非常喜歡這題也是因為題目看起來很難　　而且我相信　一定有人在看了解答之後會說：原來這麼簡單

需要提示或答案的人　跟我反應一下　我目前不打算直接公佈作法

如果都沒有人反應　那麼這兩題就讓它隨風去　反正我也沒有損失

此內容已被編輯, February 29, 2012 ,由 曾阿牛

[AnJo 11]

抱歉啊最近比較忙比較少來逛，剛剛才看到～

為了怕雷還是反白一下？

第一題沒有特殊要求的話應該是3種鎖就好了，這樣可以保證「至少要三個人才能打開」，不過卻無法保證「三個人一定打得開」

第二題比較複雜一點，想了兩分鐘沒有特別的招，所以我想應該是990把吧？每一間房間各有11把

(1)990

(2)不要有一個人拿到兩隻一樣的鑰匙就行，但是我想順向發大家會比較好想像？

(3)因為再少的話要是持有鑰匙的十個人都出去遊盪不就慘了嗎？

喔，我的假設是出來遊盪的人都是隨機從昨天有睡覺的九十人中產生的，所以990把一定可以搞定

如果我有誤解題目的話肯定比990更少支，這是你要的答案嗎？

臨時想出來的有錯請樓主修正，我星期五應該會再上吧

（而且，這次是在數學版？）

此內容已被編輯, February 29, 2012 ,由 AnJo

[曾阿牛 10]

第二題答對了　不管是不是用兩分鐘　都很不錯唷

只是在鑰匙的分配上　並沒有提供一個確實的作法

第一題　題目裡說到：要湊足三人　才能開寶箱　不到三人就無法開寶箱

其實是兩個條件的組合

第一　要湊足三人　才能開寶箱：是指　三人聚在一起　就能保證開箱　再說得明白點　就是　任意三人聚在一起　就能聚集開鎖所需的全部鑰匙

第二　不到三人就無法開寶箱：任意兩人的鑰匙都不足以開所有的鎖

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

開學了　我也有事纏身　不會常上來

[王小寛- 10]

好難喔看不懂

第一題還好可是第二題就...….

[jean1983 10]

第一題

因為任意三個人即可開箱，只有兩個人無法開箱，

所以對任意兩個人的組合，需要有一把鎖讓他們打不開。

因此共需C(10,2)=45把鎖。

假設10個人分別為A,B,C,...J。

對A而言，他無法解開AB鎖、AC鎖、AD鎖...AJ鎖，

亦即45道鎖中，他無法開啟9道鎖，

因此配給他36把鑰匙。

考慮小一點的情況：四個人中湊齊三個人即可開所有的鎖。

以下是只有兩人時，必定有無法開啟的鎖的配置情況之一：

　１２３４５６

ＡＸＸＸ

ＢＸ　　ＸＸ

Ｃ　Ｘ　Ｘ　Ｘ

Ｄ　　Ｘ　ＸＸ

AB無法開1號鎖、AC無法開2號鎖、AD無法開３號鎖、

BC無法開４號鎖、BD無法開5號鎖、CD無法開6號鎖。

因此，可以如此配置鑰匙：

　１２３４５６

Ａ　　　ＶＶＶ

Ｂ　ＶＶ　　Ｖ

ＣＶ　Ｖ　Ｖ

ＤＶＶ　Ｖ

[rai 10]

第一題

因為任意三個人即可開箱，只有兩個人無法開箱，

所以對任意兩個人的組合，需要有一把鎖讓他們打不開。

因此共需C(10,2)=45把鎖。

假設10個人分別為A,B,C,...J。

對A而言，他無法解開AB鎖、AC鎖、AD鎖...AJ鎖，

亦即45道鎖中，他無法開啟9道鎖，

因此配給他36把鑰匙。

考慮小一點的情況：四個人中湊齊三個人即可開所有的鎖。

以下是只有兩人時，必定有無法開啟的鎖的配置情況之一：

　１２３４５６

ＡＸＸＸ

ＢＸ　　ＸＸ

Ｃ　Ｘ　Ｘ　Ｘ

Ｄ　　Ｘ　ＸＸ

AB無法開1號鎖、AC無法開2號鎖、AD無法開３號鎖、

BC無法開４號鎖、BD無法開5號鎖、CD無法開6號鎖。

因此，可以如此配置鑰匙：

　１２３４５６

Ａ　　　ＶＶＶ

Ｂ　ＶＶ　　Ｖ

ＣＶ　Ｖ　Ｖ

ＤＶＶ　Ｖ

--

不太懂，不是一個人只有一把鑰匙歐？

果然沒理解題目是件很危險的事，受教了 XD

[jean1983 10]

這題是很久以前的排列組合題目

(我只確定是民國90年以前的)

原題目少寫了「每個人可以有多把鑰匙」

我記得原本的題目是關於核子武器，大概是

「某國有核子武器，N個高層有權限發射。因為blahblah，所以至少要有K個高層到場才能發射。至少要設定幾道發射器的密碼鎖、每位高層知道幾個密碼，才能滿足上述條件。」

參考書有制式解答。

這題還需說明，如何確定C(N-1,K-1)是最少的鎖的數量。

[AnJo 11]

現在才發現，如果倒著想，應該是秒殺題才對T_T

太執著於「每個人要有幾隻鑰匙了」

[曾阿牛 10]

原題目少寫了「每個人可以有多把鑰匙」

......　不瞞各位　我第一次遭遇這題　是從"數學思考"一書中看到的(還是建中人翻譯的)

書中的題目除了沒有提到「每個人可以有多把鑰匙」之外　也沒有提到有幾人

更沒有提到一把鎖只有一個鑰匙孔

個人認為"一把鎖只有一個鑰匙孔"這條件是絕對不能少的　

如果少掉　那麼　只要準備一把三孔的鎖　就能達成目標

個人認為「每個人可以有多把鑰匙」這條件是倒是不必陳述出來

不陳述出來　不表示限制一人一把鑰匙

而是增加了解題目的難度

另外　此題當然還可以問至少需要幾把鑰匙　等等的問題　只不過　個人認為　能答出鎖的問題　自然能答出鑰匙的問題

旅館那一題　是五年前　我改編同類問題所造出的　目的是用來考驗我的學弟妹

所以題目的敘述較長　提問也比較多(一口氣問了三小題)

這題還需說明，如何確定C(N-1,K-1)是最少的鎖的數量。

如果我沒會錯意　應該是確定C(N,K-1)是最少的鎖的數量

[AnJo 11]

其實我覺得這題目出得很好

並不是簡單與否的問題，我想樓主要講的是現在教材當中

的數學（我只讀到高中對不起）太趨向於解題取向

忽略了過程當中的理解

我個人的感覺現在的數學好像在背解法......

[Nevar 10]

和樓上同感

第二航

此內容已被編輯, March 15, 2012 ,由 Nevar
沒看到有人解出第二題

[曾阿牛 10]

第一題

因為任意三個人即可開箱，只有兩個人無法開箱，

所以對任意兩個人的組合，需要有一把鎖讓他們打不開。

因此共需C(10,2)=45把鎖。

假設10個人分別為A,B,C,...J。

對A而言，他無法解開AB鎖、AC鎖、AD鎖...AJ鎖，

亦即45道鎖中，他無法開啟9道鎖，

因此配給他36把鑰匙。

45是對的答案　　可是從 jean1983 的答案無法明顯看出為什麼45是最少的

要讓任意兩人　有開不了的鎖　不見得需要全部的組合C(10, 2)

假設10人中有四人分別叫ABCD　那麼

會不會有一把鎖能讓AB和CD兩組人都開不了？　如果有　則答案有可能更少

此內容已被編輯, March 26, 2012 ,由 曾阿牛

[jean1983 10]

令L為鎖的集合，L={1,2,...,n}。

K_1,K_2,...,K_10為那10個人各自擁有的鑰匙集合，K_i包含於L。

任意三人可以開全部的鎖，所以K_x U K_y U K_z = L。

任意兩人無法開全部的鎖，所以L - (K_x U K_y) 非空。

假設對於x,y,i,j，{x,y}不等於{i,j}，K_x U K_y = K_i U K_j，

則對於下列四個集合：

K_x U K_y U K_i，K_x U K_y U K_j，K_x U K_i U K_j，K_y U K_i U K_j，

至少存在一個不等於L，與前提「任意三人可解開全部的鎖」矛盾。

因此，至少需準備C(10,2)=45道鎖。

[曾阿牛 10]

您選擇了用集合的方式來解說　這點值得讚許

但是　我反而產生了兩個疑問：

第一：　K_x U K_y = K_i U K_j　為何可推得 四個集合 K_x U K_y U K_i，K_x U K_y U K_j，K_x U K_i U K_j，K_y U K_i U K_j 中

至少存在一個不等於L? (PS: 現在看懂了)

第二：　得到矛盾後　則知假設錯誤　所以　存在 x, y, i, j　其中(x, y) ≠ (i, j)　且K_x U K_y ≠ K_i U K_j　但這似乎沒有解釋到為什麼 45 是最少

_______________________________________________________________________

好吧　讓我來試試：

假設 有一把鎖 L　能讓不同的兩組人 xy 和 ij 無法打開

在考慮 xy 和 ij 是不同的兩組的情況下　可得 xyij 至少有三人　

也就是說　有一把鎖 L　能讓三人無法打開　違背了任三人可開箱的條件

所以　那樣的鎖 L 是不存在的　也因此 45 最少

此內容已被編輯, April 3, 2012 ,由 曾阿牛