Maths Olympiad Prep

Library / /160 of 520

Combinatorics Difficulty 6.6 National olympiad Find the answer

For every 0i17 0 \le i \le 17, ai\equal{\minus1,0,1} a_i \equal{} \{ \minus{} 1, 0, 1\}.
How many (a0,a1,,a17) (a_0,a_1, \dots , a_{17}) 18\minus 18 \minus{}tuples are there satisfying :
a0\plus2a1\plus22a2\plus\plus217a17\equal210 a_0 \plus{} 2a_1 \plus{} 2^2a_2 \plus{} \cdots \plus{} 2^{17}a_{17} \equal{} 2^{10}

Pick one

Solution

1. We need to find the number of 18-tuples (a0,a1,,a17)(a_0, a_1, \dots, a_{17}) where each ai{1,0,1}a_i \in \{-1, 0, 1\} and they satisfy the equation:
a0+2a1+22a2++217a17=210 a_0 + 2a_1 + 2^2a_2 + \cdots + 2^{17}a_{17} = 2^{10}

2. Notice that 2102^{10} is a power of 2, and we need to express it as a sum of terms of the form 2iai2^i a_i where ai{1,0,1}a_i \in \{-1, 0, 1\}.

3. We can write 2102^{10} as a sum of distinct powers of 2, considering the constraints on aia_i. The possible ways to write 2102^{10} using the terms 2iai2^i a_i are:
210,211210,212211210,,217216211210 2^{10}, \quad 2^{11} - 2^{10}, \quad 2^{12} - 2^{11} - 2^{10}, \quad \ldots, \quad 2^{17} - 2^{16} - \cdots - 2^{11} - 2^{10}

4. Each of these expressions represents a unique way to form 2102^{10} using the terms 2iai2^i a_i with ai{1,0,1}a_i \in \{-1, 0, 1\}.

5. To count the number of such sets, we observe that each expression corresponds to a unique combination of aia_i values. Specifically, each expression involves a different set of indices ii where ai=1a_i = 1 and the rest are 0 or -1.

6. The number of such distinct sets is equal to the number of terms in the sequence from 2102^{10} to 2172162112102^{17} - 2^{16} - \cdots - 2^{11} - 2^{10}. This sequence has 8 terms.

Conclusion:
8 \boxed{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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.