Maths Olympiad Prep

Library / /32 of 43

Algebra Difficulty 6.1 National Olympiad Prove it JBMO

Problem:
Let AA and BB be two non-empty subsets of X={1,2,,11}X=\{1,2, \ldots, 11\} with AB=XA \cup B = X. Let PAP_{A} be the product of all elements of AA and let PBP_{B} be the product of all elements of BB. Find the minimum and maximum possible value of PA+PBP_{A} + P_{B} and find all possible equality cases.

Solutions — 2

Solution 1

Solution:
For the maximum, we use the fact that (PA1)(PB1)0(P_{A} - 1)(P_{B} - 1) \geqslant 0, to get that PA+PBPAPB+1=11!+1P_{A} + P_{B} \leqslant P_{A} P_{B} + 1 = 11! + 1. Equality holds if and only if A={1}A = \{1\} or B={1}B = \{1\}.

For the minimum observe, first that PAPB=11!=cP_{A} \cdot P_{B} = 11! = c. Without loss of generality let PAPBP_{A} \leqslant P_{B}. In this case PAcP_{A} \leqslant \sqrt{c}. We write PA+PB=PA+cPAP_{A} + P_{B} = P_{A} + \frac{c}{P_{A}} and consider the function f(x)=x+cxf(x) = x + \frac{c}{x} for xcx \leqslant \sqrt{c}. Since
f(x)f(y)=xy+c(yx)yx=(xy)(xyc)xy f(x) - f(y) = x - y + \frac{c(y - x)}{y x} = \frac{(x - y)(x y - c)}{x y}
then ff is decreasing for x(0,c]x \in (0, c].
Since xx is an integer and cannot be equal with c\sqrt{c}, the minimum is attained to the closest integer to c\sqrt{c}. We have 11!=283452711=72077=6317\lfloor \sqrt{11!} \rfloor = \left\lfloor \sqrt{2^{8} \cdot 3^{4} \cdot 5^{2} \cdot 7 \cdot 11} \right\rfloor = \lfloor 720 \sqrt{77} \rfloor = 6317 and the closest integer which can be a product of elements of XX is 6300=2579106300 = 2 \cdot 5 \cdot 7 \cdot 9 \cdot 10.
Therefore the minimum is f(6300)=6300+6336=12636f(6300) = 6300 + 6336 = 12636 and it is achieved for example for A={2,5,7,9,10}A = \{2,5,7,9,10\}, B={1,3,4,6,8,11}B = \{1,3,4,6,8,11\}.

Suppose now that there are different sets AA and BB such that PA+PB=402P_{A} + P_{B} = 402. Then the pairs of numbers (6300,6336)(6300, 6336) and (PA,PB)(P_{A}, P_{B}) have the same sum and the same product, thus the equality case is unique for the numbers 63006300 and 63366336. It remains to find all possible subsets AA with product 6300=22325276300 = 2^{2} \cdot 3^{2} \cdot 5^{2} \cdot 7. It is immediate that 5,7,10A5,7,10 \in A and from here it is easy to see that all possibilities are A={2,5,7,9,10},{1,2,5,7,9,10},{3,5,6,7,10}A = \{2,5,7,9,10\}, \{1,2,5,7,9,10\}, \{3,5,6,7,10\} and {1,3,5,6,7,10}\{1,3,5,6,7,10\}.

Solution 2

Solution:
We have PA+PB2PAPB=211!=144077P_{A} + P_{B} \geqslant 2 \sqrt{P_{A} P_{B}} = 2 \sqrt{11!} = 1440 \sqrt{77}. Since PA+PBP_{A} + P_{B} is an integer, we have PA+PB144077=12636P_{A} + P_{B} \geqslant \lceil 1440 \sqrt{77} \rceil = 12636. One can then follow the approach of the first solution to find all equality cases.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.