For a positive integer $n$, if $n$ is a product of two different primes and $n \equiv 2 \pmod 3$, then $n$ is called "special number." For example, $14, 26, 35, 38$ is only special numbers among positive integers $1$ to $50$. Prove that for any finite set $S$ with special numbers, there exist two sets $A, B$ such that $A \cap B = \emptyset, A \cup B = S$ $||A| - |B|| \leq 1$ For all primes $p$, the difference between number of elements in $A$ which is multiple of $p$ and number of elements in $B$ which is multiple of $p$ is less than or equal to $1$.
Problem
Source: KMO 2023 P8
Tags: combinatorics
gnoka
06.11.2023 08:40
what do you mean by p in the third case？ any prime ？
mathlove_13520
06.11.2023 15:45
Let a Bipartite Graph $G=(P, Q)$ s.t. $P =$ {$p|p\equiv1(mod3)$} $Q =$ {$q|q\equiv2(mod3)$} $(p, q) \in E(G) \Leftrightarrow pq \in S$ Now the problem becomes : Find $S$, $T$ s.t. - $S \cap T = \phi, S \cup T = E(G)$ - $||S| - |T|| \leq 1$ - For all vertex $v$, the difference between number of edge containing $v$ in $S$ and number of edge containing $v$ in $T$ is less than or equal to $1$. We show this by induction. If the graph includes a loop, the number of edges of the loop will be even. let a loop $C$ = {$c_1, c_2, ... , c_n$}. remove $C$ and use induction. We get $S$ and $T$. Let $S'$ $=$ $S$ + {$(c_i, c_{i+1}) | i\equiv0(mod2)$} and $T'$ $=$ $T$ + {$(c_i, c_{i+1}) | i\equiv1(mod2)$} $S'$ and $T'$ match the conditions, and we are done. If not, each of the connected subgraphs in $G$ will be a tree. Then, there exists two leaves $l_1$, $l_2$ and vertexs $m_1$, $m_2$, ... , $m_s$ , $v$, $n_t$, ..., $n_1$ s.t. - $P$ = ($l_1$, $m_1$, $m_2$, ... , $m_s$ , $v$, $n_t$, ..., $n_1$, $l_2$) is a path. - $d(m_i)$ = $d(n_j)$ = $2$ remove $C$ and use induction. We get $S$ and $T$. Subdivide the cases when $s+t$ is even or odd, and we can make $S'$ and $T'$ simillarly like above. $S'$ and $T'$ match the conditions, and we are done.
It was 1 minute left when I wrote this solution on test lol
Anyway, it was a fun problem.
math_comb01
15.02.2024 18:07
Cute! Consider the bipartite graph $\mathcal{G} = (P,Q)$, $P$ the primes of the form $3k+1$ and $Q$ the primes of the form $3k+2$. Now we proceed by induction on the number of edges. If there is any cycle, then it must be of even length, so any other path will be a tree, now take a path joining two leaves, it passes through the node and every vertex in path have degree $2$ so removing this and using Induction hypothesis we're done.