dgrozev wrote: Let $M$ be a set of $2017$ positive integers. For any subset $A$ of $M$ we define $f(A) := \{x\in M\mid \text{ the number of the members of }A\,,\, x \text{ is multiple of, is odd }\}$. Find the minimal natural number $k$, satisfying the condition: for any $M$, we can color all the subsets of $M$ with $k$ colors, such that whenever $A\neq f(A)$, $A$ and $f(A)$ are colored with different colors. $x$ is multiple of what?

Better wording: dgrozev wrote: Let $M$ be a set of $2017$ positive integers. For any subset $A$ of $M$ and for every $x\in M$ we define $$x\in f(A)\mid \text{The number of elements in }A\text{ that }x\text{ is multiple of is odd}$$Find the minimal natural number $k$ satisfying the condition: For any set $M$, we can color all the subsets of $M$ with $k$ colors such that whenever $A\neq f(A)$, $A$ and $f(A)$ are colored with different colors.

Progress 'cause I have to go on mobile for a while: Note that $f:\mathcal{P}(M)\mapsto \mathcal{P}(M)$ generates an endomorphism-associated digraph. For the sake of our problem, we can de-direct it. In particular, each connected component consists of a cycle with trees emanating from each vertex of said cycle. The chromatic number of the overall graph is clearly the maximum of the chromatic numbers of each of the connected components. It is not hard to see that we can color each connected component with at most three colors (in the case of an odd cycle) and at most $2$ colors otherwise. Now I found many constructions for $k=2$, but I can't find any nontrivial (i.e. non self-referential) odd cycle I claim that no such cycle exists and that $k=2$, but I don't quite have a proof. The worst that could happen is that I am wrong and that $k=3$, so...

As it turns out, I think $\boxed{k=2}$ was correct. The idea is to let $A_0,A_0,\dots,A_{n-1},A_0$ be a primitive cycle. (So $A_{i+1}=f(A_i)$ and $A_i=A_j\implies i=j$ with indices being taken modulo $n$.) Furthermore let the cycle be non self-referential; i.e. $n>1$. Consider the set $Q$ of maximal elements of the poset $\left(\bigcup A_i,\mid\right)$. It is readily seen that an element is in $Q$ iff it is maximal in each $A_i$. Now consider the set $R$ of maximal elements of the poset $\left(\bigcup A_i\setminus Q,\mid\right)$. $R$ is nonempty by non self-referentiality. It is not hard to show that for any $r\in R$ we have $r\in A_i\iff r\not\in A_{i+1}$. It follows that $2\mid n$, as desired $\blacksquare$ Edit: This should be read as a continuation of post 4

Yes, you are right. Generally speaking, I could understand it. Could you explain that part: rafayaashary1 wrote: ...Consider the set $M$ of maximal elements of the poset $\left(\bigcup A_i,\mid\right)$. It is readily seen that an element is in $M$ iff it is maximal in each $A_i$... What does $\left(\bigcup A_i,\mid\right)$ mean? rafayaashary1 wrote: $f:\mathcal{P}(M)\mapsto \mathcal{P}(M)$ generates an endomorphism-associated digraph... I'm not pedantic, but it's not an endomorphism . A morphism preserves some structure, which is not the case here. Comment: The official solution in addition uses the fact $f$ is an injection, which can be checked easily. Then each component of that graph is a cycle of even length. As you noted, it's not essential to prove $k=2$.

Oops, as it turns out, overloading the labels $M$ and $n$ doesn't help the legibility of my post I have changed some of the labels (but nothing else) in post 5 if it helps. The main idea in the section you pointed out is to look at the union $A_0\cup A_1\cup\cdots\cup A_{n-1}$ as a poset under divisibility. In particular, we consider the maximal elements: those that divide no other in the set (it is possible that there are many of these). Let $Q$ be the set of said maximal elements. We first want to show that $q\in Q\text{ and }q\in A_i\implies q\in A_{i+1}$. But this is true because $q$ has, by definition, exactly $1$ multiple in $A_i$ (which is $q$ itself), and $A_{i+1}=f(A_i)$. If follows that $Q\subseteq A_i$ for all $i$. Our next idea is then to consider $A_0\cup A_1\cup\cdots\cup A_{n-1}\setminus Q$ as a poset under divisibility. Again we consider the maximal elements, call them $R$ this time. If $R$ is nonempty, it is easily seen that we must have $A_0=f(A_0)$ (or in other words $n=1$) because each $A_i$ must be exactly $Q$ (no more by the inclusion above, no less by the union below). So we need only show that if $n>1$, or in other words $R$ is nonempty then we must have $2\mid n$. But I claim that $r\in R$, if it exists, must occur in sets $A_i$ in an alternatin fashion. That is, we need (and it suffices) to show that $r\in A_i\implies r\not\in A_{i+1}\text{ and } r\not\in A_i\iff r\in A_{i+1}$. This, however, is a consequence of the inclusion above, and the fact that by definition the only possible multiples of $r$ in $A_0\cup A_1\cup\cdots\cup A_{n-1}$ are $r$ and elements of $Q$ $\Box$ Note that it is not really necessary to use poset terminology; mainly I just wanted to talk about maximal elements in a familiar and motivated context. One last thing: the function is an endomorphism in the category Set (But on a serious note, I agree that it is a misleading terminology. The main reason I used the phrase was because I originally saw the idea in a paper dealing with groups.)

Ok, I see, $\left(\bigcup A_i,\mid\right)$ means poset under divisibility. I assume $a\prec b$ iff $a\mid b$, since it complies with: rafayaashary1 wrote: we consider the maximal elements: those that divide no other in the set Now, there is something wrong here: rafayaashary1 wrote: $q\in Q\text{ and }q\in A_i\implies q\in A_{i+1}$. But this is true because $q$ has, by definition, exactly $1$ multiple in $A_i$ (which is $q$ itself), That's, you should either take the minimal elements, or flip around the relation "precedes". Or simpler, instead of it, write something like that: Let $\bigcup A_i=\{a_1<a_2<\dots<a_m\}$ and $j$ be the first index such that $\#\{i\mid 1\leq i\leq j, a_i\mid a_j \}$ is even. If such index doesn't exists then $f(A_i)=A_i$, so its a isolated vertex. Otherwise, it can be easily checked that $a_1,\dots,a_{j-1}$ belong to all $A_i$'s and the belonging of $a_j$ ocurr alternatively.

Ah, indeed there is an overbearing assumption in the second quote. I have a fix that is not substantially different from yours; let $Q_0$ be the set of maximal elements of $\bigcup A_i$ and let $Q_{k+1}$ be the set of maximal elements of $\bigcup A_i\setminus Q_0\setminus Q_1\setminus \cdots \setminus Q_k$. We look first in $Q_1$ for an element with an odd number of multiples in $Q_0$. If that doesn't exist, we look for an element of $Q_2$ that has an odd number of multiples $Q_0\cup Q_1$, and so on until either we find such an element (done because then the sketchy claim is actually true) or no such element exists (done because then the function evaluated at the set is itself).

In fact, I think it can be shown that all cycle lengths are powers of two, which trivializes the problem.

The answer is $2$. We will prove the general version with $2017$ replaced by $n$. CLAIM 1. $f$ is a bijection on the set $2^M$. Proof. We will use induction on $n$. Suppose $f(A)=f(B)$ for some $A,B\in M$. Now it is easy to show that the smallest element of a set is preserved by $f$. Therefore, the smallest element of $A$ and $B$ are equal. Let this element be $s$. Let $S$ be the set of multiples of $s$. Now, for a set $X$ define $X_s=X\setminus(X\cup S)$. Let $f_s$ be the corresponding operation in $M_s$, then notice for every $a\in M_s$, the number of divisors of $a$ in $A_s$ is same as the number of divisors of $a$ in $A$. Therefore $$f_s(A_s)=(f(A))_s=(f(B))_s=f_s(B_s)$$Since $|M_s|<M$ we have $$A_s=B_s$$by inductive hypothesis. Now for a set $X$ which contains $s$ define $X_1=X\setminus\{s\}$. Let $f_1$ be the corresponding operation in $M_1$. Now notice that $$f_1(A_1\setminus{A_s})=M_1\setminus ((f(A))_1\setminus (f(A))_s)=M_1\setminus ((f(B))_1\setminus (f(B))_s)=f_1(B_1\setminus{B_s})$$Since $|M_1|<M$ we have $A_1=B_1$, so $A=B$ as desired. $\blacksquare$ This shows that $f$ can be decomposed into cycles and fixed points. CLAIM 2. All cycles of $f$ are even. Proof. Let $A$ be a set and define $A_i=f^i(A)$. Suppose this cycle has length $t$. Then consider the functions $g_i(m):M\to{1,-1}$ defined by $$g_i(m)=\begin{cases} 1&\text{if }m \text{does belong to } A_i\\ -1&\text{if }m \text{does not belong to } A_i\end{cases}$$Let $n$ be the smallest integer such that $g_0(n)\neq g_1(n)$. Then all numbers smaller than it are invariant by $f$, therefore $g_i(n)=g_0(n)$ if and only if $i$ is even, so we are done. $\blacksquare$. Therefore, we can color all the cycles of $f$ using $2$ colors as desired.

I'm surprised I didn't notice the connection to this problem earlier.