※ 引述《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