Maths Olympiad Prep

Library / /278 of 520

Combinatorics Difficulty 7.0 National olympiad Find the answer

Let f0f_0 be the function from Z2\mathbb{Z}^2 to {0,1}\{0,1\} such that f0(0,0)=1f_0(0,0)=1 and f0(x,y)=0f_0(x,y)=0 otherwise. For each positive integer mm, let fm(x,y)f_m(x,y) be the remainder when fm1(x,y)+j=11k=11fm1(x+j,y+k) f_{m-1}(x,y) + \sum_{j=-1}^{1} \sum_{k=-1}^{1} f_{m-1}(x+j,y+k) is divided by 22.
Finally, for each nonnegative integer nn, let ana_n denote the number of pairs (x,y)(x,y) such that fn(x,y)=1f_n(x,y) = 1.
Find a closed form for ana_n.

Proposed by Bobby Shen

A number or a short expression. Spacing and $ signs are ignored.

Solution

To find a closed form for an a_n , we need to analyze the behavior of the function fm(x,y) f_m(x,y) and how it evolves over iterations. Let's break down the problem step by step.

1. Initial Function Definition:
f0(x,y)={1if (x,y)=(0,0)0otherwise f_0(x,y) = \begin{cases} 1 & \text{if } (x,y) = (0,0) \\ 0 & \text{otherwise} \end{cases}

2. Recursive Definition:
For each positive integer m m , the function fm(x,y) f_m(x,y) is defined as:
fm(x,y)=(fm1(x,y)+j=11k=11fm1(x+j,y+k))mod2 f_m(x,y) = \left( f_{m-1}(x,y) + \sum_{j=-1}^{1} \sum_{k=-1}^{1} f_{m-1}(x+j, y+k) \right) \mod 2

3. Counting Non-zero Terms:
We need to find an a_n , the number of pairs (x,y)(x,y) such that fn(x,y)=1 f_n(x,y) = 1 .

4. Pattern Observation:
We observe that the function fm(x,y) f_m(x,y) evolves in a way that resembles cellular automata, specifically the 2D version of the Rule 90 cellular automaton. This automaton has a known pattern of growth.

5. Binary Representation and Decomposition:
The problem can be simplified by considering the binary representation of n n . If n n has a binary representation with a zero, we can decompose it into smaller parts. For example:
a(101101110011)2=a(1011)2a(1110011)2 a_{(101101110011)_2} = a_{(1011)_2} \cdot a_{(1110011)_2}

6. Special Case Analysis:
We need to find a2k1 a_{2^k-1} for all kN k \in \mathbb{N} . This can be done by analyzing the recursive structure of the function.

7. Recursive Formula:
By analyzing the recursive structure, we find that:
a2k1=54k+(2)k+13 a_{2^k-1} = \frac{5 \cdot 4^k + (-2)^{k+1}}{3}

8. Combining Results:
Using the decomposition property and the special case analysis, we can combine the results to find an a_n for any n n .

Conclusion:
The closed form for an a_n is given by the recursive formula and the decomposition property. The final expression for an a_n is:
an=54k+(2)k+13 a_n = \frac{5 \cdot 4^k + (-2)^{k+1}}{3}
where k k is the largest integer such that 2k1n 2^k - 1 \leq n .

The final answer is 54k+(2)k+13 \boxed{ \frac{5 \cdot 4^k + (-2)^{k+1}}{3} }

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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