interesting function $S$ is a set with $n$ elements and $P(S)$ is the set of all subsets of $S$ and $f : P(S) \rightarrow \mathbb N$ is a function with these properties: for every subset $A$ of $S$ we have $f(A)=f(S-A)$. for every two subsets of $S$ like $A$ and $B$ we have $max(f(A),f(B))\ge f(A\cup B)$ prove that number of natural numbers like $x$ such that there exists $A\subseteq S$ and $f(A)=x$ is less than $n$. time allowed for this question was 1 hours and 30 minutes.
Problem
Source:
Tags: function, abstract algebra, algebra proposed, algebra
17.09.2010 16:11
I know a related conclusion: for any\[w\in \mathbb{R}\], the number of subsets $A$ such that \[f\left( A \right)\le w\] is zero or always a power of 2.
17.09.2010 16:44
does it help to solve the question?
18.09.2010 10:47
goodar2006 wrote: does it help to solve the question? The original conclusion holds iff there are not exactly n different values. Sorry for my poor spare time, or i'll post a solution.
18.09.2010 11:23
would you please post your solution if you had time?
09.11.2012 20:37
assume that $A$ is family of subsets like $X$ such that $f(X)\leq w$ for some $w\in \mathbb{N}$ then one can check that $A$ is a group with operation $\Delta$. so by lagrange's theorem we have $\left | A \right |$ divides $2^{n}$.
06.12.2012 00:04
Let all different values $f$ can take are $w_1<w_2<\ldots <w_m $. Notice that $\mathcal{B}_i = \{X\,|\, X\in P(S), f(X) \leq w_i \}$ is a boolean algebra- closed under union, intersection and taking complement of its elements. For example $B_1=\{\emptyset, S\}$, because if we assume that $f(S_1) < f(S)$ for some $S_1 \subsetneq S$, then $f(S) \leq \max\left(f(S_1), f(S\setminus S_1)\right) < f(S)$, contradiction. $\mathcal{B}_i$ can be generated of its atoms $A^{i}_{1},A^{i}_{2},\ldots, A^{i}_{k}$ , which are disjoint and form a partition of $S$.($A^{i}_{j}$ are all non empty minimal elemts of $\mathcal{B}_i$ under relation $\subset$). $\mathcal{B}_i = \left\{\bigcup_{j\in J} A^{i}_{j}\,|\, J\subset [k] \right\}$. Now notice the connection between the generating atoms of $\mathcal{B}_i$ and $\mathcal{B}_{i+1},\, \mathcal{B}_{i}\subsetneq \mathcal{B}_{i+1}$. If $A^{i}_{j},j=1\ldots k$ are the generating atoms of $\mathcal{B}_i$ then the generating atoms of $\mathcal{B}_{i+1}$ are: $A^{i+1}_{j,s}, j=1,\ldots k, s=1,\ldots, s(j)$, $\bigcup_{s=1}^{s(j)} A^{i+1}_{j,s} = A^{i}_j$. here at least one $s(j),\, j=1,2,\ldots,k$ is greater than $1$, since $\mathcal{B}_{i}\subsetneq \mathcal{B}_{i+1}$. It is clear now why $m \leq n$.
08.12.2012 08:48
One more sentence to finilize things. If $\|\mathcal{B}_i\|$ denotes the number of atoms of $\mathcal{B}_i $ , we have: $1 \leq \|\mathcal{B}_1\|<\|\mathcal{B}_2\|<\ldots < \|\mathcal{B}_m\| \leq n $. Therefore $m \leq n$. It is possible to construct an example of $f$ with exactly $n$ different values. This problem, as a statement, is similar to http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=438356 But the ideas behind the solutions are not so similar.
02.11.2019 20:28
The key idea in the following solution is to replace the $\cup$ operation with $\oplus$ ("XOR"). The following two lemmas do just that. We will also use $!T$ to denote $S - T$, for $T \subseteq S.$ Lemma 1. $f(A \cap B) \le \max(f(A), f(B)).$ Proof. Notice that $f(A \cap B) = f(! (A \cap B)) = f((!A) \cup (!B)) \le \max(f(!A), f(!B)) = \max(f(A), f(B))$, and so we're done. $\blacksquare$ Lemma 2. $f(A \oplus B) \le \max(f(A), f(B))).$ Proof. Note that $A \oplus B = (A \cup B) \cap (!(A \cap B))$. Hence, we have from Lemma $1$ that: $$f(A \oplus B) \le \max(f(A \cup B), f(!(A \cap B))) = \max(\max(f(A), f(B)), f(A \cap B)) = \max(f(A), f(B)).$$ $\blacksquare$ Now, let the values attained by $f$ be $v_1 < v_2 < \cdots < v_k.$ Let $S_i \subseteq P(S)$ denote the set of subsets $T$ of $S$ so that $f(T) \in \{v_1, v_2, \cdots, v_i \}.$ Observe that to each subset $T \in P(S)$, we can associate a string in $\{0, 1\}^n$ in the obvious way ($1$ if an element is in $T$, $0$ else). Now, let $T_i$ be the set of associated binary strings of all the subsets of $S_i.$ Now, observe that $T_i$ is a subspace of $\{0, 1\}^n$ for each $1 \le i \le k.$ Indeed, if $a, b \in T_k$, then applying Lemma $2$ on the subsets of $S$ corresponding to $a, b$ imply that $a+b \in T_k$ as well. Hence, it makes sense to let $n_i$ be the dimension of $T_i$ for each $1 \le i \le k$. We've that $t_1 \ge 1$ because $000 \cdots 0, 111 \cdots 1 \in T_1.$ It's also clear that $n_{i+1} > n_i$ for each $1 \le i < k$ (as $T_{i+1} - T_i$ is nonempty). Together with $n_k = \dim P(S) = n$, we have that $k \le n$, as desired. $\square$