A wizard keeps an aviary with sixteen perches for his phoenixes. The perches are numbered and all start out empty. Upon experimentation, the wizard has devised a spell to increase the power of his phoenixes. The strength of a phoenix can be represented as a positive integer. At any time, the wizard may do one of two things:
- 1.Summon a phoenix of strength 1 onto any empty perch. It is then bound to that perch.
- 2.Release two bound phoenixes of strength , wherever they sit, and cast the spell to fuse them into a phoenix of strength . The perches previously occupied by the released phoenixes now become empty, and the new phoenix settles onto any empty perch and is bound to that perch.
The wizard is a stickler about bookkeeping and requires his scribe to maintain a time-ordered record of the state of the aviary. For every numbered perch, the state of the aviary tells us whether that perch is empty or the strength of the phoenix that occupies it. The wizard's scribe insists that every observable state can be recorded as a single 64-bit integer and has wagered a month's pay on it. For each of the following questions, assume all of the perches start empty.
- (a)Settle the bet.
- (b)The wizard has since developed his own strength and can now summon phoenixes of strength 1 or strength 2. Settle the bet once more.
- (c)Summoning phoenixes of strength 2 has taken a toll on the wizard. Humbled, he returns to only summoning phoenixes of strength 1. Furthermore, he decided that he should keep stronger phoenixes closer to his dais for protection while he is recovering: when two phoenixes are fused, the new phoenix now must settle on the lower-numbered perch among the two previously-occupied perches. Settle the bet one final time. What is the exact number of observable states?