Golden set

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Golden set

G H J

Reveal topic tags

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Iran 2004

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#1 h Sep 18, 2004, 11:00 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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.

This post has been edited 1 time. Last edited by Omid Hatami, Sep 29, 2004, 6:24 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4464 posts

Myth

#2 h Sep 18, 2004, 5:42 PM • 2 Y

Y by Adventure10, Mango247

Hi, Omid Hatami!
Are you sure that statement is correct?
Maybe I am wrong, but it seems I disprove it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#3 h Sep 19, 2004, 11:48 AM • 2 Y

Y by Adventure10, Mango247

Yes I'm sure that problem is correct. It was our exam last week.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

793 posts

sam-n

#4 h Sep 19, 2004, 12:12 PM • 2 Y

Y by Adventure10, Mango247

yes the main idea of this problem was given from the paper from erdos about random graph (just a liittle manipulation)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#5 h Sep 28, 2004, 8:34 AM • 2 Y

Y by Adventure10, Mango247

Of course the official solution is easy using Dirichlet theorem in number theory

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4464 posts

Myth

#6 h Sep 28, 2004, 8:42 AM • 2 Y

Y by Adventure10, Mango247

If you say that problem is correct, it means that I still don't understand statement.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#7 h Sep 28, 2004, 6:19 PM • 2 Y

Y by Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4464 posts

Myth

#8 h Sep 28, 2004, 6:28 PM • 2 Y

Y by Adventure10, Mango247

Thank you, but the same is written above

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#9 h Sep 28, 2004, 6:33 PM • 2 Y

Y by Adventure10, Mango247

Well I don't realize where is the problem. Explain more that what don't you understand.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4464 posts

Myth

#10 h Sep 28, 2004, 6:55 PM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#11 h Sep 29, 2004, 6:23 AM • 2 Y

Y by Adventure10, Mango247

Excuse me I didn't say that $U,V$ must be finite but I thought I had said.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4464 posts

Myth

#12 h Sep 29, 2004, 12:24 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

793 posts

sam-n

#13 h Sep 29, 2004, 2:04 PM • 2 Y

Y by Adventure10, Mango247

oh myth i think it is part of default (being finite )

anyway sorry

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a