функция в/у множества, МО Иран 2010 (финал)

[drago]

[tex]S[/tex] е крайно множество с [tex]n[/tex] елемента, а [tex]P(S)[/tex] e множеството от всички подмножества на [tex]S[/tex].
Дадена е функцията [tex]f:\, P(S) \to \mathbb{N}[/tex] със следните свойства.

1) За всяко [tex]A; \, A \subset S[/tex] е изпълнено [tex]f(A) = f(S \setminus A)[/tex].
2) за всеки [tex]A, B; \, A \subset S, \, B \subset S[/tex] е изпълнено:
[tex]f(A\cup B) \leq \max\left(f(A),f(B)\right)[/tex].

Докажете, че различните значения, които [tex]f[/tex] може да приема са не повече от n.

[drago]

Ето една подобна:
viewtopic.php?f=10&t=7391
обаче приликата е само външна.

[Baronov]

Нека различните стойности, които функцията приема са [tex]\{x_1, x_2\dots x_k\}[/tex]. Тогава [tex]A_i=\{S: f(S) \leq x_i\}[/tex] е [tex]\sigma[/tex]-алгебра за всяко [tex]i[/tex]. Броят не елементите на всяка крайна [tex]\sigma[/tex]-алгебра е степен на 2...

[Гост]

Да, така е, но защо броят на различните стойности на [tex]f[/tex] e не повече от [tex]n[/tex] ?

[drago]

Нека различните стойности, които функцията приема са [tex]\{x_1, x_2\dots x_k\}[/tex]. Тогава [tex]A_i=\{S: f(S) \leq x_i\}[/tex] е [tex]\sigma[/tex]-алгебра за всяко [tex]i[/tex]. Броят не елементите на всяка крайна [tex]\sigma[/tex]-алгебра е степен на 2...

Хм, хитро, но все пак е давана на олимпиада за ученици и не можеш да очакваш, че го знаят наготово.
Моето решение: http://www.artofproblemsolving.com/Foru ... 7#p2869267
Между другото от представянето на алгебрата като всевъзможни обединения на минималните си елементи се вижда, че броят на елементите и са степен на 2.