Maths Olympiad Prep

Library / /31 of 144

Algebra Difficulty 7.8 National olympiad, round 2 Find the answer

Let a0,a1,a2,a_{0},a_{1},a_{2},\ldots be an increasing sequence of nonnegative integers such that every nonnegative integer can be expressed uniquely in the form ai+2aj+4aka_{i}+2a_{j}+4a_{k}, where i,ji,j and kk are not necessarily distinct. Determine a1998a_{1998}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let a0,a1,a2, a_0, a_1, a_2, \ldots be an increasing sequence of nonnegative integers such that every nonnegative integer can be uniquely represented in the form ai+2aj+4ak a_i + 2a_j + 4a_k , where i,j, i,j, and k k are not necessarily distinct. We aim to determine a1998 a_{1998} .

The uniqueness condition suggests that the sequence of a a 's behaves similarly to a positional numeral system. Specifically, each ai a_i acts like a digit in a base-8 (octal) system due to the coefficients 1,2, 1, 2, and 4 4 , which suggest powers of 2.

To represent any number N N uniquely as ai+2aj+4ak a_i + 2a_j + 4a_k , each index i,j,k i, j, k corresponds to a digit in base-8 representation, i.e., i,j,k i, j, k select which terms an a_n represent the "digit" places in the expansion.

Thus, the numbers N N can be expanded in a form similar to a base-8 system where each digit spans from 0 to the maximum allowable index. This insight guides us to choose each ai=i a_i = i , which aligns the sequence of a a 's directly with the indices required for base expansion.

Considering the sequence as an=n a_n = n , we have:

- a0=0 a_0 = 0 ,
- a1=1 a_1 = 1 ,
- a2=2 a_2 = 2 ,
- a3=3 a_3 = 3 ,
- ...
- an=n a_n = n .

For a1998 a_{1998} , we recognize 1998 1998 as a straightforward positional representation in base 8. Thus, converting 1998 from decimal to base 8, we obtain:

199810=111110011102 1998_{10} = 11111001110_2

Converting this binary to octal (since every three binary digits correspond to one octal digit):
111110011102=37368 11111001110_2 = 3736_8

Therefore, a1998 a_{1998} corresponds directly to this octal representation.

Thus, the solution for a1998 a_{1998} is given by the base-8 representation:
37368 \boxed{3736_8}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.