Maths Olympiad Prep

Library / Balkan MO Shortlist /9 of 19

Balkan MO Shortlist

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,Y⊆SX, Y \subseteq S, we have f(X∩Y)=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
max⁡f∈F∣Im(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,Y⊆S X, Y \subseteq S , we have:
f(X∩Y)=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(X∩Y)=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 X∩Y=∅ 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 T⊆S 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 T⊆S 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(X∩Y)=min⁡(f(X),f(Y)) f(X \cap Y) = \min(f(X), f(Y)) . For subsets X X and Y Y :
f(X∩Y)=∣X∩Y∣=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 f∈F 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.