Question

(a) How many numbers between 1 and 70.000,000 , including both 1 and 70.000 .000 are divisible by \(2,5,\) or \(7 ?\) (b) How many numbers between 1 and \(6,000,000,\) including both 1 and 6,000,000 , are divisible by \(4,5,\) or \(6 ?\)

Short answer

(a) 46,000,000 numbers; (b) 2,800,000 numbers.

Step-by-step solution

Understanding the Problem

We need to determine how many numbers are divisible by 2, 5, or 7 within a certain range. We'll apply the principle of inclusion-exclusion to solve this.

Apply Inclusion-Exclusion for Part (a)

First, we'll calculate the number of numbers divisible by each of the factors (2, 5, and 7) and their combinations using the formula: \[ N(A \cup B \cup C) = N(A) + N(B) + N(C) - N(A \cap B) - N(A \cap C) - N(B \cap C) + N(A \cap B \cap C) \] where \(A\) is divisible by 2, \(B\) is divisible by 5, and \(C\) is divisible by 7.

Compute Divisibles for Part (a)

For numbers up to 70,000,000, calculate:- \(N(A) = \left\lfloor \frac{70,000,000}{2} \right\rfloor \)- \(N(B) = \left\lfloor \frac{70,000,000}{5} \right\rfloor \)- \(N(C) = \left\lfloor \frac{70,000,000}{7} \right\rfloor \)- \(N(A \cap B) = \left\lfloor \frac{70,000,000}{10} \right\rfloor \)- \(N(A \cap C) = \left\lfloor \frac{70,000,000}{14} \right\rfloor \)- \(N(B \cap C) = \left\lfloor \frac{70,000,000}{35} \right\rfloor \)- \(N(A \cap B \cap C) = \left\lfloor \frac{70,000,000}{70} \right\rfloor \) and plug into the inclusion-exclusion formula.

Final Calculation for (a)

Calculate the individual values:- \(N(A) = 35,000,000\)- \(N(B) = 14,000,000\)- \(N(C) = 10,000,000\)- \(N(A \cap B) = 7,000,000\)- \(N(A \cap C) = 5,000,000\)- \(N(B \cap C) = 2,000,000\)- \(N(A \cap B \cap C) = 1,000,000\)Finally, compute using inclusion-exclusion: \[ 35,000,000 + 14,000,000 + 10,000,000 - 7,000,000 - 5,000,000 - 2,000,000 + 1,000,000 = 46,000,000 \]

Apply Inclusion-Exclusion for Part (b)

Similar to part (a), apply inclusion-exclusion:\[ N(A \cup B \cup C) = N(A) + N(B) + N(C) - N(A \cap B) - N(A \cap C) - N(B \cap C) + N(A \cap B \cap C) \] where \(A\) is divisible by 4, \(B\) is divisible by 5, and \(C\) is divisible by 6.

Compute Divisibles for Part (b)

For numbers up to 6,000,000, calculate:- \(N(A) = \left\lfloor \frac{6,000,000}{4} \right\rfloor \)- \(N(B) = \left\lfloor \frac{6,000,000}{5} \right\rfloor \)- \(N(C) = \left\lfloor \frac{6,000,000}{6} \right\rfloor \)- \(N(A \cap B) = \left\lfloor \frac{6,000,000}{20} \right\rfloor \)- \(N(A \cap C) = \left\lfloor \frac{6,000,000}{12} \right\rfloor \)- \(N(B \cap C) = \left\lfloor \frac{6,000,000}{30} \right\rfloor \)- \(N(A \cap B \cap C) = \left\lfloor \frac{6,000,000}{60} \right\rfloor \) and plug into the inclusion-exclusion formula.

Final Calculation for (b)

Calculate the individual values:- \(N(A) = 1,500,000\)- \(N(B) = 1,200,000\)- \(N(C) = 1,000,000\)- \(N(A \cap B) = 300,000\)- \(N(A \cap C) = 500,000\)- \(N(B \cap C) = 200,000\)- \(N(A \cap B \cap C) = 100,000\)Finally, compute using inclusion-exclusion: \[ 1,500,000 + 1,200,000 + 1,000,000 - 300,000 - 500,000 - 200,000 + 100,000 = 2,800,000 \]

Key concepts

Divisibility

In mathematics, divisibility is the concept where one number can be divided by another number without leaving a remainder. It plays a crucial role in many areas of number theory and has practical applications in problems, such as finding common denominators or simplifying fractions. In this exercise, we focus on determining numbers divisible by specific integers like 2, 5, and 7. For instance, a number is divisible by 2 if its last digit is even, by 5 if its last digit is 0 or 5, and by 7 when the difference between twice the last digit and the remaining part of the number is a multiple of 7. When solving questions regarding divisibility in a given range, it often involves counting how many numbers within that range can be divided evenly by these specific integers, and this is where the use of formulas becomes necessary, simplifying what could otherwise be tedious calculations. The principle of divisibility helps in breaking down complex problems into simpler, more manageable tasks and is an essential tool in the field of number theory.

Combinatorics

Combinatorics is a branch of mathematics dealing with combinations of objects belonging to a finite set in accordance to certain constraints such as those of graph theory. This field often involves counting, arrangement, and combination-related questions. In our case, we focus on how the principle of inclusion-exclusion from combinatorics can be applied. The principle helps calculate probabilities or number counts for overlapping events. For instance, when we need to find numbers divisible by 2, 5, or 7, these sets of numbers have overlaps. The inclusion-exclusion principle efficiently accounts for this by:

• First adding all numbers divisible by each of the individual criteria.
• Then subtracting those counted multiple times due to being divisible by combinations (like 10, 14, and 35).
• Finally, adding back those counted too many times due to divisibility by all three numbers.

This principle reduces errors in counting and ensures the correct number of elements in the union of these sets.

Mathematical Problem Solving

Mathematical problem solving involves the process of working through details of a problem to reach a solution. It includes attempting and achieving new understandings of concepts. In the context of this exercise, solving such a problem requires understanding the combinatorial aspect of counting problems and applying systematic approaches like the inclusion-exclusion principle. To tackle this type of problem-solving:

• Identify what is being asked—here we need to count numbers divisible by certain integers.
• Apply systematic methods—using divisibility rules and strategic principles.
• Double-check calculations to avoid mistakes—like ensuring no overlap errors in counting.

Mathematical problem solving is an essential skill that can sharpen logical reasoning and analytical thinking. By dissecting problems into smaller achievable steps, anyone can tackle complex problems with greater ease and accuracy.