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 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⋅5=15 in it. Then having 7 in A would give us a greater value of our multiplication. Cause we will have 7⋅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⋅7=49
23.02.2024 05:54
Am I missing something or shouldn't it be 5⋅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.