For any subset $S$ of $T$, define an enemy of $S$ to be an integer in $T$ that is coprime to all elements of $S$. Observe that a good set does not have an enemy. For any set $S$, let $f(S)$ denote the set of all enemies of $S$. (So, if $S$ is a good subset, $f(S) = \phi$.) For any two subsets $A,B$ of $T$, call the ordered pair $(A,B)$ bad iff for any $x \in A$ and $y \in B$, $gcd(x,y) = 1$. It is trivial that the number of these ordered pairs is odd (if $(A,B)$ is a pair, then $(B,A)$ is a pair, and $( \phi , \phi )$ is the only pair of the form $(A,A)$). Now, for any subset $X$ of $T$, the number of bad pairs of the form $(X,S)$ is equal to $2^{|f(X)|}$ because $(X,S)$ is bad iff $S$ is a subset of $f(X)$. Since $2^{|f(X)|}$ is odd iff $|f(X)|=0$ iff $X$ is a good subset, the above two facts imply that the number of good subsets of $T$ is odd. This problem can also be interpreted in a graphical way: denote the elements of $T$ as vertices of a graph, and connect two vertices $A$ and $B$ iff the numbers corresponding to $A$ and $B$ are not coprime - then we can observe this as a problem in graph theory.

very easy with inclusion-exclusion principle.

I want to see this inclusion-exclusion solution. Even if there is one, I don't think this problem can possibly be called easy.

A few observations. In the graph interpretation, it is enough to consider the graph $G = (V,E)$ as being of minimal degree $\delta(G) \geq 1$ (also, loops are allowed), and define a set of vertices $S \subseteq V$ as being good if and only if every vertex of the graph is connected to at least one from $S$. Under these definitions, the empty set $\emptyset$ is vacuously not good, while $V$ is always good. Any good set must clearly contain at least a vertex from each connected component of $G$. This leads to the second observation. The use of the divisibility relation is irrelevant - it needs not be a partial order relation. Any other, so that each element is in relation to at least another one, or to itself, is enough (otherwise, if some element is isolated, there clearly are no good sets). Finally, the vacuousness of the fact the empty set is not good is kind of contrived - it would have been better to just forbid it in the thesis.

Dear my friends ; Here is a good reference for that problem

Let $ P(S)=\{ p_{1}, p_{2}, ..., p_{k}\} $ be set whose member is all prime divisors of $S$, and $S_{i}$ be subset of $S$, whose element is the multiples of $p_{i}$ in $S$. Then the number of good subsets is $ 2^{|S|} + \sum_{\phi \not= I\subset [k] }{(-1)^{|I|+1}} 2^{ |S/\bigcup_{i \in I}S_{i}|} $ . But, if $I= [k]$, then, $2^{ |S/\bigcup_{i \in I}S_{i}|} =1 $, otherwise each $2^{ |S/\bigcup_{i \in I}S_{i}|} $ is even number. So the parity of the number of good subsets is odd. Is it right? Sorry for my poor answer and and my poor english.

luapsedree wrote: otherwise each $2^{ |S/\bigcup_{i \in I}S_{i}|} $ is even number. This is what I don't think is true, unless I'm misunderstanding what you're trying to say. It's possible for the union of the $S_i$ to equal $S$ even if $I$ is not everything (say for example $T=\{6,10,15\}$, so that $S_1=\{2,3\}, S_2=\{2,5\},S_3=\{3,5\}$). In fact, I think that the statement $\cup S_i=S$ is equivalent to $I$ being good, which means that inclusion/exclusion doesn't tell you anything modulo $2$.

My solution (rather long please check and tell me if it is wrong) Suppose $|T|=n$.We call a subset $S$ of $T$ bad if there exists $t \in T$ such that $gcd(s,t)=1 \forall s \in S$. There are $2^n-1$ non empty subsets of $T$.So to prove the number of good subsets is odd,we prove the number of bad subsets is even. Denote by $B_n$ the set of bad subsets of $T_n$ Let $f(n)$ be the number of bad subsets of $|T_n|=n$.Each element is a person and define $a$ knows $b$ iff $gcd(a,b)=1$.Suppose $f(k)$ is even $\forall k \leq n$,we prove that $f(n+1)$ is even We find $f(n+1)$=the number of bad subsets of $T_{n+1}$ Consider a person $m$,who knows exactly $k$ of the others. There are 2 types of bad subsets of $T_{n+1}$ 1) not containing $m$:there are $f(n)$ bad subsets 2) containing $m$: there are 2 subcases: a) $T_{n+1}$ \ $\{m\}$ is bad : there are $f(n)$ bad subsets. b) $T_{n+1}$ \ $\{m\}$ is good: In this case $m$ must know every members of $B_{n+1}$ => there are $2^k$ bad subsets. subcase a) and b) also has $f(k)$ bad subsets in common. So we have $f(n+1)=2f(n)+2^k-f(k)$=> the number of bad subsets is even,QED.

could you define $T_n$?

@qwerty414: Very nice double counting solution. (I have fixed a few typos: four $S$'es that were meant to be $X$'es.) @mavropnevma: mavropnevma wrote: A few observations. In the graph interpretation, it is enough to consider the graph $G = (V,E)$ as being of minimal degree $\delta(G) \geq 1$ (also, loops are allowed), and define a set of vertices $S \subseteq V$ as being good if and only if every vertex of the graph is connected to at least one from $S$. Under these definitions, the empty set $\emptyset$ is vacuously not good, while $V$ is always good. Any good set must clearly contain at least a vertex from each connected component of $G$. You must require the condition that every vertex of $G$ is connected to itself; otherwise the number of good subsets needs not be odd (counterexample: triangle graph). @KDS: I don't understand your proof.

Sorry for the old bump, found this problem super interesting and made an account to post my proof. Feedback welcome Observe that any $t \in T$ that is pairwise coprime with all other $t \in T$ must be an element of any good set $S$. This follows from the definition of coprimality; if $t_1 \notin S$, then $gcd(t_1, t) = 1 \forall t$. Now we will construct the set $\bf{S}$ of all good sets $S$. Note that we can remove any $t \in T$ that has a noncoprime partner without loss of "good" status. We will call these elements "replaceable". The set $T_{replaceabel}$ = $\{t_1,t_2...t_n\}$. From $T$, omit any proper subset of $T_{replaceable}$, and the resulting set is good. The number of ways of doing this is clearly represented by the cardinality of the Power Set of $T_{replaceable}$, sans the subset $T_{replaceable}$ itself (following from the definition of proper subset). Let $P(A)$ denote the power set of $A$. By the cardinality of power sets theorem (widely available), $\mid P(T_{replaceable}) \mid$ = $2^n$, where n = $\mid T_{replaceable} \mid $. Our $\mid \bf{S}$ is then equal to $\mid P(T_{replaceable}) \mid - 1$, which reduces to $2^n -1$ for some $n \in Z^+$. This quantity is trivially odd, and we are done.

Here's a solution that I don't see above yet. I can't word the first part combinatorially but the finish is. The problem is asking for us to show that the number of dominating sets in a graph is odd. Let $x_i$ be the variable representing whether the $i$-th vertex is chosen, and say the graph has $n$ vertices. $x_i = 0$ if not, else $x_i = 1$. Let $N(v)$ denote the neighbor set of a vertex $v$, and $N(v)$ includes $v$ itself. Note that the number of dominating sets is \[ \sum_{x_i = 0, 1} \prod_v \left(1 - \prod_{u \in N(v)} (1-x_u) \right). \]The sum is over all $2^n$ ways to assign $x_i = 0$ or $1$ for each $i$. To abuse notation, for a subset $S$ of the vertices, let $x_S = \prod_{v \in S} x_v.$ Looking back at the above sum and taking mod 2, we get \[ \sum_{x_i = 0, 1} \prod_v \left(1 - \prod_{u \in N(v)} (1-x_u) \right) = \sum_{x_i = 0, 1} \prod_v \left( \sum_{\emptyset \not= S \subseteq N(v)} x_S \right). \] Imagine expanding out the product. Then the $\sum_{x_i = 0, 1}$ kills all terms that do not have all the variables when taking $\pmod{2}.$ Indeed, if some monomial contains only $m$ variables, the sum over it evaluates to $2^{n-m}$ obviously. So the final sum is really computing the number of ways to pick a nonempty subset $S_v$ of each $N(v)$ such that every vertex is contained in at least one of the subsets. Now consider the adjacency matrix of $G$ (with $1$'s along the main diagonal). In the row $v$, circle the elements belonging to $S_v.$ If every column has at least one circled $1$, call the circling valid. Now, consider reflecting the circled elements over the main diagonal. Since every vertex was contained in some subset, the reflection across the main diagonal is also a valid way of choosing subsets. Therefore, it suffices to show that the number of valid ways of choosing subsets such that the resulting circles are symmetric wrt to main diagonal is odd. First circle some pairs of $1$'s in the adjacency matrix, without circling any $1$'s along the main diagonal. Now consider the number of ways of circling some $1$'s along the main diagonal to make the circling valid. Now we have to circle some of the $1$'s on the main diagonal. We must circle the $1$'s that have no elements already circled in their row/column, and the other ones can be either circled or not. Therefore, if there is at least one $1$ along the main diagonal that has something circled in its row, the total number of valid ways to circle some $1$'s on the main diagonal is even. If nothing is initially circled, we must circle every $1$ on the main diagonal, for a contribution of $1$, so the total is odd.

Let $P$ denote the set of all primes that divide some elements of $T$. For an integer $X$ and prime $p$, we let $1_{X\equiv 0(p)}$ equal $1$ if $p$ divides $X$, and equal 0 otherwise. A subset $S$ of $T$ is good exactly when \[ \prod_{s\in S}^{}\prod_{p\in P}^{} (1 - 1_{s\equiv 0(p)}1_{t\equiv 0(p)}) = 0 \]for every $t\in T$, where we use the convention that the empty product is $1$. So we see that a subset $S$ of $T$ is good exactly when \[\prod_{t\in T}^{} (1 - \prod_{s\in S}^{}\prod_{p\in P}^{} (1 - 1_{s\equiv 0(p)}1_{t\equiv 0(p)})) = 1 \]and is equal to $0$ otherwise. So the number of good subsets of $T$ is just \[\sum_{S \subseteq T}^{} \prod_{t\in T}^{} (1 - \prod_{s\in S}^{}\prod_{p\in P}^{} (1 - 1_{s\equiv 0(p)}1_{t\equiv 0(p)})), \]where the sum is taken over all subsets $S$ of $T$. We only are interested in the parity of the number of good subsets of $T$, so after reducing modulo 2, the number of good subsets of $T$ modulo 2 is \[\sum_{S \subseteq T}^{} \prod_{t\in T}^{} (1 + \prod_{s\in S}^{}\prod_{p\in P}^{} (1 + 1_{s\equiv 0(p)}1_{t\equiv 0(p)})). \]We expand out to the product over elements of $T$ to get that the number of good subsets of $T$ modulo 2 is \[\sum_{S \subseteq T}^{} \sum_{S^\prime \subseteq T}^{} \prod_{t\in S^\prime}^{} \prod_{s\in S}^{}\prod_{p\in P}^{} (1 + 1_{s\equiv 0(p)}1_{t\equiv 0(p)}), \]where $S^\prime$ ranges over all subsets of $T$ Now we define \[f(S,S^\prime ) = \prod_{t\in S^\prime}^{} \prod_{s\in S}^{}\prod_{p\in P}^{} (1 + 1_{s\equiv 0(p)}1_{t\equiv 0(p)}) \]where $S$ and $S^\prime$ are subsets of $T$. Note that \[f(\emptyset, \emptyset) \equiv 1 (2)\]by our convention that the empty product is equal to 1. We note that for a non-empty subset $S$ of $T$, we have that \[f(S,S) \equiv 0 (2).\]Indeed, choose an $x\in S$ and a prime $p\in P$ that divides $x$. Then one of the terms of the product will be $(1 + 1_{x\equiv 0(p)}1_{x\equiv 0(p)}) \equiv 0 (2)$. We also note that for two non-empty distinct subsets $S$ and $S^\prime$ of $T$, we have \[f(S,S^\prime) \equiv f(S^\prime, S) (2).\]This follows directly from the fact that $f(S,S^\prime)$ is symmetric with respect to $S$ and $S^\prime$, which can be observed simply by noting the form that the product that defines $f$ takes. If we can show that \[\sum_{S \subseteq T}^{} \sum_{S^\prime \subseteq T}^{}f(S,S^\prime) \equiv 1 (2), \]then we will be done. We can pair off the "off diagonal" terms where $S \neq S^\prime$, so that part of the sum contributes $0$ modulo $2$. As for the "diagonal terms" where $S = S^\prime$, we will always contribute a $0$ to the sum except for the term $f(\emptyset, \emptyset)$, which contributes $1$ modulo $2$ to the sum, so we are done.

We prove that the number of dominating sets of a finite graph $G$ is odd. Let $S$ be the set of all pairs of disjoint subsets $V_1,V_2\subseteq V(G)$ such that there are no edges between $V_1,V_2$. Consider the following function \[1_D(V_1)=|\{V_2\subseteq V(G)|(V_1,V_2)\in S\}| \pmod 2\]We claim that this is the indicator function for whether $V_1$ is dominating. Let $V_1'$ be the set of vertices not adjacent to any vertex in $V_1$. Then clearly the $V_2$ in the definition of $1_D$ are precisely the subsets of $V_1'$, so the number of subsets is odd precisely when $V_1'=\emptyset$, i.e. $V_1$ is dominating. Thus we wish to consider \[\sum_{V_1\subseteq V(G)} 1_D(V_1)\pmod 2\]But $1_D(V_1)=\sum_{V_2\subseteq V(G)} 1_{(V_1,V_2)\in S}\pmod 2$ So we are considering \[\sum_{V_1\subseteq V(G)}\sum_{V_2\subseteq V(G)} 1_{(V_1,V_2)\in S} \pmod 2\]But the double sum is precisely the number of elements of $S$, so we wish to show that $|S|$ is odd. But this is clear: every element $(V_1,V_2)\in S$ corresponds to another element $(V_2,V_1)\in S$, and these are equal only at $(\emptyset, \emptyset)$, thus the involution has only one fixed point, implying that $|S|$ has odd parity.

adamov1 wrote: Let $V_1'$ be the set of vertices not adjacent to any vertex in $V_1$. "... and not equal to any vertex in $V_1$", you forgot to add. Otherwise, a nice proof! We can say more about the number of dominating sets, as was recently found by Heinrich and Tittmann (arXiv:1701.03453v1): Theorem. Let $G$ be a simple graph, and let $V$ be the set of its vertices. Let $n$ be the size of $V$. Assume that $n > 0$. A detached pair shall mean a pair $\left(A, B\right)$ of two disjoint subsets $A$ and $B$ of $V$ having the property that there is no edge connecting a vertex in $A$ to a vertex in $B$. Let $\alpha$ be the number of all detached pairs $\left(A, B\right)$ for which both numbers $\left|A\right|$ and $\left|B\right|$ are even and positive. Let $\beta$ be the number of all detached pairs $\left(A, B\right)$ for which both numbers $\left|A\right|$ and $\left|B\right|$ are odd. Then: (a) The numbers $\alpha$ and $\beta$ are even. (b) The number of dominating sets of $G$ is $2^n - 1 + \alpha - \beta$. The "detached pairs", of course, are the elements of the set you call $S$, but the above theorem gives an actual equality, not just a congruence modulo $2$. (Heinrich and Tittmann state a result equivalent to the Theorem, speaking of bipartite induced subgraphs of the complement graph of $G$ instead of detached pairs; thus, their $a\left(G\right)$ and $b\left(G\right)$ correspond to what I call $\alpha/2$ and $\beta/2$, respectively.) I give a completely elementary proof of the Theorem in my unfinished Notes on graph theory (see Theorem 3.2.2).

Let $G$ be a graph with vertex set $T$, and $s,t\in T$ are connected if and only if $\gcd(t,s)>1$. The problem asks us to show that $G$ has an odd number of dominating sets (a dominating set is a set of vertices $X$ such that each vertex of $G$ is either in $X$ or is adjacent to an element of $X$). Incidentally, it is not hard to see that any simple graph $G$ can arise over all $T\subset\mathbb{N}$. Main Idea. Let $P$ be the number of ordered pairs $(A,B)$ where $A,B\subset T$ and $A\cap B=\emptyset$, and no vertices of $A$ are adjacent to any vertices of $B$ (I did not come up with this on my own, I'm not really sure how one would come up with it). At this point the rest is straightforward. Clearly if $(A,B)$ is a valid pair, so is $(B,A)$, and since the only pair of the form $(A,A)$ is $(\emptyset,\emptyset)$, $P$ is odd. Now, consider the number of valid pairs for some fixed $A$. Let $x$ be the number of vertices that $A$ is not adjacent to. Then, the number of pairs of the form $(A,B)$ is $2^x$, which is odd if and only if $A$ is a dominating set. Thus, $P$ is equal to the number of dominating sets if we work mod $2$, but since $P$ is odd, we are done.

Consider the subsets of $T$ as the vertices of a digraph, and join two sets iff all elements of one set are coprime to all elements of the other set. We count the number of edges, in this case. The number of vertices connected to a non-good vertex $v$ must be even (a vertex $x$ connected to $y$ means that a directed edge from $y$ to $x$ exists), since for any vertex $w$ connected to $v$, the vertex corresponding to the set of remaining elements of $T$ and coprime to all elements of $v$ should also be connected to $v$. Since the total number of edges is odd (only the null set has a loop, and all pairs of vertices have exactly 2 edges), the number of vertices emanating from good vertices must be odd. There is only one vertex connected to a good vertex, and it corresponds to $\null$, so the number of good vertices equals the number of edges from good vertices, which is odd, completing our proof.

Inclusion exclusion approach. We count the number of subsets which are not good. For brevity any non good subset we call a bad subset. Let $\mathcal{B}$ be the family of bad subsets and we exclude the empty set from $\mathcal{B}$. We should prove $|\mathcal{B}|$ is even. Note that a set $B\in \mathcal{B}$ if and only if there exists $t\in T$, such that $\gcd(t,b)=1$ for all $b\in B$. Let us construct a graph $G$ with set of vertices $V=S$ and $v_1,v_2\in V$ are connected iff $\gcd(v_1,v_2)=1$. Then a set $B\subset V$ is bad iff there exists a vertex $v\in V$ connected with all vertices in $B$. Thus, it boils down to prove that in every simple graph $G(V,E)$ the set of all bad subsets is even. Let $V=\{v_1,v_2,\dots,v_n \}$. Denote by $V_i,i=1,2,\dots,n$ the set of all vertices of $G$ connected with $v_i$. By $\mathcal{V}_i,i=1,2,\dots,n$ we denote the family of all non empty subsets of $V_i$. Then $\mathcal{B}=\bigcup\limits_{i=1}^n \mathcal{V}_i$. By inclusion exclusion principle: $$\left|\bigcup\limits_{i=1}^n \mathcal{V}_i\right| = \sum_I (-1)^{|I|+1} \left|\bigcap_{i\in I}\mathcal{V}_i\right| $$where the summing in the RHS is over all $I\subset\{1,2,\dots,n\}$. Note that $\bigcap_{i\in I}\mathcal{V}_i$ in fact is the set of all non empty subsets of $\bigcap_{i\in I}V_i$. Their number is odd iff $\bigcap_{i\in I}V_i\neq \emptyset.$ Hence: $$\left|\bigcup\limits_{i=1}^n \mathcal{V}_i\right| \equiv \left|\{I\mid \bigcap_{i\in I}V_i\neq \emptyset \}\right| \pmod 2.$$So, we should prove the RHS is even. The following observation is crucial to make further progress. For any $I_1,I_2\subset \{1,2,\dots,n\}$, if $\{v_i : i\in I_2\}\subset \bigcap_{i\in I_1}V_i$ then $\{v_i : i\in I_1\}\subset \bigcap_{i\in I_2}V_i$. Indeed, if $v_i\in V_j$ then $v_j\in V_i$. In other words it simply means that if $v_i$ is connected with $v_j$ then $v_j$ is connected with $v_i$. It resembles of some parity between collections of $V_i$'s with non empty intersection. To exploit this idea let us consider a bipartite graph $G'$ with vertices $\mathcal{V}'$ and $\mathcal{V}''$, where $\mathcal{V}'$ consists of all subsets $\{V_i : i\in I\}$ for which $\bigcap_{i\in I}V_i\neq \emptyset$ and $\mathcal{V}''$ consists of all non empty subsets $V''\subset V$. We connect $V'\in \mathcal{V}'$ with $V''\in \mathcal{V}''$ iff $V'' \subset \bigcap V'$. Thus, every $V'\in\mathcal{V}'$ is connected with odd number of vertices of $\mathcal{V}''$. Hence the number of edges of $G'$ has the same parity as the number of vertices of $\mathcal{V}'$ which is $\left|\{I\mid \bigcap_{i\in I}V_i\neq \emptyset \}\right|$. On the other hand, as said above, there is a symmetry of edges in $G'$: if $\{V_i : i\in I_1\}$ is connected with $\{v_i : i\in I_2\}$ then $\{V_i : i\in I_2\}$ is also connected with $\{v_i : i\in I_1\}$. Combining it with the fact $\{V_i:i\in I\}$ is not connected with $\{v_i:i\in I\}$ (because $v_i\not\in V_i,i=1,2,\dots,n$), we obtain that the number of edges of $G'$ is even, meaning $\left|\{I\mid \bigcap_{i\in I}V_i\neq \emptyset \}\right|$ is even.

MellowMelon wrote: Let $T$ be a finite set of positive integers greater than 1. A subset $S$ of $T$ is called good if for every $t \in T$ there exists some $s \in S$ with $\gcd(s, t) > 1$. Prove that the number of good subsets of $T$ is odd. Solution. Consider the graph $G$ whose vertex set is $T$ and two numbers are adjacent if and only if they are not relatively prime, we basically want to show that the total number of dominating sets of the graph is odd. Let the vertex set be $S_n=\{1,2,\ldots,n\}.$ Define $e_{ij}$ to be $1$ if $i$ and $j$ are adjacent, and $0$ otherwise. Observe that a non empty subset $S\subset S_n$ is dominating if and only if $$\prod_{k\in (S_n\setminus S)}\left (1-\prod_{x\in S}(1-e_{kx})\right)=1,$$otherwise the LHS is equal to $0.$ Therefore the total number of dominating sets is equal to $$1+\underbrace{\sum_{\substack{S\subset S_n\\ S\ne\varnothing}}\prod_{k\in (S_n\setminus S)}\left (1-\prod_{x\in S}(1-e_{kx})\right)}_{\overset{\text{def}}{=}f(G)}$$We want to show that $f(G)$ is even. Put $e_{ij}\to 1-e_{ij},$ in other words, consider the compliment. Calculating in $\mathbb{F}_2,$ \begin{align*} f(G) &= \sum_{\substack{S\subset S_n\\ S\ne\varnothing}}\prod_{k\in (S_n\setminus S)}\left (1-\prod_{x\in S}e_{kx}\right)\\ &= \sum_{\substack{S\subset S_n\\ S\ne\varnothing}}\left(1+\sum_{\substack{K\subseteq(S_n\setminus S)\\K\ne \varnothing}}\prod_{k\in K}\prod_{x\in S} e_{kx}\right)\\ &=\sum_{\substack{S\subset S_n\\ S\ne\varnothing}}\sum_{\substack{K\subseteq(S_n\setminus S)\\K\ne \varnothing}}\prod_{k\in K}\prod_{x\in S} e_{kx}\\ &= \sum_{\substack{A,B\subset S_n\\ A\cap B=\varnothing\\ A,B\ne\varnothing}}\prod_{a\in A}\prod_{b\in B} e_{ab}\\ &=\sum_{\substack{\{A,B\}\subseteq \mathcal{P}(S_n)\\ A\cap B=\varnothing\\ A,B\ne\varnothing}}\left(\prod_{a\in A}\prod_{b\in B} e_{ab}+\prod_{b\in B}\prod_{a\in A} e_{ba}\right)=0 \end{align*}In the last step, $\mathcal{P}(S_n)$ denotes the power set of $S_n.~~\blacksquare$

USA Team Selection Test 2010 Problem 6 wrote: Let $T$ be a finite set of positive integers greater than 1. A subset $S$ of $T$ is called good if for every $t \in T$ there exists some $s \in S$ with $\gcd(s, t) > 1$. Prove that the number of good subsets of $T$ is odd.

Solved with nukelauncher. We work on the graph \(G\) with vertex set \(T\) such that we have an edge \(x\sim y\) whenever \(\gcd(x,y)>1\). A dominating set \(S\) of a graph \(G\) is a set of vertices such that every vertex of \(G\) is a distance of at most one away from some element of \(S\). I contend that, for general graphs \(G\), the number of dominating sets is always odd. For each set \(X\) of vertices of \(G\), let \(h(X)\) denote the set of vertices of \(G\) a distance at least two away from the elements of \(X\). Observe that \(h(X)=\varnothing\) if and only if \(X\) is a dominating set. Consider pairs \((X,Y)\) of sets of vertices of \(G\). We say such a pair is magical if for all \(x\in X\) and \(y\in Y\), the distance between \(x\) and \(y\) in \(G\) is at least two. Evidently the number of magical pairs is odd, since \((X,Y)\) good implies \((Y,X)\) good, and the only good pair \((X,X)\) is \((\varnothing,\varnothing)\). But for each \(X\), the number of magical pairs \((X,\bullet)\) is \(2^{|h(X)|}\), since \(\bullet\) must be a subset of \(h(X)\). It follows that \begin{align*} \#\text{dominating sets} &=\#\{X:h(X)=\varnothing\} \equiv\sum_X2^{|h(X)|}\\ &=\sum_X\#\{(X,\bullet)\text{ magical}\} \equiv1\pmod2, \end{align*}as needed.

Draw the graph $G$ with there vertices being $T$ and two elements $a,b$ of $T$ being connected if $\gcd(a,b)>1$. Thus, this question is clearly asking us to show that the number of dominating subsets of $G$ is odd. (dominating subsets are sets for which all elements of $T$ are $\leq 1$ away.) To do this, we consider the set $S = \{(A,B) \mid \text{there does not exist } a\sim b,a\in A, b\in B\}$. Define $f(R)$ to be the number of points not connected to $R$. Then, if we let $X$ be the number of sets $R$ such that $f(R)=0$. \[|S| = \sum_{A\in T} 2^{f(A)} \equiv X\]However, we also know that $|S|$ is odd because as long $(X,Y)\in S$ satisfy $|X|,|Y|>0$, then $(Y,X)\in S$ too. The only time this fails is when $X=Y=\emptyset$. Thus, $X$ is odd and we're done. $\blacksquare$.

According to Teacher Yinghua Ai, this problem actually has something to do with TOPOLOGY. Also, RMM 2012/1 is a vibe. In graph theory, the RMM problem can be re-stated like this: RMM 2012/1 wrote: Let $G = U\cup V$ be a bipartite graph. Call a non-empty subset $A$ of $U$ to be "good", iff all the vertices in $A$ have a common neighbor in $V$; the same holds for a non-empty subset $B$ of $V$. We're asked to prove that the number of good subsets in $U$ has the same parity of that in $V$. Now let's see something interesting that would overkill the above problem. The theorem below was discovered in around 1950s: Based on a bipartite graph $G = U\cup V$, we can construct two topological space $X, Y$ in the following manner: $\quad \CIRCLE$ For any good subset containing only one element $A = \{a\}$, we place a point at $a$ (i.e. a 0-dimension simplex). $\quad \CIRCLE$ For any good subset with two elements $A = \{s, t\}$, we draw an edge between $s, t$ (i.e. a 1-dimension simplex). $\qquad \vdots$ $\quad \CIRCLE$ For any good subset with exactly $k$ elements, we put a $k-1$-dimension simplex connecting all those elements. Then the $\textcolor{blue}{X, Y}$ defined as above have homotopy equivalence. And, a corollary of the theorem: $\chi (X)\equiv \chi (Y)$, where $\chi (X)$ denotes the Euler indicative number. Using this theorem, we immediately killed RMM 2012/1. This TST problem can be also killed in the same way, but with some twist since we have to find some good subset which is not stated directly.

So smart it's stupid Consider the graph $G$ with elements of $T$ as vertices and an edge between $v,w$ iff $\gcd(v,w)>1$. Then a good subset of $T$ is equivalent to a dominating set of $G$—that is, a subset $S$ of vertices of $G$ such that any vertex in $G$ is either adjacent to $S$ or in $S$. Hence we will prove more generally that any graph has an odd number of dominating sets. By Brouwer et al., this is trivial, Q.E.D. The key claim is the following: Claim: A set $S \subseteq G$ is dominating if and only if there are an odd number of sets $T \subseteq G \setminus S$ such that $S$ and $T$ are nonadjacent. Proof: Suppose we have $n$ vertices that aren't adjacent to $S$. Then there are $2^n$ choices for $T$, which is odd if and only if $n=0$, which occurs precisely when $S$ is dominating by definition. $\blacksquare$ Thus to show that there are an odd number of dominating sets $S$, it suffices to show that there are an odd number of ordered set pairs $(S,T)$ such that $S$ and $T$ are nonadjacent and $S \cap T = \emptyset$. But this is clear, since $(S,T)=(\emptyset,\emptyset)$ works Every other pair satisfies $S \neq T$, so if $(S,T)$ works then so does $(T,S)$ so the desired quantity is indeed odd. $\blacksquare$ Remarks: Perhaps one of the key ideas in this problem is to shift perspectives from a set to a graph. In general, in a problem involving some set $S$ and some binary operation $f : S^2 \to \{0,1\}$ (where $0$ corresponds to false and $1$ corresponds to true), one can restate the problem in graph-theoretic terms, with elements of $S$ as vertices and an edge between $x,y$ if $f(x,y)=1$. In the case of this problem, our function is $f(x,y)=(\gcd(x,y)>1)$ (viewing it as a boolean condition like one would while programming). Another idea is the global approach. Often in these problems where we're counting something and parity/modular residues are related, one either uses global techniques (as in here or spoiler ISL 2016/C3 ), or perhaps less often, local (and usually inductive) techniques (I think spoiler USA TSTST 2020/5 doesn't fit in well at all with the other two examples, but it feels similar)

A good double counting exercise. Took hints on this one. This one can also be solved by the fact that the number of dominating subsets of a graph is odd as stated in many posts above. But here is my proof for the sake of storage. Let $N$ be the number of pairs $(I,J)$ where $I,J \in T$ and for any $i \in I$ and $j \in J$, we have $(i,j) = 1$. Note that the number $N$ is odd because if $(I,J)$ is a pair satisfying this relation, then so is $(J,I)$, the only case being $(I,J) = (\emptyset, \emptyset)$. Now for $A$ such that it is a good subset of $T$, it contributes to one such pair in $N$, being $(A, \emptyset)$. Let $X$ be the number of good subsets of $T$, then there are $X$ pairs in $N$ which have a good subset as one of the member of the pair. Now for $A$ such that is a bad subset of $T$, for any element in $A$, let there be $t$ elements in $T$ such that their gcd is one. Then like we can find $2^{t}$ subsets $B$ which can work with this set as a pair. Then the number of pairs bad subsets contribute to $N$ is even. So, we should have $X$ is odd. Hence, the claim. Remark: As @2above remarked, this can work for any boolean function $f: S^{2} \rightarrow {0,1}$, at first after seeing this problem, one can note the non relevancy of the gcd in the problem statement easily. This either leads you to the dominating subsets approach or to the double counting approach. The main motivation behind double counting (according to me and it can be wrong) is like you want to compare it to some other thing $N$ whose parity can be taken out easily. So you want this $N$ to be symmetric with some edge case in it, this can be pair of some sort. Since while trying this problem, I was not able to find this $N$, so I took a hint on it, the major part of the problem is finding this $N$. Alternate Solution: The alternate solution I found is almost the same as of CBK's solution, but this what I tried at first, I got stuck at finding the parity of the sum and I don't really know why I missed it. I am not posting it here for the sake of brevity.

Let $G$ be the graph on $T$ where $s \sim t$ if and only if $\gcd(s, t) > 1$. Let $e_{ij}$ be the indicator variable for the adjacency of $i$ and $j$ in $G$. Note that a good subset, in the context of $G$, is equivalent to a dominating set. In particular, a subset $S \subset T$ is dominating if and only if \[ \prod_{i\in T \setminus S}\left (1-\prod_{j\in S}(1-e_{ij})\right)=1, \]and is $0$ otherwise. Thus, the number of dominating sets of $T$ is given by \[ \sum_{S \subset T} \ \prod_{i\in T \setminus S}\left (1-\prod_{j\in S}(1-e_{ij})\right). \]For disjoint nonempty subsets $A$, $B$ of $T$, let \[ f(A, B) := \prod_{i \in A} \left(1 - \prod_{j \in B} (1-e_{ij})\right).\]Note that \[ f(A, B) = \begin{cases} 0 & \exists \: j\in A \ \text{connected to all} \ i \in B \\ 1 & \text{otherwise.} \end{cases} \]It follows that $f(A, B) = f(B, A)$ by swapping the order of products, so we rewrite the desired sum as \[ 1 + \sum_{S \subset T, S \neq \emptyset} f(S, T \setminus S), \]and the latter summation is even as it contains both $f(S, T \setminus S)$ as well as $f(T \setminus S, S)$ for each instance of $S$, and we are done. Remark: [motivation] The expression for the number of good subsets in terms of edge indicator variables was largely motivated by the application of combinatorial nullstellensatz to Theorem 6.1 of Alon's original paper on the technique. Remark: This proof is no different from a double counting argument; it's just a technical way to arrive at the same summation idea, in which we exploit symmetry to win.

We count pairs $(T_1, T_2)$ of subsets such that for any $t_1 \in T_1$ and $t_2 \in T_2$, $\gcd(t_1, t_2) = 1$. Note that if $T_1$ is good, we must have $T_2 = \emptyset$. Otherwise, there exists a set $S_1$ for this $T_1$ consisting of all the elements $s$ that do not share any prime factors with any $t_1 \in T_1$ that is empty; thus for a bad $T_1$ we can associate $2^{|S_1|}$ pairs. On the other hand, the total number of pairs is odd because $(T, T)$ is never a valid pair unless $T = \emptyset$ (as all positive integers are greater than $1$), and if $(T_1, T_2)$ is valid, $(T_2, T_1)$ must also be valid. Because only good subsets contribute an odd term to the sum, it follows that there must be an odd number of good subsets, as needed. Remark: The solution is motivated by the $x \to 2^x$ mapping exchanging positiveness with parity. Considering the set as a graph with an edge $st$ if $\gcd(s, t) > 1$ and looking at the rows and columns of the adjacency matrix naturally motivates counting these pairs $(T_1, T_2)$; they correspond to a row and column of the matrix such that the intersection $T_1 \cap T_2$ is the zero matrix.