JBMO Shortlist 2019 A3

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

JBMO Shortlist 2019 A3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

618 posts

#1 h Sep 12, 2020, 10:56 AM • 1 Y

Y by centslordm

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

This post has been edited 1 time. Last edited by Steve12345, Sep 12, 2020, 10:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15 posts

#2 h Sep 12, 2020, 2:24 PM • 1 Y

Y by centslordm

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

This post has been edited 2 times. Last edited by Steelgeere, Sep 13, 2020, 10:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

479 posts

#3 h Sep 12, 2020, 7:58 PM • 2 Y

Y by primesarespecial, centslordm

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

This post has been edited 2 times. Last edited by electrovector, Sep 20, 2020, 3:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

131 posts

#5 h Jun 1, 2021, 5:05 PM • 1 Y

Y by centslordm

$A \cup B = X$ Can anybody explain me this???

This post has been edited 3 times. Last edited by sttsmet, Jun 1, 2021, 5:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

407 posts

#7 h Jun 4, 2021, 8:16 PM

Y by

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!}$

This post has been edited 3 times. Last edited by Marinchoo, Jun 4, 2021, 8:22 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a