Let $A$ and $B$ be two non-empty subsets of $X = \{1, 2, . . . , 11 \}$ with $A \cup B = X$. Let $P_A$ be the product of all elements of $A$ and let $P_B$ be the product of all elements of $B$. Find the minimum and maximum possible value of $P_A +P_B$ and find all possible equality cases. Proposed by Greece
Problem
Source:
Tags: algebra
12.09.2020 17:24
Note that 11! = 2^8*3^4*5^2*7*11. Maximum is indefinitely 2×11!. Minimum is partitioning X into A and B with Pb > Pa such that Pb/Pa is minimum. Clearly 6300 divides 11! and one other divisor is as close as 6300 to (11!)^(1/2) so required minima is 6300+6336=12636. Too bland problem : ( I had earlier given solution to a similar question where A and B are mutually disjoint. Thanks @below. TBH not much of a problem still
12.09.2020 22:58
Maximum is obviously $2 \cdot 11!$ For the minimum as expressed @above, we have $$P_A + \frac{11!}{P_A} \ge 2 \sqrt{11!}$$So the closer $P_A$ and $P_B$ are, the smaller minimum we have. For $P_A=2 \cdot 5 \cdot 7 \cdot 9 \cdot 10$ and $P_B= 3 \cdot 4 \cdot 6 \cdot 8 \cdot 11$ we have minimum $12636$ @above also thanks for the example, I didn't waste too much time on it
01.06.2021 20:05
$A \cup B = X$ Can anybody explain me this???
04.06.2021 23:16
This is a very tedious problem, because you don't need a lot of insight, but rather to be able to compute a lot. Here is a full solution (as the previous ones kind of point towards the right idea, but are incomplete): $P_{A}+P_{B}\leq P_{X}+P_{X}=2P_{X}=2\times 11!$. Equality occurs when $\{2,3,4,5,6,7,8,9,10,11\}\in A$ and $\{2,3,4,5,6,7,8,9,10,11\}\in B$, so all the equality cases are: $$(A,B)=(X\backslash\{1\},X),(X,X\backslash\{1\}),(X,X)$$Now onto the nontrivial part, that is the minimum of $P_{A}+P_{B}$. If there is some $2\leq c\leq 11$, such that $c\in A$ and $c\in B$, then for the set $A'=A\backslash\{c\}$ we would have $A'\cup B=X$ and $P_{A'}+P_{B}=\frac{1}{c}P_{A}+P_{B}<P_{A}+P_{B}$, so ${A\cap B}\in \{1\}$. Let's notice the obvious inequality that if $x,y,z,t>0$, $xy=zt$ and $y>x>z$, then $x+y<z+t$. Indeed, if we assume otherwise, then $zt\leq z(x+y-z)=-(z-x)(z-y)+xy<xy$, contradiction. So we've shown that $P_{A}P_{B}=11!$ and $P_{A}+P_{B}$ is minimal when $|P_{A}-P_{B}|$ is minimal, now we should just find $P_{A}$ and $P_{B}$. Notice that $11!=2^8\times 3^4\times 5^2\times 7\times 11$, so $\sqrt{11!}=2^4\times 3^2\times 5\times \sqrt{77}=720\sqrt{77}$. We can bound up to the third decimal point to get $8.774<\sqrt{77}<8.775$, so $6317<720\sqrt{11!}<6318$. WLOG assume that $\{11\}\in A$ as if we switch $A$ and $B$ nothing will change. Now we'll look for the nearest number to $6317$, which is divisible by $11$ and has only prime divisors $2,3,5,7$. And so we begin checking the numbers around $\frac{6317}{11}\approx 574$: $$\boxed{567 = 3^4\times 7}, 568 = 2^{3}\times 71, 569 \text{ is prime }, 570 = 2\times 3\times 5\times19, 571 \text{ is prime }$$$$ 572 = 2^2\times 11\times 13, 573 = 3\times 191, 574 = 2\times 7\times 41, 575 = 5^{2}\times 23, \boxed{576 = 2^{6}\times 3^{2}} $$Now we only have to check the two possibilities: $3^4\times 7\times 11+2^{8}\times 5^{2}=6237+6400=12637$ and $2^{6}\times 3^{2}\times 11+2^2\times 3^2\times 5^2\times 7=6336+6300=12636$, so $P_{A}+P_{B}\geq 12636$. It only remains to look at what those sets might be. It's easy to see that all the equality cases are: $$A=\{2,5,7,9,10\}, B=\{1,3,4,6,8,11\}$$$$A=\{1,2,5,7,9,10\}, B=\{3,4,6,8,11\}$$$$A=\{1,2,5,7,9,10\}, B=\{1,3,4,6,8,11\}$$$$A=\{1,3,5,6,7,10\}, B=\{2,4,8,9,11\}$$$$A=\{3,5,6,7,10\}, B=\{1,2,4,8,9,11\}$$$$A=\{1,3,5,6,7,10\}, B=\{1,2,4,8,9,11\}$$$$A=\{1,3,4,6,8,11\}, B=\{2,5,7,9,10\}$$$$A=\{3,4,6,8,11\}, B=\{1,2,5,7,9,10\}$$$$A=\{1,3,4,6,8,11\}, B=\{1,2,5,7,9,10\}$$$$A=\{2,4,8,9,11\}, B=\{1,3,5,6,7,10\}$$$$A=\{1,2,4,8,9,11\}, B=\{3,5,6,7,10\}$$$$A=\{1,2,4,8,9,11\}, B=\{1,3,5,6,7,10\}$$$\boxed{\text{Answer: } 12636\leq P_{A}+P_{B}\leq 2\times 11!}$