【問題】商人過河

[樹精 10]

第一部分

三名商人各帶一名隨從乘船過河 一隻小船只能容納兩人 由他們自己滑行 在河的另一岸

一旦隨從的人數比商人多 就殺人取財 但如何成船的大全掌握在商人的手裡 商人們要怎麼安全過河呢?

喔~第二部分改天在打

題目有怪怪的嗎?

商人可以躲在船上嗎?

拜託各位提出自己的想法吧~

[AndyLeo 10]

兩名隨從先到對岸 一名隨從回來再把一名隨從帶到對岸 然後一名隨從回來

這樣變成這邊是三個商人一個隨從 對面是兩個隨從 然後兩個商人一起開船到對岸

然後一個商人跟一個隨從開船回去原本的岸上 然後兩個商人再開船到對岸

隨從開船回去把仍在對面的兩個隨從接過來就好了

我用"商"代表商人 "隨"代表隨從 畫一次圖

商商商隨隨隨船____________________

商商商隨_________________________隨隨船

商商商隨隨船______________________隨

商商商___________________________隨隨隨船

商商商隨船________________________隨隨

商隨_____________________________商商隨隨船

商商隨隨船________________________商隨

隨隨_____________________________商商商隨船

隨隨隨船__________________________商商商

隨_______________________________商商商隨隨船

隨隨船____________________________商商商隨

_________________________________商商商隨隨隨船

[aa011854 10]

好像可以用排列組合去算?

[樹精 10]

這是第二部分

商人為K名 可各帶隨從A名 小船最多做B人 探討安全渡河模式

請各為愛數學的大家

提出自己的看法吧

排列組合阿?怎麼排阿?可以提示一下嗎?

[AndyLeo 10]

我想應該直接探討商人K名 隨從A名(一個商人各帶兩個隨從還沒搭船就被殺了)

並且K要大於等於A

小船至少要可以乘坐兩個人(如果更少, 那就只有一個在划來划去)

可以坐四個人不用探討 每次兩個商人跟兩個隨從到對岸 放下一個商人跟一個隨從

周而復始一定可以載完,所以B=2 or 3

我看到的這種問題商人不能躲在船上

假設B=2, K=A

隨從可以一直把隨從帶到對岸

所以可以帶min{A-1, 2}個隨從到對岸(加上A-1是因為一定有一個隨從要回來)

然後2個商人到對岸 接下來

一定要一個商人跟一個隨從回去(不然一定有一邊的商人被殺)

接下來不是所有商人都到對岸 不然就只能一個商人跟一個隨從再到對岸

因為K=A, 兩邊商人跟隨從一直保持相等的狀態 除非有一邊商人空了

所以商人無法一次到對岸就無解了, 可得K=3是最大值

如果A=K-1

一個商人跟一個隨從到對岸 放下商人 隨從回去

一個商人跟一個隨從到對岸 放下隨從 商人回去

由於商人多了一個 所以多出一個隨從可以在中間替大家開船

不論幾個商人都有辦法載到對岸, 得知K為任意解

可以推得A小於K就是不論幾個人都有解

如果B=3且K=A

那可以載min{A-1,3}個隨從到對岸

然後3個商人到對岸 一個商人一個隨從回去

接下來一次載三個商人 如果載不完那也是無解

因為只能一個商人跟一個隨從划來划去

所以K=5是最大值

如果A小於K,由上得知K為任意解(船每次載兩個人就跟上面的證明一樣)