Let X be the set consisting of the first 2018 terms of the arithmetic progression 1, 6, 11, ..., and

Q: Why do we use the Principle of Inclusion-Exclusion here? Can't we just list them out?

Listing them out would take a lifetime! The Principle of Inclusion-Exclusion, $n(X \cup Y) = n(X) + n(Y) - n(X \cap Y)$, is our mathematical shortcut. It acknowledges that when we add the sizes of $X$ and $Y$, we count the common elements twice. Subtracting the intersection $n(X \cap Y)$ once corrects this double-counting perfectly.

Q: How did you know the common difference of the intersection is 35?

Great observation! If a number is in both sequences, it must satisfy both $x \equiv 1 \pmod{5}$ and $x \equiv 9 \pmod{7}$. By the Chinese Remainder Theorem, or simply by observing the periodicity, the common terms must repeat every $\text{LCM}(5, 7) = 35$ units. It is the smallest step that satisfies both growth rates simultaneously.

Q: Wait, why did we check $k \le 1440$ instead of $k \le 2018$?

Excellent catch! While $k$ can go up to 2018 in set $Y$, the common terms are also constrained by the length of set $X$. We must satisfy both $n \le 2018$ and $k \le 2018$. Since $n$ is a function of $k$, the tighter constraint on $k$ (which is $k \le 1440$) dictates the maximum number of common terms.

Q: Is it possible for the first common term to be outside the range of the sets?

Yes, in some problems, the first common term might appear after the 2018th term of one of the sets. Always verify that your first common term $a_{common}$ is within the bounds of both sequences. Here, our first common term is 16, which is well within both sets.

Q: Why does $k = 2 + (r-1)5$ represent all common terms?

Since the common terms form an AP with a common difference of 35, and the original sequence $Y$ has a common difference of 7, the index $k$ must increase by $35/7 = 5$ for every new common term. Thus, $k$ itself forms an AP with a common difference of 5.

Question

Let $X$ be the set consisting of the first 2018 terms of the arithmetic progression $1, 6, 11, \dots$, and $Y$ be the set consisting of the first 2018 terms of arithmetic progression $9, 16, 23, \dots$. Then, the number of elements in the set $X \cup Y$ is ________.

Sigma Percentile · Accepted Answer

### The Harmony of Intersecting Progressions

Imagine you are standing at the edge of two infinite numerical highways. Highway $X$ starts at 1 and jumps forward by 5 every step: $1, 6, 11, 16, \dots$.

Highway $Y$ starts at 9 and leaps forward by 7 every step: $9, 16, 23, 30, \dots$. You have been given a specific task: count how many unique numbers exist if you combine the first 2018 terms of both highways.

### The Principle of Inclusion-Exclusion

To solve this, we invoke the elegant Principle of Inclusion-Exclusion. If we simply add the number of terms in $X$ to the number of terms in $Y$, we are counting the 'common' numbers twice—once because they belong to $X$, and once because they belong to $Y$.

To get the true count of the union, we must subtract the intersection. Our formula is simple yet powerful:

$$n(X \cup Y) = n(X) + n(Y) - n(X \cap Y)$$

We know $n(X) = 2018$ and $n(Y) = 2018$. The real mystery lies in finding $n(X \cap Y)$, the number of elements that live in both sets.

### Finding the Common Ground

Let us define the general terms of our sequences. For set $X$, the $n$-th term is $T_n = 1 + (n-1)5 = 5n - 4$. For set $Y$, the $k$-th term is $U_k = 9 + (k-1)7 = 7k + 2$.

For a number to be in the intersection, it must satisfy $T_n = U_k$. This leads us to the equation:

$$5n - 4 = 7k + 2$$

Rearranging this, we get $5n = 7k + 6$, or $n = \frac{7k + 6}{5}$. For $n$ to be an integer, $7k + 6$ must be divisible by 5.

By testing small values of $k$, we find that when $k=2$, $n = \frac{14+6}{5} = 4$. This tells us that the 4th term of $X$ is the same as the 2nd term of $Y$. Calculating this, we get $5(4)-4 = 16$. Indeed, 16 is the first common term!

### The Rhythm of the Intersection

Because the common difference of $X$ is 5 and the common difference of $Y$ is 7, the common terms will repeat at intervals of $	ext{LCM}(5, 7) = 35$. This means the common terms themselves form an arithmetic progression with a common difference of 35.

Since the original sequence $Y$ has a common difference of 7, the index $k$ must increase by $35/7 = 5$ for each subsequent common term. Thus, the indices $k$ that yield common terms follow the sequence $2, 7, 12, \dots$, which can be written as $k = 2 + (r-1)5$, where $r$ is the number of common terms.

### The Final Boundary

We must ensure these common terms do not exceed the 2018 terms provided. We have two constraints: $n \le 2018$ and $k \le 2018$. Using our relation $n = \frac{7k + 6}{5}$, the constraint $n \le 2018$ implies:

$$\frac{7k + 6}{5} \le 2018 \Rightarrow 7k + 6 \le 10090 \Rightarrow 7k \le 10084 \Rightarrow k \le 1440.57$$

Since $k$ must be an integer, $k \le 1440$. Now, we substitute our expression for $k$ into this inequality:

$$2 + (r-1)5 \le 1440 \Rightarrow (r-1)5 \le 1438 \Rightarrow r-1 \le 287.6 \Rightarrow r \le 288.6$$

Thus, there are exactly $r = 288$ common terms. Finally, we return to our inclusion-exclusion formula:

$$n(X \cup Y) = 2018 + 2018 - 288 = 3748$$

We have navigated the intersection of these two progressions and arrived at the solution. The final answer is **3748**.

Enter Numerical Value:

Visualized Solution

Objective & Inclusion-Exclusion

Analyzing Set $X$

Analyzing Set $Y$

Equating General Terms

Isolating Variables

Divisibility Condition

The Common Terms AP

General Form of $k$

Applying Boundary Conditions

Setting Up the Inequality

Solving for Total Common Terms ( $r$ )

Final Calculation

The Sigma Insight: Arithmetic Progression (A.P.)

The Harmony of Intersecting Progressions

The Principle of Inclusion-Exclusion

Finding the Common Ground

The Rhythm of the Intersection

The Final Boundary

Similar Questions

The number of common terms in the progressions $4, 9, 14, 19, \dots$ , up to $2 5^{t h}$ term and $3, 6, 9, 12, \dots$ , up to $3 7^{t h}$ term is :

Let $A = {1, a_{1}, a_{2}, \dots, a_{18}, 77}$ be a set of integers with $1 < a_{1} < a_{2} < \dots < a_{18} < 77$ . Let the set $A + A = {x + y : x, y \in A}$ contain exactly 39 elements. Then, the value of $a_{1} + a_{2} + \dots + a_{18}$ is equal to ______.

The series of positive multiples of 3 is divided into sets : ${3}, {6, 9, 12}, {15, 18, 21, 24, 27}, \dots$ Then the sum of the elements in the $1 1^{t h}$ set is equal to ________.

Let 3, 6, 9, 12, ... upto 78 terms and 5, 9, 13, 17, ... upto 59 terms be two series. Then, the sum of the terms common to both the series is equal to ______.

Let $3, 7, 11, 15, \dots, 403$ and $2, 5, 8, 11, \dots, 404$ be two arithmetic progressions. Then the sum, of the common terms in them, is equal to

The number of terms common to the A.P.’s 3, 7, 11, … 407 and 2, 9, 16, … 709 is _______.

The number of terms common the two A.P $3, 7, 11, \dots, 407$ and $2, 9, 16, \dots, 709$ is

The sum of the common terms of the following three arithmetic progressions. $3, 7, 11, 15, \dots, 399$ , $2, 5, 8, 11, \dots, 359$ and $2, 7, 12, 17, \dots, 197$ , is equal to

Suppose that all the terms of an arithmetic progression (A.P.) are natural numbers. If the ratio of the sum of the first seven terms to the sum of the first eleven terms is $6 : 11$ and the seventh term lies in between $130$ and $140$ , then the common difference of this A.P. is \dots.