Maths Olympiad Prep

Library / /9 of 13

Number theory Difficulty 6.5 National olympiad Find the answer

Determine if there exists a finite set AA of positive integers satisfying the following condition: for each aAa\in{A} at least one of two numbers 2a2a and
a3\frac{a}{3} belongs to AA.

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

Solution

To determine whether there exists a finite set A A of positive integers such that for each aA a \in A , at least one of the numbers 2a 2a or a3 \frac{a}{3} belongs to A A , we proceed as follows:

Assume for the sake of contradiction that such a finite set A A exists. We will focus on the properties of the elements within this set.

1. Property of Multiplication by 2:

If aA a \in A , then 2a 2a must also be included in A A . This means that starting from any element a a , repeatedly multiplying by 2 gives additional elements that must also be in A A . This forms an infinite sequence a,2a,4a,8a, a, 2a, 4a, 8a, \ldots .

2. Property of Division by 3:

Similarly, if aA a \in A and a a is divisible by 3, then a3 \frac{a}{3} must be in A A . Continuously dividing by 3 (if possible) forms another sequence. However, dividing by 3 can only continue while the result remains a positive integer.

Given that A A is a finite set, eventually, these procedures of multiplying by 2 and dividing by 3 (when possible) must terminate.

3. Contradiction from Finite Assumption:

Let's explore the implication of having such operations in a supposed finite set A A :

- Consider the largest element bA b \in A . Applying the doubling process from any element less than or equal to b b will generate elements 2b,4b, 2b, 4b, \ldots potentially larger than b b . Therefore, these elements must exist in A A , forcing A A to expand beyond b b , contradicting the finiteness of A A .

- Suppose all elements aA a \in A cannot be divided by 3. Then the requirement a3A \frac{a}{3} \in A can never be satisfied for any a a . This requires A A to empty, further implying A A cannot exist.

Thus, given any initial assumption of the set A A being finite, we derive contradictions via the infinite generation of elements through multiplication or unfeasible satisfaction of conditions via division by 3. Therefore:

The answer is that no such finite set A A exists. Thus, the final conclusion is:

No \boxed{\text{No}}

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.