We say $m \circ n$ for natural m,n $\Longleftrightarrow$ nth number of binary representation of m is 1 or mth number of binary representation of n is 1. and we say $m \bullet n$ if and only if $m,n$ doesn't have the relation $\circ$ We say $A \subset \mathbb{N}$ is golden $\Longleftrightarrow$ $\forall U,V \subset A$ that are finite and arenot empty and $U \cap V = \emptyset$,There exist $z \in A$ that $\forall x \in U,y \in V$ we have $z \circ x ,z \bullet y$ Suppose $\mathbb{P}$ is set of prime numbers.Prove if $\mathbb{P}=P_1 \cup ... \cup P_k$ and $P_i \cap P_j = \emptyset$ then one of $P_1,...,P_k$ is golden.
Problem
Source: Iran 2004
Tags: number theory, prime numbers, combinatorics proposed, combinatorics
Myth
18.09.2004 20:42
Hi, Omid Hatami! Are you sure that statement is correct? Maybe I am wrong, but it seems I disprove it.
Omid Hatami
19.09.2004 14:48
Yes I'm sure that problem is correct. It was our exam last week.
sam-n
19.09.2004 15:12
yes the main idea of this problem was given from the paper from erdos about random graph (just a liittle manipulation)
Omid Hatami
28.09.2004 11:34
Of course the official solution is easy using Dirichlet theorem in number theory
Myth
28.09.2004 11:42
If you say that problem is correct, it means that I still don't understand statement.
Omid Hatami
28.09.2004 21:19
Well I mean that we ahve a relation and $A \subset \mathbb{N}$ we say $A$ is golden if and only if for evey $U,V \subset A$ that $U \cap V= \emptyset$ then thre exist $z \in A$ that z has relation with every $x \in U$ and does'nt have relation with every $y\in V$
Myth
28.09.2004 21:28
Thank you, but the same is written above
Omid Hatami
28.09.2004 21:33
Well I don't realize where is the problem. Explain more that what don't you understand.
Myth
28.09.2004 21:55
Let $P_1=\{5,7\}$. Set $P_1$ is not golden (U={5}, V={7}). Let $P_2=P\setminus P_1$. Suppose $P_2$ is golden. Consider $U=\{13\}\cup \{a\in P_2\,|,13\circ a\}$, $V=\{11\}$. We see $13\bullet 11$ and $2\not\in U$. For all remaining prime numbers we have $p \bullet p$, since binary representation of $p$ has 0 on p-th place. So if $z\circ x\ \forall x\in U$ then $z\circ 13$ $\Rightarrow$ $z\in U$, but $z\bullet z$ -- contradiction. What is wrong?
Omid Hatami
29.09.2004 09:23
Excuse me I didn't say that $U,V$ must be finite but I thought I had said.
Myth
29.09.2004 15:24
I am very angry because both Omid and Sam-n said that statement is correct... rrrrrr... Now problem become very clear and really simple if we are allowed to use Dirichlet theorem.
sam-n
29.09.2004 17:04
oh myth i think it is part of default (being finite ) anyway sorry