Great orz

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

Great orz

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: FKMO 2025 P5

The post below has been deleted. Click to close.

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

14 posts

#1 h Mar 30, 2025, 4:54 AM

Y by

$S={1,2,...,1000}$ and $T'=\left\{ 1001-t|t \in T\right\}$ .
A set $P$ satisfies the following three conditions:
$1.$ All elements of $P$ are a subset of $S$ .
$2. A,B \in P \Rightarrow A \cap B \neq \O$
$3. A \in P \Rightarrow A' \in P$
Find the maximum of $|P|$ .

This post has been edited 3 times. Last edited by Hip1zzzil, Mar 30, 2025, 5:02 AM
Reason: Err

Z K Y

The post below has been deleted. Click to close.

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

69 posts

#2 h Mar 30, 2025, 4:57 AM

Y by

answer
Click to reveal hidden text

This post has been edited 2 times. Last edited by whwlqkd, Mar 30, 2025, 8:31 AM

Z K Y

The post below has been deleted. Click to close.

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

185 posts

#3 h Mar 30, 2025, 5:33 AM

Y by

Hip1zzzil wrote:

$S={1,2,...,1000}$ and $T'=\left\{ 1001-t|t \in T\right\}$ .
A set $P$ satisfies the following three conditions:
$1.$ All elements of $P$ are a subset of $S$ .
$2. A,B \in P \Rightarrow A \cap B \neq \O$
$3. A \in P \Rightarrow A' \in P$
Find the maximum of $|P|$ .

The notations used here are slightly different with the original statement. It would be better to change it as:

Quote:

For a subset $T$ of the set $S = \{1, 2, \dots, 1000\}$ , let $\tilde{T} = \{1001 - t \ | \ t \in T\}$ . Find the maximum number of elements in the set $\mathcal{P}$ that satisfies all of the three following conditions:

All elements of $\mathcal{P}$ are subsets of $S$ .
For any two elements $A, B$ of $\mathcal{P}$ , $A\cap B$ is not empty.
For any element $A$ of $\mathcal{P}$ , $\tilde{A} \in \mathcal{P}$ .

Z K Y

The post below has been deleted. Click to close.

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

59 posts

#4 h Mar 30, 2025, 6:11 AM

Y by

solution sketch

Z K Y

The post below has been deleted. Click to close.

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

persamaankuadrat

150 posts

persamaankuadrat

#5 h Mar 30, 2025, 7:41 AM

Y by

@above, how did you calculate $2^{500}$ ?

Z K Y

The post below has been deleted. Click to close.

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

69 posts

#6 h Mar 30, 2025, 7:45 AM

Y by

Pick one in each of that sets:
{1,1000},{2,999},{3,998},…,{500,501}

Z K Y

The post below has been deleted. Click to close.

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

persamaankuadrat

150 posts

persamaankuadrat

#7 h Mar 30, 2025, 7:50 AM • 2 Y

Y by k2i_forever, whwlqkd

Haha! I was walking around my kitchen and realized that I was thinking $T^{C}$ the wrong way...you replied before I got to delete my comment! Thanks anyways :-D

:-D

Z K Y

The post below has been deleted. Click to close.

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

119 posts

sansae

#8 h Mar 30, 2025, 3:41 PM

Y by

Let $\widetilde{T}:=T'$ . Observe that $\widetilde{A^{C}}={(\widetilde{A})}^{C}$ .

So we can partite $2^{1000}$ sets into groups of the form $\{A, A^{C}, \widetilde{A}, \widetilde{A}^{C}\}$ , where some elements may coincide in each group. If the number of elements in some group is not equal to $4$ , then the only possibility occurred are $\{A=\widetilde{A}, A^{C}=\widetilde{A}^{C}\}$ and $\{A=\widetilde{A}^{C}, A^{C}=\widetilde{A}\}$ . Note that

(i) In a group of $4$ sets, at most $2$ sets can be chosen.
(ii) In $\{A=\widetilde{A}, A^{C}=\widetilde{A}^{C}\}$ , at most $1$ set can be chosen.
(iii) In $\{A=\widetilde{A}^{C}, A^{C}=\widetilde{A}\}$ , not set can be chosen.

Since there are $2^{500-1}$ groups of the form $\{A=\widetilde{A}^{C}, A^{C}=\widetilde{A}\}$ , at most $2^{999}-2^{499}$ sets can be chosen.

For construction,
(i) In a group of $4$ sets $\{A, A^{C}, \widetilde{A}, \widetilde{A}^{C}\}$ , choose $\{A, \widetilde{A}\}$ if $|A| \ge 500$ and $\{A^{C}, \widetilde{A}^{C}\}$ if $|A|<500$ .
(ii) In a group of $2$ sets $\{A=\widetilde{A}, A^{C}=\widetilde{A}^{C}\}$ , choose $\{A\}$ if $|A|\ge 500$ and $\{A^{C}\}$ if $|A|<500$ .

This gives $2^{999}-2^{499}$ sets, and each of the sets have $\ge 500$ elements (by construction). By consturction, the first and third condition of the statement are satisfied. If the second statement failed for some $A, B$ , then we would have $|A|=|B|=500$ and thus $A=B^{C}$ , but by construction we can guarantee that we had never chosen such $(A, B)$ . This finishes the proof.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a