You have two blackboards $A$ and $B$. You have to write on them some of the integers greater than or equal to $2$ and less than or equal to $20$ in such a way that each number on blackboard $A$ is co-prime with each number on blackboard $B.$ Determine the maximum possible value of multiplying the number of numbers written in $A$ by the number of numbers written in $B$.
Problem
Source:
Tags: contests, coprime numbers, number theory
25.04.2023 19:18
The Answer is $\boxed{49}$ But How can I prove this? :/ $A={2,4,7,8,11,14,16}$ $B={3,5,9,13,15,17,19}$
25.04.2023 20:59
We have 8 prime numbers and to get the maximum possible value of this multiplication we have to have equal or close to equal number of integers in both $A$ and $B$. Writing $2$ and $3$ in different pairs gives us $4$ powers of $2$ in $A$ and $2$ power of $3$ in $B$. As we have a smaller number of integers in $B$ we have to have $5$ in $B$ to get $3 \cdot 5 = 15$ in it. Then having $7$ in $A$ would give us a greater value of our multiplication. Cause we will have $7 \cdot 2 = 14$ in $A$. ( we cannot have it in $B$ as it wouldn't give us any multiple of $7$). In this case we have $6$ elements in $A$ and $4$ in $B$ and $4$ prime numbers left. As we said before we have to have equal number of integers in both $A$ and $B$. So we give $1$ prime to $A$ and other $3$ to $B$. And we get $7 \cdot 7 = \boxed{49}$
23.02.2024 05:54
Am I missing something or shouldn't it be $5 \cdot 13 = 65$? Just use: A = 7, 11, 13, 17, 19 and B = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20.