2003 AIME II 题目3

定义一个“好字”指的是一列字母 仅仅包含字母A B C 当然这三个字母不必全部出现在这个序列中 并且 B不能紧跟着A C不能紧跟着B A不能紧跟着C 这样的7位字母的”好字“一共有多少个？ 让我们来考虑这个问题 现在我们有很多A B 和C 于是数列可以全部是A 或全部是B 或全部是C 因为一些字母可能不会出现 B不能紧跟着A 也就是只有A或C能紧跟着A C不能紧跟着B 也就是说能紧跟着B的 只有A或B A不能紧跟着C 也就是只有C或B能紧跟着C 那么7位字母的好字一共有多少个呢? 让我们先考虑一下位字母 我们需要7个字母 1 2 3 4 5 6 7位字母 在第一个字母上没有限制 因为它前边没有其它字母 所以它可以是A B 或C 所以第一个字母有三种可能 第一个字母有三种可能 但是无论第一个字母是什么 有多少种可能 对第二个字母来说？ 如果第一个字母是A 那么第二个字母只能是A或者C 因为B不能紧连着A 如果第一个字母是B 那么第二个字母只能是B或者A 因为C不能紧连着B 如果第一个字母是C 那么第二个字母只能是B或者C 所以无论第一个字母是什么 第二个字母只有两种可能性 另一个考虑的角度是 有一个字母 无论第一个字母是什么 第二位上 总有一个字母会被排除 所以会剩下两种可能性 第三位也是同理 我们在这里填上一个字母 无论这个字母是什么 下一位都会排除掉一个可能的字母 所以下一位只剩下两个可能 供我们填写 无论这里这个字母是什么 同样的逻辑 这一位只有两种可能 所以一共有多少种可能呢? 3x2x2x2x2x2x2 一共有6个2 也就是3x2^6 也就是3乘以2的6次方 等于64 就等于180+12等于192 也就是有192个7位字母的“好字” 或者是如上定义的“好字”