Let A and B be two non-empty subsets of X={1,2,...,11} with A∪B=X. Let PA be the product of all elements of A and let PB be the product of all elements of B. Find the minimum and maximum possible value of PA+PB 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⋅11! For the minimum as expressed @above, we have PA+11!PA≥2√11!So the closer PA and PB are, the smaller minimum we have. For PA=2⋅5⋅7⋅9⋅10 and PB=3⋅4⋅6⋅8⋅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∪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): PA+PB≤PX+PX=2PX=2×11!. Equality occurs when {2,3,4,5,6,7,8,9,10,11}∈A and {2,3,4,5,6,7,8,9,10,11}∈B, so all the equality cases are: (A,B)=(X∖{1},X),(X,X∖{1}),(X,X)Now onto the nontrivial part, that is the minimum of PA+PB. If there is some 2≤c≤11, such that c∈A and c∈B, then for the set A′=A∖{c} we would have A′∪B=X and PA′+PB=1cPA+PB<PA+PB, so A∩B∈{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≤z(x+y−z)=−(z−x)(z−y)+xy<xy, contradiction. So we've shown that PAPB=11! and PA+PB is minimal when |PA−PB| is minimal, now we should just find PA and PB. Notice that 11!=28×34×52×7×11, so √11!=24×32×5×√77=720√77. We can bound up to the third decimal point to get 8.774<√77<8.775, so 6317<720√11!<6318. WLOG assume that {11}∈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 631711≈574: 567=34×7,568=23×71,569 is prime ,570=2×3×5×19,571 is prime 572=22×11×13,573=3×191,574=2×7×41,575=52×23,576=26×32Now we only have to check the two possibilities: 34×7×11+28×52=6237+6400=12637 and 26×32×11+22×32×52×7=6336+6300=12636, so PA+PB≥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}Answer: 12636≤PA+PB≤2×11!