Maths Olympiad Prep

Library / /13 of 27

Combinatorics Difficulty 6.3 National olympiad Find the answer

Determine the number of 20212021-tuples of positive integers such that the number 33 is an element of the tuple and consecutive elements of the tuple differ by at most 11.

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

Solution

We are tasked with determining the number of 20212021-tuples of positive integers (a1,a2,,a2021)(a_1, a_2, \ldots, a_{2021}) such that the number 33 is an element of the tuple, and for each pair of consecutive elements (ai,ai+1)(a_i, a_{i+1}), the condition ai+1ai1|a_{i+1} - a_i| \leq 1 holds.

Step 1: Counting the Total Number of Tuples

First, we consider the number of possible 20212021-tuples where ai{1,2,3}a_i \in \{1, 2, 3\}. Since each element can independently take any of the three values, there are:
32021 3^{2021}
such tuples.

Step 2: Excluding Tuples Where 3 is Not Present

Next, we calculate the number of tuples where the number 3 does not appear. In this case, each element aia_i can only be either 1 or 2. Thus, there are:
22021 2^{2021}
tuples where the number 3 is absent.

Step 3: Subtraction to Find the Desired Tuple Count

The desired number of tuples, i.e., tuples where at least one element is 3, is the total number of tuples minus the number of tuples with no '3'. Therefore, the result is given by:
3202122021 3^{2021} - 2^{2021}

Hence, the number of 20212021-tuples satisfying the given conditions is:
3202122021 \boxed{3^{2021} - 2^{2021}}

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.