Maths Olympiad Prep

Library / /10 of 21

Algebra Difficulty 7.9 National olympiad, round 2 Find the answer

Let F\mathcal{F} be the set of all the functions f:P(S)Rf : \mathcal{P}(S) \longrightarrow \mathbb{R} such that for all X,YSX, Y \subseteq S, we have f(XY)=min(f(X),f(Y))f(X \cap Y) = \min (f(X), f(Y)), where SS is a finite set (and P(S)\mathcal{P}(S) is the set of its subsets). Find
maxfFIm(f).\max_{f \in \mathcal{F}}| \textrm{Im}(f) |.

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

Solution

Let S S be a finite set with S=n |S| = n . We are asked to find the maximum size of the image of a function f f in the set F\mathcal{F}, where F\mathcal{F} is the set of all functions f:P(S)R f : \mathcal{P}(S) \to \mathbb{R} satisfying the condition that for all subsets X,YS X, Y \subseteq S , we have:
f(XY)=min(f(X),f(Y)). f(X \cap Y) = \min(f(X), f(Y)).
The objective is to maximize Im(f) |\text{Im}(f)| , the number of distinct values taken by f f .

### Step-by-step Analysis

1. Understanding the Condition:
The condition f(XY)=min(f(X),f(Y)) f(X \cap Y) = \min(f(X), f(Y)) implies that for any subsets X X and Y Y of S S , if XY= X \cap Y = \emptyset , we should have f()=min(f(X),f(Y)) f(\emptyset) = \min(f(X), f(Y)) . Therefore, f() f(\emptyset) is the smallest value in the image of f f .

2. Construction of the Function:
Consider constructing f f based on the size of subsets. Define f(T) f(T) for every subset TS T \subseteq S based on its size:
f(T)=T. f(T) = |T|.

3. Image of the Function:
Under this construction:
- f()=0 f(\emptyset) = 0 .
- For any subset TS T \subseteq S with T=k |T| = k , f(T)=k f(T) = k .

As T T can be any subset, the value of f(T) f(T) can range from 0 0 to n n , where n=S n = |S| .

4. Size of the Image Set:
The image of f f , Im(f)\text{Im}(f), contains all integers from 0 0 to n n , inclusive. Therefore, Im(f)=n+1 |\text{Im}(f)| = n + 1 .

5. Verification:
Verify that this satisfies the condition f(XY)=min(f(X),f(Y)) f(X \cap Y) = \min(f(X), f(Y)) . For subsets X X and Y Y :
f(XY)=XY=min(X,Y)=min(f(X),f(Y)). f(X \cap Y) = |X \cap Y| = \min(|X|, |Y|) = \min(f(X), f(Y)).

In conclusion, the maximum size Im(f) |\text{Im}(f)| for functions fF f \in \mathcal{F} is indeed:
n+1. \boxed{n + 1}.
This represents the distinct non-negative integer values from 0 0 up to the size of the set S S , fulfilling the function condition defined in F\mathcal{F}.

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.