Maths Olympiad Prep

Library / /1076 of 1394

, 2018

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:
Find the largest positive integer nn for which there exist nn finite sets X1,X2,,XnX_{1}, X_{2}, \ldots, X_{n} with the property that for every 1a<b<cn1 \leq a < b < c \leq n, the equation
XaXbXc=abc \left|X_{a} \cup X_{b} \cup X_{c}\right| = \lceil \sqrt{a b c} \rceil
holds.

Solution

Solution:
First, we construct an example for N=4N=4. Let X1,X2,X3,X4X_{1}, X_{2}, X_{3}, X_{4} be pairwise disjoint sets such that X1=X_{1}=\varnothing, X2=1|X_{2}|=1, X3=2|X_{3}|=2, and X4=2|X_{4}|=2. It is straightforward to verify the condition.

We claim that there are no five sets X1,X2,,X5X_{1}, X_{2}, \ldots, X_{5} for which #(XaXbXc)=abc\#(X_{a} \cup X_{b} \cup X_{c}) = \lceil \sqrt{a b c} \rceil, for 1a<b<c51 \leq a < b < c \leq 5. Note that showing the non-existence of five such sets implies that there are no nn sets with the desired property for n5n \geq 5 as well.

Suppose, for sake of contradiction, that there are such X1,,X5X_{1}, \ldots, X_{5}. Then, note that X1X2X4=3|X_{1} \cup X_{2} \cup X_{4}| = 3, X1X2X5=4|X_{1} \cup X_{2} \cup X_{5}| = 4, and X2X4X5=7|X_{2} \cup X_{4} \cup X_{5}| = 7. Note that
X1X2X4+X1X2X5=X2X4X5. |X_{1} \cup X_{2} \cup X_{4}| + |X_{1} \cup X_{2} \cup X_{5}| = |X_{2} \cup X_{4} \cup X_{5}|.
For any sets A,B,C,DA, B, C, D, we have the following two inequalities:
ABC+ABDABCDBCD |A \cup B \cup C| + |A \cup B \cup D| \geq |A \cup B \cup C \cup D| \geq |B \cup C \cup D|
For A=X1A = X_{1}, B=X2B = X_{2}, C=X4C = X_{4}, and D=X5D = X_{5} in the situation above, we conclude that the equalities must both hold in both inequalities. The first equality shows that X1X2=X_{1} \cup X_{2} = \varnothing, and therefore both X1X_{1} and X2X_{2} are empty.

Now observe that X1X4X5=57=X2X4X5|X_{1} \cup X_{4} \cup X_{5}| = 5 \neq 7 = |X_{2} \cup X_{4} \cup X_{5}|. This gives a contradiction.

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.