Maths Olympiad Prep

Library / /19 of 1394

Combinatorics Difficulty 4.5 AIME Find the answer United States

Problem:
Find the number of pairs of union/intersection operations (1,2){,}2\left(\square_{1}, \square_{2}\right) \in \{\cup, \cap\}^{2} satisfying the following condition: for any sets S,TS, T, function f:STf: S \rightarrow T, and subsets X,Y,ZX, Y, Z of SS, we have equality of sets
f(X)1(f(Y)2f(Z))=f(X1(Y2Z)), f(X) \square_{1}\left(f(Y) \square_{2} f(Z)\right)=f\left(X \square_{1}\left(Y \square_{2} Z\right)\right),
where f(X)f(X) denotes the image of XX : the set {f(x):xX}\{f(x): x \in X\}, which is a subset of TT. The images f(Y)f(Y) (of YY ) and f(Z)f(Z) (of ZZ ) are similarly defined.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Answer: 1 If and only if 1=2=\square_{1}=\square_{2}=\cup. See http://math.stackexchange.com/questions/359693/overview-of-1

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.