Maths Olympiad Prep

Library / /658 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

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.

A number or a short expression. Spacing and $ signs are ignored.

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=,X2=1,X3=2X_{1}=\varnothing,\left|X_{2}\right|=1,\left|X_{3}\right|=2, and X4=2\left|X_{4}\right|=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 #\left(X_{a} \cup X_{b} \cup X_{c}\right)=\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\left|X_{1} \cup X_{2} \cup X_{4}\right|=3, X1X2X5=4\left|X_{1} \cup X_{2} \cup X_{5}\right|=4, and X2X4X5=7\left|X_{2} \cup X_{4} \cup X_{5}\right|=7. Note that X1X2X4+X1X2X5=X2X4X5\left|X_{1} \cup X_{2} \cup X_{4}\right|+\left|X_{1} \cup X_{2} \cup X_{5}\right|=\left|X_{2} \cup X_{4} \cup X_{5}\right|. 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=X1,B=X2,C=X4A=X_{1}, B=X_{2}, C=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\left|X_{1} \cup X_{4} \cup X_{5}\right|=5 \neq 7=\left|X_{2} \cup X_{4} \cup X_{5}\right|. 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.