Olympiad Maths Prep

Track / Stage 6 / 324 of 400 #1324 of 2000

Problem 1324

National olympiad, first round
Combinatorics Difficulty 6.7 Find the answer

The number 11 is written on the blackboard. After that a sequence of numbers is created as follows: at each step each number aa on the blackboard is replaced by the numbers a1a - 1 and a+1a + 1; if the number 00 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 11 after 00 steps; 22 after 11 step; 1,31, 3 after 22 steps; 2,2,42, 2, 4 after 33 steps, and so on. How many numbers will there be on the blackboard after nn steps?

Official solution

1. Initial Setup and Sequence Generation:
- We start with the number 11 on the blackboard.
- At each step, each number aa on the blackboard is replaced by a1a-1 and a+1a+1.
- If 00 occurs, it is erased immediately.
- If a number occurs more than once, all its occurrences are left on the blackboard.

2. Pattern Observation:
- After 00 steps: 11
- After 11 step: 22
- After 22 steps: 1,31, 3
- After 33 steps: 2,2,42, 2, 4
- We observe that:
- An even row rr consists of copies of the odd numbers 1,3,,r+11, 3, \ldots, r+1.
- An odd row rr consists of copies of the even numbers 2,4,,r+12, 4, \ldots, r+1.
- The number r+1r+1 occurs exactly once in row rr.

3. Inductive Step for Even Rows:
- Consider an even row r=2nr = 2n.
- It can be shown by induction that this row 2n2n contains exactly 2k+1n+k+1(2nn+k)\frac{2k+1}{n+k+1} \binom{2n}{n+k} copies of any odd integer 2k+12k+1 with 0kn0 \le k \le n.
- This is because:
- Every copy of 2k12k-1 in row 2n22n-2 generates one copy of 2k+12k+1 in row 2n2n.
- Every copy of 2k+12k+1 in row 2n22n-2 generates two copies of 2k+12k+1 in row 2n2n.
- Every copy of 2k+32k+3 in row 2n22n-2 generates one copy of 2k+12k+1 in row 2n2n.

4. Special Case for Integer 1:
- In particular, row r=2nr = 2n contains exactly 1n+1(2nn)\frac{1}{n+1} \binom{2n}{n} copies of the integer 11.

5. **Total Number of Integers in Row rr:**
- Let f(r)f(r) denote the total number of integers in row rr.
- We claim that f(2n)=(2nn)f(2n) = \binom{2n}{n} and f(2n1)=12(2nn)f(2n-1) = \frac{1}{2} \binom{2n}{n}.
- The proof is by induction on nn, and f(0)=f(1)=1f(0) = f(1) = 1 are clear.

6. Inductive Proof:
- For the inductive step:
- Every (even) integer in an odd row 2n12n-1 spawns off two integers in row 2n2n; hence f(2n)=2f(2n1)f(2n) = 2f(2n-1).
- Every (odd) integer in an even row 2n2n spawns off two integers in row 2n+12n+1, but the 1n+1(2nn)\frac{1}{n+1} \binom{2n}{n} zeroes generated by the copies of 11 are erased again. Hence:
f(2n+1)=2f(2n)1n+1(2nn)=12(2n+2n+1) f(2n+1) = 2f(2n) - \frac{1}{n+1} \binom{2n}{n} = \frac{1}{2} \binom{2n+2}{n+1}

The final answer is 12(2n+2n+1)\boxed{\frac{1}{2} \binom{2n+2}{n+1}}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.