Let $A$ and $B$ be nonempty subsets of $\mathbb{N}$. The sum of $2$ distinct elements in $A$ is always an element of $B$. Furthermore, the result of the division of $2$ distinct elements in $B$ (where the larger number is divided by the smaller number) is always a member of $A$. Determine the maximum number of elements in $A \cup B$.
Problem
Source: 2023 Indonesia TST Stage 1: Test 4 - Combinatorics
Tags: combinatorics, trivial
31.05.2024 21:36
Maybe I consider something wrong Condition 1 of the problem: If $x,y \in A \implies \left\lfloor \frac{x}{y} \right\rfloor \in B$ (1) Condition 2 of the problem: If $x,y \in B, x>y \implies \left\lfloor \frac{x}{y} \right\rfloor \in B$ (2) Suppose that there exists $a,b,c \in A$ such that $a>b>c \overset{\text{(1)}}{\implies} a+b,a+c,b+c \in B \overset{\text{(2)}}{\implies} \left\lfloor \frac{a+b}{a+c} \right\rfloor \in A$. But $\left\lfloor \frac{a+b}{a+c} \right\rfloor \leq \frac{a+b}{a+c} < \frac{a+b}{a} < \frac{2a}{a} =2 \implies \left\lfloor \frac{a+b}{a+c} \right\rfloor =1 \implies 1 \in A \overset{\text{(1)}}{\implies} c+1, c+2, c+3, \dots \in B \implies 2c \in B$ $ \overset{\text{(2)}}{\implies} \left\lfloor \frac{2c}{c} \right\rfloor = 2 \in A \overset{\text{(1)}}{\implies} 1+2, 1+3, 1+4, \dots \in B \implies B = \mathbb{N} \implies A = \mathbb{N} \implies |A \cup B| = \infty$
01.06.2024 05:43
Say A has 3 distinct elements, x, y, and z. Assume x<y<z. Then y+z and x+z are two distinct elements of B, so their quotient is a member of A, but z<x+z<y+z<2z so their quotient is strictly between 1 and 2, contradiction. So A has 2 or less elements. Say B has 4 distinct elements, w, x, y, and z. Assume w<x<y<z. Then x/w, y/w, and z/w are distinct elements of A, contradicting with A having 2 or less elements. So B has 3 or less elements. Thus together A and B must have at most 5 elements. This is achieved by (2,4) and (6,12,24).
02.06.2024 04:23
HyperDunteR wrote: Maybe I consider something wrong Condition 2 of the problem: If $x,y \in B, x>y \implies \left\lfloor \frac{x}{y} \right\rfloor \in B$ (2) Suppose that there exists $a,b,c \in A$ such that $a>b>c \overset{\text{(1)}}{\implies} a+b,a+c,b+c \in B \overset{\text{(2)}}{\implies} \left\lfloor \frac{a+b}{a+c} \right\rfloor \in A$. But $\left\lfloor \frac{a+b}{a+c} \right\rfloor \leq \frac{a+b}{a+c} < \frac{a+b}{a} < \frac{2a}{a} =2 \implies \left\lfloor \frac{a+b}{a+c} \right\rfloor =1 \implies 1 \in A \overset{\text{(1)}}{\implies} c+1, c+2, c+3, \dots \in B \implies 2c \in B$ $ \overset{\text{(2)}}{\implies} \left\lfloor \frac{2c}{c} \right\rfloor = 2 \in A \overset{\text{(1)}}{\implies} 1+2, 1+3, 1+4, \dots \in B \implies B = \mathbb{N} \implies A = \mathbb{N} \implies |A \cup B| = \infty$ I think there is additional information for condition 2, the division of any two element in $B$ cannot have a remainder. So it's like $$x,y \in B\text{ with } x>y \implies \frac{x}{y} \in A.$$ So, the answer is $5$, proof @above
02.06.2024 04:31
GreenTea2593 wrote: Let $A$ and $B$ be nonempty subsets of $\mathbb{N}$. The sum of $2$ distinct elements in $A$ is always an element of $B$. Furthermore, the result of the division of $2$ distinct elements in $B$ (where the larger number is divided by the smaller number) is always a member of $A$. Determine the maximum number of elements in $A \cup B$. For clarity Condition 1 : for any $$x,y \in A , x\ne y \implies x+y \in B.$$ Condition 2 : for any $$x,y \in B , x>y \implies \frac{x}{y} \in A.$$