Maths Olympiad Prep

Library / /133 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

Sequence of integers {un}nN0\{u_n\}_{n \in \mathbb{N}_0} is given as: u0=0u_0=0, u2n=unu_{2n}=u_n, u2n+1=1unu_{2n+1}=1-u_n for all nN0n \in \mathbb{N}_0
a)a) Find u1998u_{1998}
b)b) If pp is a positive integer and m=(2p1)2m=(2^p-1)^2, find umu_m

Solution

To solve the given problem, we need to understand the sequence {un}nN0\{u_n\}_{n \in \mathbb{N}_0} defined by the following rules:
- u0=0u_0 = 0
- u2n=unu_{2n} = u_n
- u2n+1=1unu_{2n+1} = 1 - u_n

We will use these rules to find u1998u_{1998} and umu_m where m=(2p1)2m = (2^p - 1)^2.

### Part (a): Finding u1998u_{1998}

1. Binary Representation of 1998:
- Convert 1998 to its binary form:
1998=210+29+28+27+26+23+22+21=(11111001110)2 1998 = 2^{10} + 2^9 + 2^8 + 2^7 + 2^6 + 2^3 + 2^2 + 2^1 = (11111001110)_2
- The binary representation of 1998 is 11111001110211111001110_2.

2. Count the Number of 1's:
- Count the number of 1's in the binary representation:
Number of 1’s=7 (which is odd) \text{Number of 1's} = 7 \text{ (which is odd)}

3. **Determine u1998u_{1998}**:
- According to the given rule, un=1u_n = 1 if there is an odd number of 1's in the binary representation of nn, and un=0u_n = 0 if the number is even.
- Since 1998 has an odd number of 1's, we have:
u1998=1 u_{1998} = 1

### Part (b): Finding umu_m where m=(2p1)2m = (2^p - 1)^2

1. **Expression for mm**:
- Given m=(2p1)2m = (2^p - 1)^2, we need to find its binary representation.
- Note that 2p12^p - 1 in binary is a sequence of pp 1's:
2p1=11112 (p times) 2^p - 1 = 111\ldots1_2 \text{ (p times)}
- Squaring this number results in a binary number with a specific pattern.

2. **Binary Representation of mm**:
- The binary representation of mm will have a block of p1p-1 1's, followed by pp 0's, and ending with a single 1:
m=22p1+22p2++2p+2+2p+1+1=(11110001)2 m = 2^{2p-1} + 2^{2p-2} + \ldots + 2^{p+2} + 2^{p+1} + 1 = (11\ldots1100\ldots01)_2
- This representation has pp 1's in total.

3. **Determine umu_m**:
- Count the number of 1's in the binary representation of mm:
Number of 1’s=p \text{Number of 1's} = p
- According to the rule, un=1u_n = 1 if there is an odd number of 1's in the binary representation of nn, and un=0u_n = 0 if the number is even.
- Therefore, um=0u_m = 0 if pp is even, and um=1u_m = 1 if pp is odd.

The final answer is:

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.