The number is written on the blackboard. After that a sequence of numbers is created as follows: at each step each number on the blackboard is replaced by the numbers and ; if the number occurs, it is erased immediately; if a number occurs more than once, all its occurrences are left on the blackboard. Thus the blackboard will show after steps; after step; after steps; after steps, and so on. How many numbers will there be on the blackboard after steps?
Problem 1324
Official solution
1. Initial Setup and Sequence Generation:
- We start with the number on the blackboard.
- At each step, each number on the blackboard is replaced by and .
- If occurs, it is erased immediately.
- If a number occurs more than once, all its occurrences are left on the blackboard.
2. Pattern Observation:
- After steps:
- After step:
- After steps:
- After steps:
- We observe that:
- An even row consists of copies of the odd numbers .
- An odd row consists of copies of the even numbers .
- The number occurs exactly once in row .
3. Inductive Step for Even Rows:
- Consider an even row .
- It can be shown by induction that this row contains exactly copies of any odd integer with .
- This is because:
- Every copy of in row generates one copy of in row .
- Every copy of in row generates two copies of in row .
- Every copy of in row generates one copy of in row .
4. Special Case for Integer 1:
- In particular, row contains exactly copies of the integer .
5. **Total Number of Integers in Row :**
- Let denote the total number of integers in row .
- We claim that and .
- The proof is by induction on , and are clear.
6. Inductive Proof:
- For the inductive step:
- Every (even) integer in an odd row spawns off two integers in row ; hence .
- Every (odd) integer in an even row spawns off two integers in row , but the zeroes generated by the copies of are erased again. Hence:
The final answer is .