【4/1/26 更新第12题】摸鱼人节（April Fish Day）一周年，推荐一些有趣但不难的编程练习题（不是 LeetCode）
Amex卡号碰撞建模引热议，坛友分享相关NP完全问题论文。
关键信息
- 主题：Amex卡号后四位碰撞问题（#361）。
- 核心规律：Amex主卡首张后四位固定为
100x，副卡递增101a/102b...；换卡后四位按200y/300z等序列递增。最后一位由Luhn算法决定（#361）。 - 数学模型：基于生日悖论（Birthday Paradox）。开4张卡时，出现后四位重复的概率已达50%（#361）。
- 编程任务：计算持有M张有FHR权益的Amex卡时，严格执行“遇重复即换”策略下的总期望换卡次数及第m张卡的换卡次数。要求编写代码计算而非仅模拟（#361）。
- 难度设定：
- 简单版：假设最后一位随机生成。在新讨论中，坛友指出可假定每次开卡和换卡最后一位都随机生成（#361, #362）。
- 进阶版：假设前11位Luhn状态随机，换卡严格遵循
100x/200y/300z序列及Luhn校验（#361）。
经验与数据点
- 卡号规律与实操痛点：由于Amex App仅显示后4位，多卡用户易刷混卡；且FHR（Fine Hotels & Resorts）权益与后四位绑定紧密，导致重复时需频繁换卡。此外，换卡涉及UPS邮寄费用，增加了持卡实际成本并伴随权益失效风险（#361）。
- 具体碰撞实例：开4张卡时即有50%概率重复。楼主（#361）在持有第4张卡时遭遇碰撞，换卡后甚至引发了新卡撞老卡的连锁换卡反应。
- Luhn校验及建模推导（#362, #366）：
- 坛友哈耶克（#362）假定Amex卡号格式为
3710 xxxxxx yn00z（$z$ 为Luhn校验和，$n$ 随换卡递增）。 - 引理1：在Luhn规则下，生成过程可等效为三元组 $(y, n, z)$，其中 $y, z \overset{\text{iid}}{\sim} \text{Uniform}(0, 9)$。由于Luhn算法在 $\mathbb{Z}_{10}$ 下仅为置换和常数相加，不改变最后一位的随机均匀分布性。因此，带递增卡号的简单版与进阶版在数学上并无显著差异。
- 换卡逻辑修正：若仅有 $n$ 递增，随着 $n$ 增长 $z$ 将表现为随机排列，碰撞概率极大（#366）。另有DP表明实际换卡时客服可能会连同中间数位一起更换，机制可能更为复杂（#366）。
- 编程题难度反馈：坛友反馈该贴推荐的编程练习题难度非常合适，既不太简单也不太难，适合想找适中难度题目的摸鱼人（#369）。
最新动态
- 答案撤回：楼主“班主任”（#365）曾在帖子中短暂发布了该数学题的参考答案，但随后进行了撤回。
- 建模解答进展：坛友哈耶克（#362）尝试使用 ChatGPT 辅助进行动态规划（DP）演算，但因在机场网络受限导致降智。他计划邀请 MIT EE 博士审阅后再行发布，以确保严密性（#362, #364）。
- 学术延伸讨论（#367, #368）：受论坛关于“优美NP完全问题”讨论的启发，坛友分享了其大学时代因“违反公序良俗”不便在泥潭公开的一个更难、更有趣的NP完全变体问题，并表示未来若能蹭到 tech report 会用小号发帖（#367）。坛友 @Chao (#368) 随后指出学术界已有关于该方向（如 Orgy Planning Problem）的公开论文，认为讨论并无问题，邀请其私信交流。