※ 引述《pentiumevo (pentiumevo)》之銘言： : 題目：一輛單向行駛的公車，滿載為25人，全程共14個車站，中途的每個車站 : 均可上下乘客。 由不同起點到達不同終點的乘客各應購買不同的車票 : 。在一次單程行駛中，車上最多可賣出多少種不同的車票？ : 出處：蘇淳，同中學生談排列組合，中國科學技術大學出版社，§1例8 : 疑惑與想法： : （1）我已明白所有車票種類數目是 : 13+12+11+...+2+1＝91 : （2）書上說：考慮起點是前七站某一站，終點是後七站某一站的所有車票， : 如此共有7×7＝49種。 : 所有持有此類車票的乘客都必須經過七號站與八號站之間的路程， : 但車子最多坐25人，因此有49－25＝24種票賣不出去。 : 因此最多可賣91－24＝67種。 : 我無法理解為什麼要這樣考慮。可以幫幫忙解說一下嗎？ : （3）如果是奇數個車站又要如何分析？可以給個Hint嗎？ : 下學期要修離散了，用的是Liu校長的組合數學導論，真的是... 應該可以想成找切入分析的點吧。像這個想法切入點在78中間，共有49種票，所以可以 排除24種情形。如果切入點考慮在67中間的話，共有6*8=48種票，只能排除48-25=23種票 。所以應該是從正中間切開能夠排除最多種。 Max x(14-x) => x=7 如果奇數的話，就正中間前一個或後一個，結果應該相同。 只是還是要說明存在性。這部份好像就沒交代。假設僅允許一個乘客。照這樣的算法， 應該可以排除 49-1 = 48種，所以最多可以賣出 91-48 = 43張票，但是其實應該只能賣出 13張票而已。解答並未給出一個賣出67種票的情況，這部份可能要在確定囉~ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.20.33