培玉 · 一试
2010 年河北预赛 · 第 12 题
F3填空题概率
某家电影院的票价为每张 元，现有 个人，其中 个人手持 元钞票，另外 个人手持 元钞票。假设开始售票时售票处没有钱，这 个人随机排队购票，则售票处不会出现找不开钱的局面的概率是。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
以五元纸币的张数衡量能否找零。
思路
每个持五元者使可用零钱增加一张，持十元者使它减少一张，所以条件变成任意前缀中前者不少于后者。
解答
把持 元者记为 ，持 元者记为 。收一张 元不须找零，可用的五元纸币增加一张；收一张 元须找出一张 元，因此可用零钱减少一张。票价为 元，收来的十元纸币不能替代五元找零。故不发生零钱短缺等价于每个前缀的 数不少于 数。
十人虽不同，每个五正五负的类型序列恰对应 个具体排队，故 个类型序列等可能。把首次出现负前缀的部分反号，可将所有坏序列双射到六正四负序列，共 个。因此所求概率为
复核
首人持十元时立刻失败，而先来五名持五元者再来五名持十元者一定成功，与前缀条件相符。反射的逆操作是对六正四负序列在第一次达到正一时截断并反号，因而坏序列计数无重漏。
方法总结
排队找零题可先用最小面额零钱建立库存过程，再转成前缀和不越界。不同人的排列要先证明归并后的类型序列仍等可能。
为什么评为 F3（会透露解法方向）
零钱库存转为前缀非负条件，再以首次越界反射计坏排队；须证明按钞票类型归并后仍等可能，而非直接忽略人的区别。
已记下，谢谢！